Java的HashMap底层实现原理（jdk1.8）

标记：vivo 提前批大数据开发岗问到HashMap底层的实现原理，回答的很烂，所以作此知识点的补充，以后在遇到java 的这些高频知识点，争取能够流利的回答出来。
在jdk1.6 1.7中，HashMap 采用位 |桶（容量）+链表实现，即使采用了链表来解决冲突，同一Hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过 key 值查询的效率会很低。而在 jdk 1.8 中 HashMap 采用位桶 + 链表 + 红黑树 实现，当链表长度超过阈值8 时，将链表转化成红黑树，这样就大大减少了查找时间。

1. HashMap 的工作原理

HashMap 基于hashing 原理，通过get() ,put() 方法储存和获取对象，当我们将键值对传递给 put()
方法时，它调用键对象的Hash() 方法来计算key的 hash值 ，hash = key.hashcode() ^ (key.hashcode()>>16), index = hash &(n - 1) ,然后找到 桶
位置来存储键值对对象《《《注意桶位置就是数组的某个位置，这个位置存储的是键值对信息，不只是键，要不然后续查找时，要逐一遍历链表，导致查询效率低下》》》。当获取对象时，通过键对象的 equals（） 方法找到正确的键值对，然后返回值对象。HashMap 使用链表解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点当中，HashMap 在每个链表节点中储存键值对对象。

所以当不同的键值对对象的 Hashcode 相同时，他们就会存储在同一个 桶（Bucket）位置的链表中。键对象的 equals()
方法用来找到键值对。

2.HashMap 的 hash 算法及计算 我们首先要知道 Java 中所有的对象都有 hashcode （使用key 的），如果使用 object 对象 get hashcode 的话会得到 int 类型的值，我们 HashMap 中主要是用它的 key 计算它的 hash值 。Hash 值 = （hashcode） ^ (hashcode >>> 16)
hash 值等于 它本身的hashcode 与 它本身的 hashcode 向右位移 16 位做异或。 这样做的目的就是算出来的值足够随机， 因为进行 hash 计算的时候足够分散，以便于计算数组下标的时候算出的值也足够分散。 HashMap 的数组默认大小位16（在不做修改的情况下），那么数组下标的是如何计算出的呢，如下：
==》 数组下标 = hash & (16-1) 或则 hash % 16，即对hash 计算得到的 hash 值对16 求余，得到一个 1 ~ 15 中的一个数，实际操作 将 hash 值与 15 进行与运算，这样速度会更快。 3.HashMap 存取机制

可参考源码分析
1. HashMap 的getValue()

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab;//Entry对象数组 Node<K,V> first,e; //在tab数组中经过散列的第一个位置 int n; K k; /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/ //也就是说在一条链上的hash值相同的 if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { /*检查第一个Node是不是要找的Node*/ if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同 return first; /*检查first后面的node*/ if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); /*遍历后面的链表，找到key值和hash值都相同的Node*/ do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }

get(key)方法获取key的hash 值，计算 hash &( n-1) 得到在链表数组中位置 first = tab[hash & (n - 1)],先判断当前数组中处理hash冲突的方式为链表还是红黑树，是红黑树就去红黑树中取出对应的节点。如果不是 ，就比较first 的 key 是否与参数 key 相等，不等就继续遍历后面的数组链表元素找到相同的 key 值后，会调用 key.equals() 找到链表中正确的节点，返回对应的 value 即可。

2. HashMap 的put()
下面简单说下添加键值对put(key,value)的过程：
1，判断键值对数组tab[]是否为空或为null，否则以默认大小resize()；
2，根据键值key计算hash值得到插入的数组索引i，如果tab[i]==null，直接新建节点添加，否则转入3
3，判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理

4.hash 冲突 冲突产生的原因就是不同的键值对 的键对象计算出的数组下标位置相同，就会产生 Hash 冲突。

Hash 冲突产生单线链表，当链表的长度达到一定值后，效率就会变的非常低，在 Jdk 1.8 之后引入了红黑树，也就是当单行链表达到一定长度后就会变成一个红黑树，具体操作是扩容之后，将原来的链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率。

HashMap 的底层扩容原理

当数组达到一定长度后，比如 HashMap 的默认数组长度是16，当达到触发条件，即是
数组长度达到了 本身长度 * 0.75(负载因子默认为 0.75)，也就是 16 * 0.75 = 12 时，就会发生扩容。
扩容原理
数组长度变为原来的 2 倍

Jdk 1.8 使用红黑树的改进

在 jdk 1.7中，HashMap 处理“碰撞”的时候，都是采用链表来存储，所以当碰撞的节点很多时，时间复杂度时 O（n）,比如极端情况下，所有的键值对对象的键值都指向数组的同一个位置，那么 hashmap 就会变成单独一个链表。
在 jdk 1.8时， HashMap 处理碰撞时加入了 红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当一个位置存储的结点过多时（ > 8 ），采用红黑树（特点时查询时间时 0（n）存储（默认阈值是 8 ,当存储结点大于 8 个时，将链表转换成红黑树存储））

HashMap 的特点： 快速查找快速存储可伸缩（扩容） HashMap 的时间查找、新增元素的时间复杂度

从时间复杂度的角度考面试者对 HashMap 的了解深度
先说元素的查询
在理想的情况下，查找的时间复杂度时 O（1）,由于 HashMap 底层使用的数组的结构，所以key 的查找在 O(1)时间内完成。

HashMap 可以分成两部分来看，hash 和 map.map 实现了键值对的存储，hash 保证了查找复杂是 O（1），因为 key 在查找对应数组的位置的时候，使用 hash = (hash = key.hashcode()) ^(hash >> 16) ,index = hash & (n-1) ，所以可以在 O（1）的时间内找到 key 所在的桶。
但是查询 O(1) 是理想的情况，所谓理想的情况就是，每个桶中存的 entryset 中只有一个值，那么查询的理想时间是 O（1）,如果桶中存放的是链表，那么在找到 key 对应的桶之后，还要调用 equals（）方法，遍历链表，时间复杂度是 O(n)，如果桶中存的是红黑树，那么时间复杂度就是 O（logn）.
添加元素时
先看 put 操作的流程：
第一步： key.hashcode(),时间复杂度是 O（1）
第二步：找到对应桶之后，判断桶里是否有元素，如果没有，直接 new 一个 entry 节点插到数组中。时间复杂度是 O（1）
第三步：如果桶里有元素，并且元素个数小于 6，则调用 equals() 方法，比较是否存在相同名字的 key ,不存在则 new 一个entry 放到链表尾部，时间复杂度 O(n)
第四步：如果桶里有元素，并且元素个数大于6，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入都链表尾部。时间复杂度O(1)+O(logn)=O(logn)。红黑树查询的时间复杂度是logn。

通过上面的分析，我们可以得出结论，HashMap新增元素的时间复杂度是不固定的，可能的值有O(1)、O(logn)、O(n)。

HashMap 结构 1.7、1.8 有哪些区别