19 | 散列表（中）：如何打造一个工业级水平的散列表

在你熟悉的编程语言中，哪些数据类型底层是基于散列表实现的？散列函数是如何设计的？散列冲突是通过哪种方法解决的？是否支持动态扩容呢？

HashMap

• 实现机制： 基于散列表实现，使用数组和链表（或红黑树）的组合。

• 散列函数设计： 默认使用键的 hashCode 方法和散列算法来计算散列码。可以通过实现 hashCode 方法来自定义键的散列方式。

• 散列冲突解决： 使用链地址法（Separate Chaining），每个散列槽上存储一个链表（或红黑树）。

• 动态扩容： 支持动态扩容，当元素数量达到容量的阈值时，重新调整大小。

HashSet

• 实现机制： 基于 HashMap 实现，只是在 HashMap 中只使用了键，而在 HashSet 中键和值相同。

• 散列函数设计： 默认使用元素的 hashCode 方法和散列算法来计算散列码，类似于 HashMap。

• 散列冲突解决： 使用链地址法，类似于 HashMap。

• 动态扩容： 支持动态扩容，内部使用一个 HashMap，因此在 HashMap 扩容时，HashSet 也会相应地进行扩容。

Hashtable

• 实现机制： 基于散列表实现，使用数组和链表的组合。

• 散列函数设计： 默认使用键的 hashCode 方法和散列算法来计算散列码。

• 散列冲突解决： 使用开放地址法，采用线性探测方式解决冲突。

• 动态扩容： 支持动态扩容，当元素数量达到容量的阈值时，重新调整大小。

LinkedHashMap

• 实现机制： 基于散列表实现，与 HashMap 类似，但保留了元素的插入顺序。

• 散列函数设计： 默认使用键的 hashCode 方法和散列算法。

• 散列冲突解决： 使用链地址法，每个散列槽上存储一个链表。

• 动态扩容： 支持动态扩容，与 HashMap 类似。