前言
近几日写代码时看到了老师应用缓存去解决一些须要常常从数据库中被查问的货色，而缓存用到了HashMap，因为考研时学到了Hash存储，所以借此再去理解一下HashMap.
Hash
Hash是将任意长度的数据映射出无限长度的数据，用来代表源数据，小到一串数据，大到任意类型任意大小的文件都能够通过肯定的算法来映射出一串数据，并且雷同的可能性极小，所以hash罕用来进行文件完整性校验。
常见的hash算法如MD-5,SHA-1,SHA-256等。
这些一罕用于明码加密。
咱们拿java中的String.hashCode()函数为例，展现一个hash算法的计算过程
public int hashCode() { int h = hash; // default 0 if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h;}咱们能够看到，hashCode()函数循环乘加字符串中的每个字符，失去最终的hash值。
Hash存储
如果仅仅依据失去的hash值来存储则会大大节约存储空间，如hash值为123456789则存到123456789号地位上，hash值为987654321则存到987654321地位上，那么会极大节约空间。所以截下来咱们用到hash函数进行再次映射。
学过数据结构的同学应该有所理解，hash存储有一个散列表，所有的数据都寄存在散列表中的相应地位上。散列表长度固定，比方散列表长度为10，那么表中就有0,1,2...9十个地位。咱们所要寄存的数据失去hash值通过hash函数映射到这10个地位中。
为了达到此成果，有很多结构散列值的算法，如除留余数法、平方取中法、折叠法、随机数法、数学分析法等。咱们以最常见的除留余数法，就是把键值通过一个固定的算法函数既所谓的hash函数转换成一个整型数字，而后将该数字对散列表长度进行取余，取余后果就当作散列表的下标(散列值)。
碰撞解决
不同的hash通过算法不免失去雷同的存储地位，为了解决这种碰撞咱们须要进行解决。
解决碰撞的办法有很多种，如线性探测法、拉链法等等。
线性探测法就是如果通过hash函数算出的地位上曾经有数据了，那就看紧邻的下一个地位有没有数据，没有数据就放到这个地位上，顺次类推。
如31就是应该在6的地位上，然而6的地位上曾经有27了，所以咱们找7地位，7地位没有数据，咱们放到7地位上。
负载因子=被除数/散列表长度
如负载因子为0.75，被除数为12，在散列表长度为16。
拉链法是每个存储地位存储一个指针，每个指针都指向一个链表。将通过hash函数算出的雷同地位的数据顺次放到链表上。
HashMap
hashMap也是散列表，同时也应用拉链解决抵触。
HashMap的默认初始容量为2^4(=16)，即便创立时指定初始容量，HashMap外部也会计算一个不小于指定容量的、最靠近的且为2的整数次幂的一个值作为初始容量。
为什么是2的整数次幂？
因为咱们在hash存储时应用了除留余数法，然而求余数计算比较复杂。所以咱们简化为与2^n-1进行与操作。从而失去2的n次方个不同的后果。如果一个数据对应二进制为11011011，那么它与1111的与运算失去后四位1011。
如果不是2的整数倍，比如说容量为12，那么对应每个hash值与1011（11）进行与运算，那么10111101与1011与运算为1001，那么X1XX地位上永远不会有数据。
同时也对拉链表进行优化。咱们想一种最坏状况，如果所有数据集中到同一链表中，那么咱们查找起来就像在查找一个程序表一样。
为了解决这个问题，咱们在链表过长时，优化成为红黑数，个别当链表长度超过8时，使其变成红黑数，红黑数能够了解为二叉搜寻树的一种。反之当长度小于6时，将红黑数变为链表。
HashMap存储键值对
hashMap存储键值对通过Entry类，用Entry数组存储键值对，Entry类外面有四个属性：hash、K、V、next，别离存储哈希值、键对象、值对象、下一个Entry对象援用。
Entry源码
Entry对象结构图
Entry存储结构图。
通过对key对象进行hashCode(),获取hash值，而后与运算获取存储地位。
ConcurrentHashMap
ConcurrentHashMap 和 HashMap 思路是差不多的，然而因为它反对并发操作，所以要简单一些。