Lotus Docs Screenshot

RubitCat

每个优秀的人,都有一段沉默的时光。那段时光,是付出了很多努力,却得不到结果的日子,我们把它叫做扎根。

精选文章

Hero Image
HashMap

这篇文章介绍了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类,它通过在节点中添加beforeafter属性来维护一个全局的双向链表,从而实现遍历顺序的保持。

文章最后提供了使用Python、C++和Java实现HashMap,以及Python和C++实现LinkedHashMap的代码示例。

最近文章