Java面试题：说一下 HashMap 的实现原理？

HashMap 是基于哈希表的 Map 接口的非同步（非线程安全）实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。该类不保证映射的顺序，特别是它不保证该顺序恒久不变。例如：

Map<String,String> map = new HashMap<>();
map.put("key1", null);
map.put(null, "value2");
System.out.println(map);

输出如下：

{key1=null, null=value2}

HashMap 数据结构

从数据结构的角度来看，HashMap是：数组+链表+红黑树（JDK1.8增加了红黑树部分）的数据结构组成，部分源码如下：

// Node 数组
transient Node<K,V>[] table;

// 链表
static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   Node<K,V> next; // 指向下一个节点
}

// 红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
   TreeNode<K,V> parent;  // red-black tree links
   TreeNode<K,V> left;
   TreeNode<K,V> right;
   TreeNode<K,V> prev;    // needed to unlink next upon deletion
   boolean red;
}

注意，除了上面核心数据结构外，还有一下核心信息：

// 数组默认初始容量：16，2 的 4 次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量，2 的 30 次方，大小为：1,073,741,824
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

装载因子用来衡量HashMap满的程度，表示当map集合中存储的数据达到当前数组大小的75%则需要进行扩容

// 链表转红黑树边界
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转离链表边界
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希桶数组
transient Node<K,V>[] table;
// 实际存储的元素个数
transient int size;

当map里面的数据大于这个threshold就会进行扩容

int threshold   阈值 = table.length * loadFactor

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

面试题广告位

当我们往Hashmap中put元素时,首先根据key的hashcode重新计算hash值,根绝hash值得到这个元素在数组中的位置(下标),如果该数组在该位置上已经存放了其他元素,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放入链尾.如果数组中该位置没有元素,就直接将该元素放到数组的该位置上。

需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
   Node<K,V>[] tab; Node<K,V> p; int n, i;

   // 判断是否进行扩容
   if ((tab = table) == null || (n = tab.length) == 0)
       // 扩容操作
       n = (tab = resize()).length;

   // (n - 1) & hash 等于 hash % (n - 1)，用于计算桶的位置
   // 如果计算出来的桶的位置为 null，则创建新的节点
   if ((p = tab[i = (n - 1) & hash]) == null)
       tab[i] = newNode(hash, key, value, null);
   else {
       // 此时，p 为计算出来桶所在的节点
       Node<K,V> e; K k;

       // 如果带保存的值的 hash 和 key 与计算得出的 p 节点相等
       if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
           e = p;
       // 如果计算得到的节点是红黑树，则直接添加节点
       else if (p instanceof TreeNode)
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
       else {
           for (int binCount = 0; ; ++binCount) {
               // 如果计算得到的 p 节点和插入的 key 不等，并且 p 的下一个节点为 null，则新创建节点
               // 将 e 指向 p 节点的下一个节点
               if ((e = p.next) == null) {
                   p.next = newNode(hash, key, value, null);
                   // 判断新增节点后，链表是否满足转化为红黑树的条件
                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                       treeifyBin(tab, hash);
                   break;
               }

               // 判断 p 节点的下一个节点是否等于带插入的节点，如果等于，则不进行操作
               if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                   break;
               
               // 让 p 指向自己的下一个节点，向后遍历
               p = e;
           }
       }

       // 如果 key 已经存在
       if (e != null) { // existing mapping for key
           V oldValue = e.value;

           // onlyIfAbsent 用来控制当 key 存在时，是否修改它的值，true-不修改，false-修改
           if (!onlyIfAbsent || oldValue == null)
               e.value = value;

           // 触发回调
           afterNodeAccess(e);
           return oldValue;
       }
   }

   // 用来记录 table 数组中已经使用了多少个元素了
   ++modCount;

   // 判断是否需要扩容操作
   if (++size > threshold)
       resize();
   
   // 触发回调
   afterNodeInsertion(evict);

   return null;
}