1.3 ConcurrentHashMap 的线程安全性

HashMap的底层算法采用了链地址法来解决哈希冲突

哈希表

在数据结构中有一种称为哈希表的数据结构，它实际上是数组的推广。如果有一个数组，要最有效的查找某个元素的位置，如果存储空间足够大，那么可以对每个元素和内存中的某个地址对应起来，然后把每个元素的地址用一个数组（这个数组也称为哈希表）存储起来，然后通过数组下标就可以直接找到某个元素了。这种方法术语叫做直接寻址法。这种方法的关键是要把每个元素和某个地址对应起来，所以如果当一组数据的取值范围很大的时候，而地址的空间又有限，那么必然会有多个映射到同一个地址，术语上称为哈希冲突，这时映射到同一个地址的元素称为同义词。毕竟，存储空间有限，所以冲突是不可避免的，但是可以尽量做到减少冲突。目前有两种比较有效的方法来解决哈希冲突：

链地址法 开放地址法 这里简要说明一下开放地址法，顾名思义，就是哈希表中的每个位置要么存储了一个元素要么为NULL。当数据比较多的时候，查找一个元素挺费事的，但是可以使用探测的方法进行查找。这个话题与本主题关系不大，感兴趣的小伙伴可以自行研究。

链地址法

为什么要把链地址法单独拿出来呢？因为后面有用。 链地址法的大概思想是：对于每个关键字，使用哈希函数确定其在哈希表中位置（也就是下标），如果该位置没有元素则直接映射到该地址；如果该位置已经有元素了，就把该元素连接到已存在元素的尾部，也就是一个链表，并把该元素的next设置为null。这样的话，每个哈希表的位置都可能存在一个链表，这种方式要查找某个元素效率比较高，时间复杂度为O(1+a)，a为哈希表中每个位置链表的平均长度。这里需要假设每个元素都被等可能映射到哈希表中的任意一个位置。