哈希表中存在哈希冲突时存入链表的问题

来源：14-7 哈希表更复杂的动态空间处理方法

v不离不弃v

2020-02-05

波波老师，您说我们创建的哈希表，当存在哈希冲突的时候，转为链表储存，但是我们在创建的时候是在TreeMap数组中的每个索引下创建了TreeMap对象，我可不可以理解为是基于树的映射对象，这并不是链表呀？是不是要创建LinkedList对像才可以呢？

写回答

1回答

liuyubobobo

2020-02-05

已采纳

印象里我在课程中说过，Java 语言标准库的实现是，在数据量比较小的情况下，映射对应的是链表，当一个键的数据量比较大的时候，转成红黑树处理。不过使用红黑树还有一个前提条件，键必须有可比性。

在课程中，我直接使用红黑树存储了。这个局限性，在这一章的最后一节也有提及。

是的，如果你希望实现更通用的哈希表，将每个键映射成链表就可以。

继续加油！：）

Coder小白菜

波波老师好，我有一个相关的问题。就是您提及的当一个键的数据量比较大的时候会从链表转成红黑树，但是在课程代码实现中当一个键的平均数据量大于10，数组就会扩容，这样键的平均数据量最大也超不过10，那如何会触发条件将链表转变为红黑树呢？

2020-05-15

共1条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 2

回答 1

回答 1

回答 2

回答 1