正文

Java集合框架深度揭秘：源码剖析，解锁高效编程之道

/0 浏览量
0427

引言

Java集合框架是Java编程语言中不可或缺的一部分，它提供了一系列用于存储和操作数据的接口和类。熟练掌握Java集合框架对于提高编程效率和质量至关重要。本文将深入剖析Java集合框架的源码，揭示其内部实现机制，帮助读者解锁高效编程之道。

集合框架概述

Java集合框架主要包括两大类：Collection和Map。Collection用于存储一组元素，而Map用于存储键值对。

Collection接口

Collection接口是所有集合类的根接口，它定义了集合的基本操作，如添加、删除、搜索和遍历元素。Collection接口的主要子接口包括List、Set和Queue。

List接口

List接口表示一个有序集合，其中元素可以重复。常见的List实现类有ArrayList、LinkedList和Vector。

  • ArrayList：基于动态数组实现，提供快速的随机访问，但插入和删除元素时性能相对较慢。
  • LinkedList：基于链表实现，插入和删除元素速度快，但随机访问性能较差。
  • Vector：与ArrayList类似，但在多线程环境下提供了同步控制。

Set接口

Set接口表示一个无序集合，其中元素不允许重复。常见的Set实现类有HashSet、LinkedHashSet和TreeSet。

  • HashSet：基于哈希表实现，存储元素时会计算其哈希值，因此插入和查找速度快。
  • LinkedHashSet：保持元素的插入顺序。
  • TreeSet：使用红黑树结构，保证了元素排序的有序性。

Map接口

Map接口表示一个键值对集合，根据键查找值。常见的Map实现类有HashMap、TreeMap和Hashtable。

  • HashMap：基于哈希表实现，提供快速查找和插入。
  • TreeMap：基于红黑树实现，自动对键值对进行排序。
  • Hashtable：与HashMap类似，但在多线程环境下提供了同步控制。

源码剖析

以下将分别对ArrayList、HashMap和HashSet的源码进行剖析。

ArrayList源码剖析

ArrayList基于动态数组实现，其源码如下：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    private transient Object[] elementData;
    private int size;

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }

    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    public E get(int index) {
        rangeCheck(index);
        return (E) elementData[index];
    }

    public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

    public E remove(int index) {
        rangeCheck(index);
        E oldValue = (E) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
        return oldValue;
    }

    // ... 省略其他方法 ...
}

HashMap源码剖析

HashMap基于哈希表实现，其源码如下：

public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;

    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    transient Node<K, V>[] table;
    transient int size;
    int threshold;
    final float loadFactor;

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        this.threshold = (int) (DEFAULT INITIAL_CAPACITY * DEFAULT LOAD_FACTOR);
        table = (Node<K, V>[]) EMPTY_NODE_ARRAY;
    }

    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 = (hash & (n - 1))) == null) {
            tab[i] = newNode(hash, key, value, null);
        } else {
            Node<K, V> e; K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
                e = p;
            } 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 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        break;
                    }
                    p = e;
                }
            }
            if (onlyIfAbsent) {
                return value;
            }
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
        ++modCount;
        if (++size > threshold) {
            resize();
        }
        return null;
    }

    // ... 省略其他方法 ...
}

HashSet源码剖析

HashSet基于HashMap实现，其源码如下：

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    private static final long serialVersionUID = 0;
    private transient HashMap<E, Object> map;

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    public int size() {
        return map.size();
    }

    public void clear() {
        map.clear();
    }

    // ... 省略其他方法 ...
}

总结

通过本文对Java集合框架的源码剖析，读者可以深入理解其内部实现机制，从而在编程实践中更好地选择和使用集合类。掌握Java集合框架，将有助于提高编程效率和质量，解锁高效编程之道。

-- 展开阅读全文 --