Java集合框架源码深度解读：从ArrayList到HashMap
在Java的世界里，集合框架堪称数据存储的基石。无论是简单的列表还是复杂的映射关系，Java集合框架都为我们提供了强大且灵活的选择。今天，就让我们一起深入挖掘ArrayList、LinkedList和HashMap这三大经典集合类的源码奥秘。
ArrayList：动态数组的魔法
ArrayList作为数组和链表的完美结合体，以其高效的随机访问能力和动态扩展性赢得了众多开发者的心。它的核心在于内部维护了一个Object[]类型的elementData数组。
当我们向ArrayList中添加元素时，add()方法首先会检查当前容量是否足够。如果不够，它将触发扩容机制，通过Arrays.copyOf()方法将原数组大小扩展为原来的1.5倍。这种渐进式的扩容策略有效地避免了频繁的小规模扩展带来的性能损耗。
关键代码片段解析
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Ensure the capacity is adequate
elementData[size++] = e; // Add the element and increase size
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) {
modCount++;
// Check for overflow
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
这段代码展示了ArrayList是如何确保其容量适应不断增长的数据量的。特别是grow()方法，它通过创建一个新的更大数组，并将原有数据迁移过去，实现了容量的增长。
LinkedList：链表结构的魅力
与ArrayList不同，LinkedList采用双向链表来存储数据。这种结构使得插入和删除操作更加高效，但随机访问则相对较慢。
LinkedList的节点定义了prev和next两个指针，分别指向前后相邻的节点。这样就形成了一个完整的双向链表。值得注意的是，LinkedList还实现了Deque接口，从而具备了队列和双端队列的操作能力。
关键代码片段解析
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Node类是LinkedList的基础构建单元，每个Node对象都包含了它所存储的元素以及指向其前驱和后继节点的引用。通过这样的设计，LinkedList能够轻松地在链表的任意位置插入或移除元素。
HashMap：哈希表的艺术
最后，我们来到HashMap这个强大的映射工具。它利用哈希函数将键映射到数组的不同索引上，从而实现快速的查找、插入和删除操作。
HashMap的核心在于其内部的Node[] table数组。当我们将一个键值对存入HashMap时，首先计算该键的哈希值，然后根据哈希值定位到table数组中的具体位置。如果该位置已经有元素存在，则会触发链地址法来处理冲突。
关键代码片段解析
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
i = (n - 1) & hash;
if ((p = tab[i]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// Handle collision...
}
}
这段代码展示了HashMap的基本put操作流程。从最初的table初始化，到最终的节点插入，每一步都体现了HashMap对于性能优化的极致追求。
通过这些详细的源码分析，我们可以看到Java集合框架是如何巧妙地平衡各种需求，提供既强大又灵活的数据存储解决方案的。希望这篇文章能让你对ArrayList、LinkedList和HashMap有更深刻的理解，并激发你进一步探索更多集合类的兴趣！