码大牛，成长于传智播客和黑马程序员的专家型顾问。欢迎加QQ交流，定期推送福利与资源，仅限高校计算机教师。
内容来自：掘金
HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap，都知道哪里要用HashMap。本文我们来分析一下HashMap的源码实现。
目录
基础：定义、容量因子、hash冲突
get方法是如何实现的？put方法是如何实现的？hash的实现resize方法是如何实现的？
一、基础：定义、容量因子、hash冲突在正式进入HashMap的源码分析之前，我们有必要先了解一下几个关键的概念。首先我们先来看一下官方文档对于HashMap的定义：HashtablebasedimplementationoftheMapinterface.Thisimplementationprovidesalloftheoptionalmapoperations,andpermitsnullvaluesandthenullkey.(TheHashMapclassisroughlyequivalenttoHashtable,exceptthatitisunsynchronizedandpermitsnulls.)Thisclassmakesnoguaranteesastotheorderofthemap;inparticular,itdoesnotguaranteethattheorderwillremainconstantovertime.可以看到HashMap是基于Map接口来实现的，并且允许空值和空键，而且HashMap不保正有序性，特别强调的是元素的顺序会随着HashMap的扩展（增删）而变化，这一点在下面我们也会有所强调。
HashMap设置LoadFactor的目的就是当capacity*laodFactor大于thredhold(阀值)的时候，HashMap就会就行resize来将HashMap的大小扩大两倍，LoadFactor(容量因子)的大小默认是0.75f。这一点如果现在不是很理解也没有关系，在下面会提及到。
另外一个重要的概念就是在jdk1.8中，HashMap做了进一步的优化，当产生hash冲突的时候，以前都是完全通过链表来解决的，现在新增加了一个staticfinalintTREEIFY_THRESHOLD=8;，当链表的长度达到8位的时候，为了提高效率，链表会扩展成红黑树。这样在下面的get操作的时候算法效率就可以由O(n)提高到O(logn)。
二、get实现原理getNode的实现比较简单，实现步骤如下：
实现步骤1.首先通过first=tab[(n-1)hash]找到第一个匹配hash值的节点，如果没有匹配成功就返回null。
.然后判断找到的第一个节点是否等于我们需要查找的key，如果是的就直接返回，否则就代表产生了碰撞，转移到红黑树或者链表中去查找。
3.如果这个节点是红黑树的子节点，转到红黑树中查找，即((TreeNodeK,V)first).getTreeNode(hash,key)。
4.否则就在链表中查找，如果没有找到就返回null。
三、put实现原理put方法的实现相比较get就稍微复杂一些了，主要分为以下几个步骤：
实现步骤1.第一个if语句：如果tab为空就创建。
.第二个if语句：通过计算hash如果没有发生碰撞就直接创建一个节点。
3.重点就是分析else语句了。
分析else语句前，建议大家先从整体看一下源码中的的两个条件分支，写的非常清晰，甚至和上面的get操作的思路有些相似，分为几个步骤：
实现步骤1.首先判断节点是否存在，如果存在直接给e赋值。
.判断节点是否是红黑树的节点，如果是的从红黑树中查找，并赋值给e。
3.否则从链表中查找，并赋值给e注意循环中加了一个检查条件if(binCount=TREEIFY_THRESHOLD-1)，TREEIFY_THRESHOLD默认是8，就是如果达到了这个阀值，就将链表扩展为红黑树。
4.最后通过检查e来看是否已经存在相应的key，如果存在就更新value的值，并且返回。
5.否则跳出else循环之后，通过修改++modCount;记录修改次数，并且判断现在hashmap是否需要resize。
p.s:afterNodeAccess(e);和afterNodeInsertion(evict);是留给HashMap的子类LinkedHashMap去实现的。
四、hash的实现
hash的实现虽然比较简单，就是高16位不变，低16位和高16位做了一个异或。但是还比较有技巧的，比如做异或，为什么要做异或呢？而不是直接(n-1)hash，因为这样很容易发生碰撞，比如假设n等于16，那么散列的其实只有低四位。
五、resize的实现resize的实现其实也很巧妙，我们来具体看一看。当超过阀值threshold的时候，就会resize，因为hashmap的长度永远都是的幂，而resize就是将长度扩展为原来的两倍，所以节点的位置可能会继续保持不变，也有可能会在原来的位置上移动两次幂。比如我们需要从16位扩展到3位，会发生如下变化：
对于hash1来说因为第5位是0，所以会保持原位置不变，但是对于hash来说因为第五个位置是1，所以相当于在原位置的基础上加上oldCapacity(16)。
resize的实现思路上面我们已经分析出来了，源代码我就不贴了，代码大家具体到jdk下面去看吧！
阅读更多
让学生爽呆的大学教育，应该是这样！
上大学就可以好好放松了？看看清华的同学在四年大学干什么吧！
教IT的赵老师说：参加完传智的暑期培训，有种顿悟的感觉！
教学好助手(boxuegu)