第十一讲 并发哈希和固有并行

一、封闭寻址哈希集

封闭寻址算法将冲突元素（哈希值相同的元素）放在相同的桶中。每个桶用无锁链表实现。若桶太满，则需要调整表的大小（扩容）。

哈希表存在扩容问题:

  1. 为桶中元素的个数设定上限；
  2. 桶阈值：若任意一个桶的大小超过上限，则将哈希表的大小加倍。
  3. 全局阈值：若超过上限的桶的数量超过一定比例，则将哈希表的大小加倍。满载率是表中元素的个数与表的大小（即桶的数量与桶的大小的乘积）之比。在 Java 中，满载率（load factor）达到 0.75 时，就需要调整哈希表的大小。