这篇文章介绍了HashMap(哈希映射)的概念、在JDK中的实现原理及其在不同编程语言中的实现。
HashMap的核心概念包括:
* 键(key):用于生成哈希索引的输入。
* 哈希函数(hash function):将键转换为哈希索引。
* 哈希表(hash table):存储键值对的列表数组。
* 负载系数(load factor):衡量哈希表填充程度的指标,默认为0.75。
HashMap的优点是:
* 增删和搜索的时间复杂度为O(1)。
JDK中的HashMap实现原理:
* 存储方式:使用哈希表存储,每个槽(Solt)是一个集装箱(Bin)。通过键的哈希值与哈希表容量取余来确定存储索引。为了提高效率,取余运算通常转化为位运算(i = (n - 1) & hash)。哈希表容量总是2的整数次方,扩容时容量变为原来的2倍,通过位运算(newThr = oldThr << 1)计算新阈值。
* 哈希冲突解决方法:当集装箱内元素数量较少时(小于树化阈值,默认为8),使用链表存储。当元素数量超过阈值时,集装箱会“树化”,转为使用红黑树存储,以提高查找效率。
* 红黑树插入键:优先使用键的哈希值比较,若哈希值不可比较则比较键的Comparable接口实现,最后使用决胜局算法(tieBreakOrder)进行比较。决胜局算法先比较类型名称,若仍无法比较则回退使用identityHashCode()。
* 红黑树搜索键:通过键的引用相等或equals方法比较判断键相等。搜索过程也优先使用哈希值,然后是Comparable接口,若冲突则递归查找左右节点。
* 自动扩容:当元素数量超过负载系数规定的阈值时,HashMap会自动扩容。扩容时,所有元素需要根据新的哈希表容量重新计算位置并移动。对于树化的集装箱,会根据元素的哈希值高低位将其分离,并可能在树规模较小时拆分成链表。
* 遍历顺序:HashMap本身不保证遍历顺序。如果需要保证遍历顺序,可以使用JDK提供的LinkedHashMap类,它通过在节点中添加before和after属性来维护一个全局的双向链表,从而实现遍历顺序的保持。
文章最后提供了使用Python、C++和Java实现HashMap,以及Python和C++实现LinkedHashMap的代码示例。