当我们需要存储数据时，动态数组虽然可以自动扩容，但在初始时刻必须指定初始容量。对于那些在编译时无法确定数量、动态增长的数据，Java集合类提供了更好的解决方案。例如ArrayList、LinkedList和Vector虽然各有优点，但在插入、删除或遍历操作上存在不足。于是，Java引入了HashMap，它是一个散列表，存储键值对集合，支持高效查找。
为了实现快速查找，HashMap选择使用数组而不是链表，这样可以利用数组的索引在O(1)复杂度下实现查找。为了解决数组索引映射问题，引入了Hash算法将key映射为数组下标。然而，Hash算法可能会导致Hash冲突，为了解决这一问题，HashMap采用链地址法，将冲突位置转换为链表存储。
然而，当链表中的节点过多时，查找性能会受到影响。为了优化查找性能，当链表长度超过8时，HashMap会将链表转换成红黑树。这样可以将O(n)复杂度的查找效率提升至O(log n)。通过这种方式，HashMap在插入、删除和查找操作上都表现出色，成为了一种高效的数据结构。
下载本文
