Collections

本文最后更新于 1 分钟前，文中所描述的信息可能已发生改变。

Java 集合框架（Java Collections Framework, JCF）提供了用于存储和操作数据的通用算法和数据结构。主要接口和类包括：

List：有序的可重复集合，如 ArrayList、LinkedList。
Set：无序的不可重复集合，如 HashSet、TreeSet。
Map：键值对映射，如 HashMap、TreeMap。
Queue：先进先出的集合，如 LinkedList、PriorityQueue。

增删改查
底层如何实现
版本更新优化
使用场景

List

ArrayList

优点：查询快，增删慢
缺点：线程不安全
底层实现：用 Object 数组实现，有扩容机制吗（1.5 倍扩容）
优化方法：预分配空间，避免频繁扩容
使用场景：随机访问频繁，增删操作较少

扩容机制：当 ArrayList 中的元素个数超过容量时，进行扩容。扩容是将容量变为原来的 1.5 倍，并将原有的数据复制到新的数组中。

java

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */); 
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

LinkedList

优点：增删快，查询慢
缺点：线程不安全
底层实现：双向链表
使用场景：增删操作频繁，查询操作较少，线程不安全

CopyOnWriteArrayList

优点：线程安全
底层实现：用 Object 数组实现，写时复制数组（加锁），读时读旧数据
使用场景：读多写少的场景

Map

HashMap

优点：查询快，增删快，存储 null 键值对
缺点：线程不安全，会造成值覆盖和循环链表（JDK1.7）
底层实现
- JDK1.7：数组+链表（拉链法），头插法
- JDK1.8：数组+链表/红黑树（拉链法），尾插法，当链表长度大于 8 时，判断数组长度是否小于 64，小于扩充数组，否则转化为红黑树，当红黑树节点小于 6 时转为链表
使用场景：键值对存储，线程不安全

扩容机制：当 HashMap 中的元素个数超过负载因子（默认 0.75）与容量的乘积时，进行扩容。扩容是将容量变为原来的两倍，并将原有的数据重新计算哈希值放入新的数组中。

java

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY; // 16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 0.75 * 16 = 12
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead; 
                        }
                    }
                }
            }
        }
        return newTab;
    }

for-each:
- for (Map.Entry<K, V> entry : map.entrySet()) { ... }：遍历键值对。
- for (K key : map.keySet()) { ... }：遍历键。
- Iterator<Map.Entry<K, V>> iterator = map.entrySet().iterator();：迭代器遍历。
- map.forEach((k, v) -> { ... })：Lambda 表达式遍历。
- map.entrySet().stream().forEach(entry -> { ... })：Stream API 遍历。
put:

hashcode() 和 equals()：
- hashCode()：返回对象的哈希码值，用于快速查找。
- equals()：用于比较两个对象是否相等，需要重写。
- 如果两个对象相等，它们的哈希码一定相等，但哈希码相等的两个对象不一定相等。
HashMap 的大小为什么是 2 的 n 次方大小呢？
- 通过 hash & (n-1) 可以快速计算索引，避免了取模运算。
- 为了减少哈希冲突，提高查询效率。
- 扩容时只需要将高位的 1 向左移动即可，避免了重新计算哈希值。
javascript
```
if (loTail != null) {
  loTail.next = null;
  newTab[j] = loHead;
}
if (hiTail != null) {
  hiTail.next = null;
  newTab[j + oldCap] = hiHead; 
}
```
1
2
3
4
5
6
7
8

TreeMap

优点：有序，查询快
底层实现：红黑树
使用场景：有序键值对存储，线程不安全

ConcurrentHashMap

优点：线程安全
底层实现
- JDK1.7：Segment（ReentrantLock） + 数组 + 链表
- JDK1.8：CAS + Synchronized + 数组 + 链表/红黑树
使用场景：高并发场景

put:
- 如果容器为空，使用 volatile + CAS 初始化容器
- 如果容器不为空，根据存储元素计算位置是否为空
  - 如果为空，使用 CAS 插入元素
  - 如果不为空，使用 synchronized 锁住链表或红黑树，插入元素

HashTable

优点：线程安全
缺点：性能较差，同一时刻只能有一个线程访问
底层实现：数组 + 链表，方法均用 synchronized 加锁
使用场景：线程安全

Set

实现原理：基于 Map 实现，只存储键值，通过 hashcode()和 equals()判断是否重复

HashSet

TreeSet

优点：有序

LinkedHashSet

优点：有序，保持插入顺序

常见问题

堆和栈的区别
HashMap 遍历方式
HashMap 实现原理
ArrayList 和 LinkedList 区别，访问效率和增改效率

List ​

ArrayList ​

LinkedList ​

CopyOnWriteArrayList ​

Map ​

HashMap ​

TreeMap ​

ConcurrentHashMap ​

HashTable ​

Set ​

HashSet ​

TreeSet ​

LinkedHashSet ​

常见问题 ​

List

ArrayList

LinkedList

CopyOnWriteArrayList

Map

HashMap

TreeMap

ConcurrentHashMap

HashTable

Set

HashSet

TreeSet

LinkedHashSet

常见问题