HashMap(一) 基础原理

这一个最常用的数据结构 可以为无数的工作提供能量。

众所周知，HashMap是一个用于存储K-V键值对的集合，每个键值对称之为Entry。这些键值对分散存储在一个数组当中，这个数组就是HashMap的主干。

HashMap数组的每一个元素的初始值都是NULL。

存取数据

对于HashMap 最常用的就是get和put。

先说说put的原理

比如调用map.put("hello", 1); 此操作会插入一个key为"hello"的元素。这时候会利用一个哈希函数来确定插入的位置(index)。

假设最终计算出来的index是1，那么结果如下：

因为Hash长度是有限的，插入更多的Entry之后再完美的哈希函数也不可避免出现index冲突的情况。
比如突然出现一个Entry5，index 也是1 ，这时候就可以使用链表来解决了。
HashMap数组的每一个元素不只是一个Entry对象，也是一个链表头节点，每个Entry对象通过Next指针都可以指向下一个Entry节点。当新来的Entry映射到冲突的数组位置时只要插入到对应的链表中即可。
需要注意的是，新来的Entry节点插入链表时使用的都是“头插法”。如图所示：

Get的原理

上面刚刚把数据塞了进去，现在轮到取出来了。
比如执行map.get("hello");此操作首先会将输入的key 做一次hash映射 得到对应的index。
但是由于刚刚所说的Hash冲突，同一个位置可能会匹配到N个Entry，这时候会顺着链表头依次往下找。假设当前状态如图所示：

第一步：我们得到hash的index为1.
第二步：得到index为1的头节点是Entry5，找到它的Key是ohayou，明显不是想要的结果。
第三步：查看Next节点Entry1，key相符合返回结果。

1. 之所以使用头插法，是因为HashMap的发明者认为后插入的数据被查找的可能性更大...