如何解决hash冲突，ThreadLocal如何解决哈希冲突

解决hash冲突的方法

1.链式地址法

2.开放寻址法 3.再HASH法 4.建立公共溢出池

4方法浪费内存，3增加了算法的复杂度。

链式地址法（HashMap)

优点：

  处理冲突简单，且无堆积现象，平均查找长度短；   链表中的结点是动态申请的，适合构造表不能确定长度的情况；   相对而言，拉链法的指针域可以忽略不计，因此较开放地址法更加节省空间。   插入结点应该在链首，删除结点比较方便，只需调整指针而不需要对其他冲突元素作调整。

缺点：   指针占用较大空间时，会造成空间浪费。若空间用于增大散列表规模进而提高开放地址法的效率。

开放地址法： 缺点：   容易产生堆积问题；   不适于大规模的数据存储；   结点规模很大时会浪费很多空间；   散列函数的设计对冲突会有很大的影响；   插入时可能会出现多次冲突的现象，删除的元素是多个冲突元素中的一个，需要对后面的元素作处理，实现较复杂；

优点：   当节点规模较少，或者装载因子较少的时候，使用开发寻址较为节省空间，如果将链式表的指针用于扩大散列表的规模时，可使得装载因子变小从而减少了开放寻址中的冲突，从而提高平均查找效率。

ThreadLocal如何解决哈希冲突

*线性探测的方式（*开放地址法*）*。来解决hash冲突，而hashMap则是通过链地址法来解决hash冲突。

可以ThreadLocal类用两层HashMap的kv，进行对象存储。外面的HashMap的Key是ThreadID，Value是内层的ThreadLocalMap的维护的Entry(ThreadLocal<?> k, Object v)数组。

和HashMap的最大的不同在于，ThreadLocalMap结构非常简单，没有next引用，也就是说ThreadLocalMap中解决Hash冲突的方式，并非链表的方式，而是采用线性探测的方式（开放地址法）。

所谓线性探测，就是根据初始key的hashcode值，确定元素在table数组中的位置，如果发现这个位置上，已经有其他key值的元素被占用，则利用固定的算法，寻找一定步长的下个位置，依次判断，直至找到能够存放的位置。

核心：由于ThreadLocalMap使用线性探测法，来解决散列冲突，所以实际上Entry[]数组在程序逻辑上，是作为一个环形存在的。

所以这里引出的良好建议是：

每个线程只存一个变量，这样所有的线程，存放到map中的Key，都是相同的ThreadLocal，如果一个线程，要保存多个变量，就需要创建多个ThreadLocal，多个ThreadLocal放入Map中时，会极大的增加Hash冲突的可能