转载

面试高频问题：HashMap实现原理

今天给同学们讲讲一个面试经常遇到的高频问题，HashMap实现原理，希望在金三银四的季节对同学们有帮助。

HashMap结构图目录

一、唠叨

二、解析思路

三、get方法

四、put方法

##五、resize方法

一、唠叨

认真阅读了下HashMap的实现方式，也参考了网上别人的一些解析，个人觉得还是有些东西想说。网上有的文章名字为HashMap源码解析，实际上就是给它里面的一些方法加上一些注释而已，有不少都是这样的。我自己看源码的时候，发现不是别人不想解析，而是它的实现真的需要亲自研读，多理顺几遍才知道怎么回事。我在这里解析的文字描述也较多，不管谁的解析，自己也都要看一下JDK源码的具体实现，我们仅提供参考而已。

##二、解析思路源码不太方便看，先说明一下我的阅读思路。 1.把常用的几个方法拷贝到文本编辑器里面。 2.HashMap中不同的时候会有不同的流程，梳理方法中的逻辑流程。就像采用极端法，采用特殊的数据，然后查看方法执行语句。未执行的语句暂时不考虑。 3.注释源码...我觉得HashMap的实现方式不够好，关键的几个方法里面包含的情况太多了，阅读起来是有难度的，而写程序的目的之一不就是让其他开发者阅读吗？一个方法内部做了太多的事情，违反了代码整洁的规则，一个函数做要尽量少的事情。解析之前稍微介绍了一些HashMap的特性，HashMap初探。（ www.jianshu.com/p/be9ffb76d…

##三、get方法先挑最简单的说

1 先从数组下标，找到对应的Node2. 2 如果Node里的第一个节点命中，直接返回 3 如果有冲突，则通过key.equals(k)去查找对应的entry 4 若为树，则在树中通过key.equals(k)查找，O(logn)； 5 若为链表，则在链表中通过key.equals(k)查找，O(n)。put方法这个中间涉及的逻辑多一些，方法需要分不同的步骤看。

##四、put方法这个中间涉及的逻辑多一些，方法需要分不同的步骤看。思路： 1对key的hashCode()做hash，然后再计算index; 2如果没碰撞直接放到bucket里； 3如果碰撞了，以链表的形式存在buckets后； 4如果节点已经存在就替换old 5value(保证key的唯一性) 6如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树； 7如果Node的容量满了(超过load factor*current capacity)，就要resize。