Java集合框架与源码解析

深入理解Java集合底层原理

一、集合框架概述

1.1 继承体系

┌─────────────────────────────────────────────────────────────────────┐│                    Java集合框架继承体系图                              │├─────────────────────────────────────────────────────────────────────┤│                                                                     ││   ┌─────────────────────────────┐                                 ││   │        Iterable            │                                 ││   │        (java.lang)         │                                 ││   └──────────────┬──────────────┘                                 ││                  │                                                ││   ┌─────────────┴──────────────┐                                ││   │                           │                                 ││   ▼                           ▼                                 ││ ┌───────────────┐    ┌───────────────────────┐                ││ │ Collection   │    │      Map             │                ││ └──────┬──────┘    └──────────┬──────────┘                ││        │                       │                                 ││   ┌───┴────┐            ┌────┴──────┐                      ││   │        │            │            │                              ││   ▼        ▼            ▼            ▼                              ││ List    Set          HashMap    SortedMap                       ││                                                         │└─────────────────────────────────────────────────────────────┘

二、List集合

2.1 ArrayList源码解析

/** * ArrayList源码解析 *  * 特点：动态数组、随机访问快、插入删除慢 */publicclassArrayList<E> extendsAbstractList<E> implementsList<E>, RandomAccess, Cloneable, Serializable{// 默认容量privatestaticfinalint DEFAULT_CAPACITY = 10;// 空数组privatestaticfinal Object[] EMPTY_ELEMENTDATA = {};// 存储元素的数组private Object[] elementData;// 元素数量privateint size;/**     * 添加元素     */publicbooleanadd(E e){// 扩容检查        ensureCapacityInternal(size + 1);        elementData[size++] = e;returntrue;    }/**     * 扩容机制     */privatevoidensureCapacityInternal(int minCapacity){if (elementData == EMPTY_ELEMENTDATA) {            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);        }if (minCapacity - elementData.length > 0) {            grow(minCapacity);        }    }/**     * 扩容 - 1.5倍     */privatevoidgrow(int minCapacity){int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0) {            newCapacity = minCapacity;        }        elementData = Arrays.copyOf(elementData, newCapacity);    }/**     * 移除元素     */public E remove(int index){        rangeCheck(index);        modCount++;        E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0) {            System.arraycopy(elementData, index+1, elementData, index, numMoved);        }        elementData[--size] = null;return oldValue;    }}

2.2 LinkedList源码

/** * LinkedList源码解析 *  * 特点：双向链表、插入删除快、随机访问慢 */publicclassLinkedList<E> extendsAbstractSequentialList<E> implementsList<E>, Deque<E>, Cloneable, Serializable{// 头节点transient Node<E> first;// 尾节点transient Node<E> last;// 节点结构privatestaticclassNode<E> {        E item;        Node<E> next;        Node<E> prev;    }/**     * 添加到链表尾部     */voidlinkLast(E e){final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);        last = newNode;if (l == null) {            first = newNode;        } else {            l.next = newNode;        }        size++;        modCount++;    }/**     * 添加到链表头部     */privatevoidlinkFirst(E e){final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);        first = newNode;if (f == null) {            last = newNode;        } else {            f.prev = newNode;        }        size++;        modCount++;    }}

三、Map集合

3.1 HashMap源码

/** * HashMap源码解析 *  * 特点：数组+链表+红黑树、O(1)查找 */publicclassHashMap<K,V> extendsAbstractMap<K,V> implementsMap<K,V>, Cloneable, Serializable{// 初始容量staticfinalint DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16// 最大容量staticfinalint MAXIMUM_CAPACITY = 1 << 30;// 负载因子staticfinalfloat DEFAULT_LOAD_FACTOR = 0.75f;// 数组transient Node<K,V>[] table;// 节点数量transientint size;/**     * 节点结构     */staticclassNode<K,V> implementsMap.Entry<K,V> {finalint hash;final K key;        V value;        Node<K,V> next;    }/**     * put方法     */public V put(K key, V value){return putVal(hash(key), key, value, false, true);    }final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict){        Node<K,V>[] tab;        Node<K,V> p;int n, i;// 扩容if ((tab = table) == null || (n = tab.length) == 0) {            n = (tab = resize()).length;        }// 计算索引if ((p = tab[i = (n - 1) & hash]) == null) {            tab[i] = newNode(hash, key, value, null);        } else {            Node<K,V> e;            K k;// 相同keyif (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {                e = p;            } elseif (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) {                            treeifyBin(tab, hash);                        }break;                    }if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {break;                    }                    p = e;                }            }// 替换值if (e != null) {                V oldValue = e.value;if (!onlyIfAbsent || oldValue == null) {                    e.value = value;                }return oldValue;            }        }        modCount++;if (++size > threshold) {            resize();        }returnnull;    }/**     * 扩容机制 - 2倍     */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;            } elseif ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                      oldCap >= DEFAULT_INITIAL_CAPACITY) {                newThr = oldThr << 1;            }        } elseif (oldThr > 0) {            newCap = oldThr;        } else {            newCap = DEFAULT_INITIAL_CAPACITY;            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }if (newThr == 0) {            newThr = (int)(newCap * loadFactor);        }        threshold = newThr;        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;                    } elseif (e instanceof TreeNode) {                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                    } else {// 链表拆分                        Node<K,V> loHead = null, loTail = null;                        Node<K,V> hiHead = null, hiTail = null;do {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 = e.next) != null);if (loTail != null) {                            loTail.next = null;                            newTab[j] = loHead;                        }if (hiTail != null) {                            hiTail.next = null;                            newTab[j + oldCap] = hiHead;                        }                    }                }            }        }return newTab;    }}

四、Set集合

4.1 HashSet源码

/** * HashSet源码 *  * 基于HashMap实现 */publicclassHashSet<E> extendsAbstractSet<E> implementsSet<E>, Cloneable, Serializable{// 底层使用HashMapprivatetransient HashMap<E,Object> map;// 固定值privatestaticfinal Object PRESENT = new Object();publicHashSet(){        map = new HashMap<>();    }publicbooleanadd(E e){return map.put(e, PRESENT) == null;    }publicbooleanremove(Object o){return map.remove(o) == PRESENT;    }publicvoidclear(){        map.clear();    }}

五、Collections工具类

5.1 排序操作

import java.util.*;/** * Collections工具类 */publicclassCollectionsDemo{/**     * 排序     */publicvoidsortDemo(){        List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 2));// 自然排序        Collections.sort(list);// 自定义排序        Collections.sort(list, (a, b) -> b - a);// 翻转        Collections.reverse(list);// 洗牌        Collections.shuffle(list);// 交换        Collections.swap(list, 0, 1);    }/**     * 查找     */publicvoidsearchDemo(){        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);// 二分查找 - 必须有序int index = Collections.binarySearch(list, 3);// 最大最小值        Integer max = Collections.max(list);        Integer min = Collections.min(list);    }/**     * 同步控制     */publicvoidsyncDemo(){// 同步List        List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());// 同步Set        Set<Integer> syncSet = Collections.synchronizedSet(new HashSet<>());// 同步Map        Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());    }/**     * 不可变集合     */publicvoidimmutableDemo(){        List<Integer> list = Collections.unmodifiableList(Arrays.asList(1, 2, 3));// 尝试修改会抛出异常// list.add(4); // UnsupportedOperationException    }}

总结

┌─────────────────────────────────────────────────────────────────────┐│                Java集合框架要点总结                                   │├─────────────────────────────────────────────────────────────────────┤│                                                                     ││   📋 List                                                          ││   └── ArrayList / LinkedList / Vector                            ││                                                                     ││   🗺️ Map                                                           ││   └── HashMap / LinkedHashMap / TreeMap                        ││                                                                     ││   📦 Set                                                           ││   └── HashSet / LinkedHashSet / TreeSet                        ││                                                                     ││   🔧 工具类                                                         ││   └── Collections / Arrays                                       ││                                                                     ││   ⚡ 核心原理                                                       ││   └── 扩容机制 / 哈希冲突 / 红黑树                               ││                                                                     │└─────────────────────────────────────────────────────────────────────┘

持续更新中，欢迎关注”军军程序课堂”获取更多面试干货！