当前位置：首页 > web >正文

java集合类

web 2025/7/12 19:19:00

javaSE中3个重点: 面向对象相关知识

集合类 (数据结构,线程)

多线程

次重点: 网络 (计网)

常用类

异常

Java集合类概述

Java集合类位于java.util包中，主要用于存储和操作一组对象。根据数据结构和用途的不同，可分为三大类：List（有序可重复）、Set（无序唯一）和Map（键值对存储）。

核心接口与实现类

List接口

ArrayList：基于动态数组实现，随机访问效率高，但插入/删除元素时性能较低。
```
List<String> list = new ArrayList<>();
list.add("Java");
list.get(0); // 访问元素
```
LinkedList：基于双向链表实现，插入/删除效率高，但随机访问性能较差。
Vector：线程安全的动态数组，性能较低，是线程安全的。

Set接口

HashSet：基于哈希表实现，元素无序，允许null值。

Set<Integer> set = new HashSet<>();
set.add(1);
set.contains(1); // 检查元素

LinkedHashSet：维护插入顺序的HashSet。
TreeSet：基于红黑树实现，元素自然排序或自定义排序。

Map接口

HashMap：基于哈希表的键值对存储，非线程安全，允许null键/值。

基本特点: 双列集合,键不能重复,值可以重复,可以有一个key为null

Map<String, Integer> map = new HashMap<>();
map.put("Key", 100);
map.get("Key"); // 获取值  
数据结构:

源码

put方法源码分析

public V put(K key, V value) {//通过key计算哈希值return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {int h;                       为了减少哈希值冲突return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; //哈希表Node<K,V> p; //记录之前int n, i; //n是哈希表长度, i是索引if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//创建哈希表if ((p = tab[i = (n - 1) & hash]) == null) // == 97%16 根据哈希值计算位置//如果该位置为null,则直接将key,value包装到一个node对象中,直接存放到第i个位的第一个tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;//判断key是否重复, 先判断哈希值(快),但是哈希有问题,值相同,但内容不同,//所以在哈希值相同时,需要调用equals(),判断内容是否相同.if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//当key不重复时,判断类型是树类型还是链表类型else if (p instanceof TreeNode)//已经是树类型,向红黑树上添加元素e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//链表for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//添加完成后,判断链表长度if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//转红黑树break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;//key相同时,会用后面key的值,覆盖之前的相同的key的值afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

重点参数:

哈希表长度: 默认是16

哈希表每次扩容原来 2 倍

哈希表的负载因子 0.75, 哈希表不会装满的,装满会影响查询效率,所以会牺牲一定的空间而换取查询效率

链表长度上限是 8 ,尝试将链表转为红黑树,但是不一定转成功, 还会判断哈希表长度,哈希表长度小于64

会先扩容哈希表,扩容后所有元素位置需要重新计算,这样链表会变短,

只有当链表长度大于等于8且哈希表长度大于64,链表才会转成红黑树.

当红黑树节点数量减少为6个时,红黑树退化成链表