HashMap的作用
HashMap哈希表，也叫做散列表。哈希表是一种比较特殊的数据结构，它遵循函数映射的思想，以Key: Value的方式存储数据。哈希表最大的特点是可以快速定位到要查找的数据，查询的时间复杂度接近O(1)。哈希表的原理并不复杂，简而言之就是根据Key来计算出存储位置，然后将数据放入该空间，查询时同样根据Key计算出存储位置后直接将相应的值取出。
哈希函数
根据Key来计算存储位置的计算规则我们称之为哈希函数。优化哈希表的关键就是表大小和哈希函数的选择。
常用的哈希函数
除留取余法
这种方法应该是最常用的哈希定址方法了。H(x) = x % p假定哈希表长度为s,则p一般取不超过s的最大质数
直接定址法
比较常用的方法
H(x) = a * x + b
冲突
哈希表还要解决的一个问题就是冲突，当选择了一个哈希函数之后，有可能不同的数据会计算出相同的key,比如H(x) = x % 5 这种算法，6 和 11 都会计算出1,此时就会产生冲突。如果不解决冲突，哈希表就无法构建出来。
解决冲突的方法
链接地址法
将有冲突的数据放在一个链表里，当查询时会根据key查到链表的第一个节点，然后遍历整个链表，找到相应的值。
开放定址法
最具代表性的一种是线性探测法
H(x) = x % 5
数据样本: {5, 6, 8, 12, 11}
计算Key: { 0, 1, 3, 2, 1}
存储数组 [0, 1, 2, 3, 4, 5, 6, 7 …..]
[5, 6, 12, 8, 11] 当存储11的时候，发现下标是1的位置以及被占据了，此时根据线性探测法的规则依次往后遍历，直到找到空的位置，所以在下标为4的位置填入11线性探测法最大的问题是冲突累计，解决一个冲突的同时会占据别的key的位置，又造成了新的冲突。
改良的方法有二次方探测法和随机数探测法