JAVA8中的解决hash冲突的方案和具体实例

一、分离链表法（链地址法，拉链法）

- 原理：未冲突的情况下，直接将该值存放在数组中（数组中的没一个位置，都是一个链表的头，如图一），一旦发生冲突（即原本存储的位置已经有值了），立即将已有冲突处的链表，指向现有值。

图一.png

- java中的应用：

• 1.hashMap(hashMap和concurrentHashMap，当前结构为链表并且是存值的时候在链表长度<8时，为链表，一旦>8，立即将链表转为红黑树；当前结构是树并且取值的时候，一旦长度<6就会成为链表。结构的变换取决于当前的状态和结构的长度)。
• 2.hashTable
• 3.hashSet

二、开放地址法

- 原理：开放地址法一般会有一个探测算法（以最简单的线性探测为例：即当前位置被占用，则继续向下走，直到下一个没被占用的位置，然后将值放在该位置中。）。当当前位置被占用，则根据探测算法计算下一次的位置，直至计算出的位置未被占用位置。

- java中的应用：

• 1.ThreadLocalMap

三、再哈希法

- 原理：顾名思义，当发生冲突的时候，在使用一次hash算法，直至不冲突为止。

- java中的应用：

• 暂未了解到，继续学习中...