来吧，说到HashMap，想必各位java开发者应该或多或少的都使用过吧，只停留在用，就没想过它的底层是怎么实现的吗？当你真正去开始了解他的底层实现的时候，你会发现，真的是设计的好巧妙呀，小编也是突发奇想，分享下自己的理解吧，如果有不对的，欢迎大家联系小编指正修改，谢谢大家。
说到HashMap，他的jdk1.7和1.8的底层实现是发生了变化的，首先我们看看1.7的吧，首先我们要明白两个概念，数组（采用一段连续的存储单元来存储数据）和链表（可以不连续，存储单元可能包含前后节点数据的地址，有单向和多向的区别）是什么，不过多展开了，自己去了解下吧。
1.7的HashMap底层结构是，数组加链表的形式，咱们一起来看看为啥是这种形式的吧，我们存一个key value的数据到map的时候，第一步会把key通过hash函数（我擦，写文章好难啊，每一句话都要解释下，hash函数是什么以及算法在后面有段落介绍，先让我把主要原理一次说完），算出一个数组的下标值，如果这个数组的这个下标里没数据，就把刚才的key value的数据存到这个数组下标这里如图：
细心的小伙伴已经发现问题了呗，如果hash函数算出的结果一样怎么办，你这数组存不下呀，对的，这个现象叫hash冲突，所以链表就来了，每一个数组下面存的都是一个链表，如果发生冲突，就依次往链表里一个一个的存，这就是1.7的HashMap的底层实现原理。
存的时候，因为HashMap不允许key重复，会涉及到key的比较，如果key是我们常用的，String，Integer这些，他们都是已经重写过equals方法了，如果key是自定义的类，就必须重写equals和hashCode函数，为啥要重写俩，是因为：1、如果两个对象相同（即用equals比较返回true），那么它们的hashCode值一定要相同；2、如果两个对象的hashCode相同，它们并不一定相同(即用equals比较返回false)。
每一个entry就是一个key value的数据，实际通过key取数据的时候，步骤是这样的，先去算key的hash函数算出所在的位置，然后拿着key去这个链表里一个一个的用equals方法比，相同的时候把value取出来结束。
我们再来看看1.8的时候，HashMap底层结构发生了什么变化，最大的区别在于引入了红黑树（又来一个需要解释的，自己去查吧这个纯数据结构的名词），整体的结构变成了下图这个样子：
先说结论吧，当链表长度大于8并且数组长度大于64时，会把链表转成红黑树，为啥要引入红黑树，主要是为了查找的时候查的快，想过一个问题没，如果链表的长度足够的长（其实是小概率事件，这里要提到一个概率论中的泊松分布，因为链表长度大于等于8时转成红黑树正是遵循泊松分布，概率已经很小了），红黑树是平均查到的次数是log(n)，长度为8的时候，平均查找长度为3，链表长的话，每次查找一个元素都要花很多次遍历很多次才能查到，链表长度为8的时候平均查找长度是几呢？咱们不妨推理一下
这个图片说的明白不，理解不了最后公式的话自己代入一个数算算，比如n=100,1加到100是5050，除以100等于50.5，是不是等于（100+1）除以2，所以，如果链表长度为8时（n+1）/2=4.5次，当n足够大时，平均查找次数约等于n/2=8/2=4,链表查询的次数4已经高于红黑树3了。
明白了吧，又有朋友看出问题了，为什么不是6（6/2=3和log(6)约等于3）的时候就转红黑树，因为吧，当链表转红黑树的时候是需要花费很多时间的，如果次数差不多的情况下，用链表可以节省转换红黑树的时间，那为什么不是7呢？还有一种情况，链表的数据发生了删除和新增，如果是7，频繁的发生链表和红黑树的转换也是不可取的，所以7可以当成一个缓冲区，避免在查找性能差不多的情况下，发生太多的链表红黑树的转换浪费时间，所以8的时候是最合适的。
Hash函数算法：这个就是对key进行的计算的函数，说到这个就必须提到HashMap的初始容量16，会自动扩容，当元素个数超过容量的0.75时就会进行扩容，每次扩容两倍，也就是说每次它的容量都会是2的次幂，为什么这么搞呢，其实是因为Hash函数采取了位运算的方式如下：
公式：index = HashCode（Key） & （Length - 1）其中Length是HashMap的长度，假设我们的key叫fym
- 计算fym的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001
- 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111
- 把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。
可以说，Hash函数算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。好了，问题来了，为什么用16作为初始容量，为什么不是10，咱们用10来看看结果是啥样子的Length - 1=9 二进制是1001与上面的结果后四位1001进行与运算 结果还是1001，在换个hashCode1011 和1111结果同样是1001，意味着什么，看明白了吗，意味着很多key的hash函数最后的计算结果都是同一个数组下标，这不就是hash冲突吗。而且有些下标永远不会出现，比如0111无论谁和9的二进制1001与都不会出现0111，这就导致了数组有些空间的浪费哦，再回看为什么每次它的容量都会是2的次幂，因为2次幂的Length - 1都是一堆111111111，可以根据hashCode保证均匀分布，减少hash冲突和数组个别空闲的问题。
HashMap的扩容步骤：创建一个新的Entry空数组，长度是原数组的2倍
遍历原Entry数组，把所有的Entry重新Hash到新数组。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。当原数组长度为8时，Hash运算是和111B做与运算；新数组长度为16，Hash运算是和1111B做与运算。Hash结果显然不同。
说到了扩容，就不得不提，HashMap的线程安全问题，HashMap是非线程安全的，假设一个HashMap已经到了Resize（包含扩容和ReHash两个步骤）的临界点。此时有两个线程A和B，在同一时刻对HashMap进行Put操作，ReHash在并发的情况下可能会形成链表环，此时问题还没有直接产生，当调用Get查找一个不存在的Key，而这个Key的Hash结果恰好等于链表环所在的位置的时候，由于位置有环形链表，所以程序将会进入死循环。所以他是非线程安全的，线程安全HashTable它的方法是同步的，效率很低，现在我们大多用ConcurrentHashMap（下回具体介绍），最后在补充几一点吧，在HashMap中，null可以作为键，这样的键只能有一个；在HashTable中，无论键key还是值value都不能为null 。
最后，大家想继续了解相关知识的，可以继续关注公众号，不定时推送。分享了这么牛逼的知识，还不请小编喝个水吗，哈哈哈，欢迎土豪直接赏赞，谢谢，您的支持就是小编最大的动力。
