Java：java开发面试必问之HashMap 飞利浦·斯塔克

文章图片

文章图片

文章图片

文章图片

文章图片
前言
之前面试时，被面试官追着问了hashMap的源码，大热天的被问的气抖冷，我们java程序员什么时候才能站起来？
为了站着把钱挣了，我回来各种百度，我觉得我又行了，现在上成果。
hashMap简介
在JDK1.8之前， hashMap底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过依次查找的效率较低。而JDK1.8中， hashMap存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树(二叉树) ，这样大大减少了查找时间。
结构如下：
hashMap源码分析

构造方法

HashMap()：创建一个初始容量 (16) 和加载因子 (0.75) 的空 HashMap 。
HashMap(int initialCapacity)：创建初始容量和默认加载因子 (0.75) 的空 HashMap 。
HashMap(int initialCapacity float loadFactor)：构造指定初始容量和加载因子的空 HashMap 。
容量好理解，加载因子是个什么东西？
简单说就是当元素个数超过加载因子*最大容量时， hashMap会扩容至两倍，加载因子过小，链表过于稀疏，浪费空间，过大虽然空间利用率起来了，但会导致查找效率变低，默认为0.75 ，一般不需要修改，

hashMap的数据结构

从这里可以发现，创建hashMap时会初始化一个元素为Entry的数组table ，从这也可看出hashMap底层实质上就是数组，只不过数组的元素为Entry ，参数initialCapacity即为table数组长度。
Entry包含了键值对（key-value），下个节点next ， hash值
在1.8中元素为node ，但只是换了个名字，还是一样的东西

【Java：java开发面试必问之HashMap】Put实现

1.7中会先判断key是否为null ，为null ，则直接调用putForNullKey方法。若不为空则先计算key的hash值，再根据hash值搜索在数组中的索引位置，若存在元素，比较key是否相同，相同则覆盖，不同则保存在链表头部，若没有元素，直接插入
1.8中put时则会先获取hash ，当key为null时会赋值0 ，当产生的链表长度过长时，会影响查询效率， 1.8中做了优化，如果table同一索引位置元素超过8个则转换为红黑树即源码中的treeNode ，低于6个会转成链表

Get则相对较简单，就是先根据key的hash值查找数组中node对象，再根据key去node中查找结果， 1.7与1.8并无多大差别，只不过1.8中有树的存在， get时要判断一下根据数据结构来获取结果。