1.前言

以前看hashmap的原理看了很多次，过了很久都忘记了。真心发现以前的看书方法不对。感觉学习还是要靠背书。这节好好的踏实的把散列这届记录下。

2.正题

散列函数：
将关键字(key) 映射成0--tablesize-1 这个范围中的某一个数，然后放到适当的单元中。这个映射就叫做“散列函数”。

冲突: 俩个或者多个关键字散列到同一个单元的时候。就会产生冲突。

装填因子:散列表的元素个数比上 tablesize 得到的值，为装填因子。

通常对于key为String的关键字来说。一种方法就是将String 的每个字符，转换成Ascll码。然后累加。之后在%tablesize。(tablesize 不能为素数)。

还有一种散列函数没搞明白，就不记录了。。

介绍完了散列函数。那么就来写下如何解决冲突问题：

1.分离链接法

image.png

在冲突的地方，加入一个单向链表。如何待插入的数据是一个新数据的时候，那么它将被插入链表的前端。不仅因为方面。更是因为最新插入的数据最有可能被用到。

当进行插入的时候。发现链表中有之前的一摸一样的key。那么就会替换掉oldValue：

image.png

。

问题1：hashmap为什么是无序的？
因为它是通过散列函数，映射得到数组的下标的。所以是无序的。

问题2：hashmap在多线程的情况下，是不安全的
hashmap 的源码是没有假如任何的锁机制。多线程的情况下。假设新插入的元素都是无重复的。那么在多线程的情况下，最后一个线程插入的数据，会覆盖之前插入的数据。所以链表的第一个数组，是最后一个线程的数。

缺点：由于给新单元分配地址需要时间，导致算法速度有些慢。

2.线程探测法
探测性散列表的table 要大于分离链接法。一般来说探测性散列表的装填因子<0.5。

线性探测法：以增量序列1，2，......，（TableSize－1）循环试探下一个存储地址

image.png

一次聚集现象:如上图的表插入30 之后。明显右边的数据要密集些。左边的数据要稀疏一点。这样的现象就叫做聚集现象。

缺点: 当表很大的时候，出现聚集情况，会导致新插入的数据要和每个单元进行比较。插入不成功的情况大大增多。

3.平方探测法
针对线性探测法的缺点，伟大的算法工程师，又想出了平方探测法，来解决线性探测法的聚集现象。

缺点：产生二次聚集。

3.LinkHashMap
LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。参考http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html

LinkHashMap 链表部分采用了双向链表。保证了插入顺序和访问顺序。

插入顺序