原文公众号名：算法爱好者

面试的时候，问些数据结构与算法方面的知识，我个小菜鸡，考试一考完，全部还给老师了。当初学的时候不理解老师的苦心，现在才逐渐理解到一个好的算法对一个程序优劣的重要性。这之后，会将看到的好的文章中的算法总结一下，加深一下记忆，并且考虑一下在实际当中怎么运用，原文我是在上面的公众号中看到的，不喜欢看我碎碎念的，可以去看看大神的东东。

一、HashMap的概念

HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry.这些键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。注意，这里我经常漏掉的一个理解的关键点是存储键值对，傻一点理解就是将键值对揉成一团，标注成Entry放在一个特殊的数组当中（为什么叫特殊的数组）。

HashMap数组每一个元素的初始值都是Null，如下图所示

对于HashMap,我们最常用的是两个方法：Get和Put

二、put和set方法的原理

    1、put方法的原理

当我们使用put插入一个元素时，比方说插入一个Key为“apple”的元素，这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）,hashMap.put("apple", 0)(这个写法的语法是put(K key , V value) )。用函数表示就是:index=Hash("apple"),假设最后计算出来的index是2，那么结果如下：

但是，HashMap的长度是有限制的，当插入的Entry越来越多时，不可避免会出现index冲突，就像下面这样：

出现冲突可以使用链表解决，如果忘记链表了，可以看看python实现链表。HashMap的数组中存的那个Entry，其实链表的头节点，后面被接到这个位置的元素，只需要前面的元素的next指向该元素就可以了,就像下面这样

注意，新插入的元素并不是插到链表的最后，而是插到最前面，后面会解释

2、Get方法的原理

当使用Get方法根据Key来查找Value的时候，会先把输入的Key做一次Hash映射，得到对应的index,index=Hash("apple"),但是上面提到会有Hash冲突，就是可能会匹配到很多个Entry，这时候就需要顺着链表的头节点一个一个往下找。假设我们要查找的Key是"apple",如下图，

第一步，查看的头节点Entry6，Entry6的Key是banana,不是我们要的结果

第二步，查看的是Next节点Entry1,Entry1的Key是apple,正是我们要找的结果

之所以把Entry6放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大

三、关于HashMap的初始长度

HashMap默认初始。长度是16，并且每次自动扩展或是手动初始化时，长度必须是2的幂。上面有提到计算Key到HashMap数组对一个位置，需要用到Hash函数（index = Hash("code")）。我们可以通过利用Key的HashCode值来做某种运算，从而得到一个尽量均匀分布的Hash函数。为了实现高效的Hash算法，HashMap的发明者采用了位运算的方式。公式如下，（Length是HashMap的长度）

index = HashCode(Key)&(Length-1)