HashMap底层实现原理及面试题

1. 常见的数据结构有三种结构

• 数组结构
• 链表结构
• 哈希表结构

1.1 各自数据结构的特点

• 数组结构： 存储区间连续、内存占用严重、空间复杂度大
  • 优点：随机读取和修改效率高，原因是数组是连续的（随机访问性强，查找速度快）
  • 缺点：插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中都要往后移动，且大小固定不易动态扩展。
• 链表结构：存储区间离散、占用内存宽松、空间复杂度小
  • 优点：插入删除速度快，内存利用率高，没有固定大小，扩展灵活
  • 缺点：不能随机查找，每次都是从第一个开始遍历（查询效率低）
• 哈希表结构：结合数组结构和链表结构的优点，从而实现了查询和修改效率高，插入和删除效率也高的一种数据结构

2. HashMap

2.1 概述

HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用NULL建和NULL值，因为key允许重复，因此只能有一个建为null，另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的。

2.2 底层结构

HashMap底层采用哈希表结构（JDK1.8之前为数组+链表、JDK1.8之后为数组+链表+红黑树）实现，结合了数组和链表的优点：
数组优点： 通过数组下标可以快速实现对数组元素的访问，效率极高；
链表优点： 插入或删除数据不需要移动元素，只需修改节点引用，效率极高。

HashMap内部使用数组存储数据，数组中的每个元素类型为Node<K,V>：

//Node包含了四个字段：hash、key、value、next，其中next表示链表的下一个节点。
static class Node<K,V> implements Map.Entry<K,V> {    final int hash;    final K key;    V value;Node<k,V> next; //链表的下一个节点Node(int hash, K key, V value, Node<K,V> next) {        this.hash = hash;        this.key = key;        this.value = value;        this.next = next;   
}public final K getKey()       { return key; }    
public final V getValue()     { return value; }   
public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);   
}
public final boolean equals(Object o) {        if (o == this)   return true;        if (o instanceof Map.Entry) {            Map.Entry<?,?> e = (Map.Entry<?,?>)o;            if (Objects.equals(key, e.getKey()) &&               Objects.equals(value, e.getValue()))                return true;      }return false;}
}

2.2.1 HashMa实现原理：

2.2.1.1 map.put(k,v)实现原理

（1）首先将k,v封装到Node对象当中（节点）。
（2）然后它的底层会调用k的hashCode()方法得出hash值。
（3）通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。

• put方法源码如下：

//put方法，会先调用一个hash()方法，得到当前key的一个hash值，
//用于确定当前key应该存放在数组的哪个下标位置
//这里的 hash方法，我们姑且先认为是key.hashCode()，其实不是的，一会儿细讲
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}//把hash值和当前的key，value传入进来
//这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false
//evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一个空实现，因此不用关注这个参数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//判断table是否为空，如果空的话，会先调用resize扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，//若没有，则把key、value包装成Node节点，直接添加到此位置。// i = (n - 1) & hash 是计算下标位置的，为什么这样算，后边讲if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else { //如果当前位置已经有元素了，分为三种情况。Node<K,V> e; K k;//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//2.如果当前是红黑树结构，则把它加入到红黑树 else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//如果头结点的下一个节点为空，则插入新节点p.next = newNode(hash, key, value, null);//如果在插入的过程中，链表长度超过了8，则转化为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//插入成功之后，跳出循环，跳转到①处break;}//若在链表中找到了相同key的话，直接退出循环，跳转到①处if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//①//说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值if (e != null) { // existing mapping for keyV oldValue = e.value;//用新值替换旧值，并返回旧值。if (!onlyIfAbsent || oldValue == null)e.value = value;//看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，//只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能// Callbacks to allow LinkedHashMap post-actions//void afterNodeAccess(Node<K,V> p) { }afterNodeAccess(e);return oldValue;}}//fail-fast机制++modCount;//如果当前数组中的元素个数超过阈值，则扩容if (++size > threshold)resize();//同样的空实现afterNodeInsertion(evict);return null;
}

• put方法通过hash函数计算key对应的哈希值，hash函数源码如下：

static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2.2.1.2 map.get(k)实现原理

(1)先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
(2)通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。

• get操作源码：

 public V get(Object key) {Node<K,V> e;//如果节点为空，则返回null，否则返回节点的value。这也说明，hashMap是支持value为null的。//因此，我们就明白了，为什么hashMap支持Key和value都为nullreturn (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//首先要确保数组不能为空，然后取到当前hash值计算出来的下标位置的第一个元素if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//若hash值和key都相等，则说明我们要找的就是第一个元素，直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//如果不是的话，就遍历当前链表（或红黑树）if ((e = first.next) != null) {//如果是红黑树结构，则找到当前key所在的节点位置if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);//如果是普通链表，则向后遍历查找，直到找到或者遍历到链表末尾为止。do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}//否则，说明没有找到，返回nullreturn null;
}

2.2.1.3 resize源码

通过put源码分析我们知道，数组的初始化和扩容都是通过调用resize方法完成的：

final Node<K,V>[] resize() {//旧数组Node<K,V>[] oldTab = table;//旧数组的容量int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到。int oldThr = threshold;//初始化新数组的容量和阈值，分三种情况讨论。int newCap, newThr = 0;//1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0。//为什么这样说呢，之前我在 tableSizeFor 卖了个关子，需要注意的是，它返回的值是赋给了 threshold 而不是 capacity。//我们在这之前，压根就没有在任何地方看到过，它给 capacity 赋初始值。if (oldCap > 0) {//容量达到了最大值if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//新数组的容量和阈值都扩大原来的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//2.到这里，说明 oldCap <= 0，并且 oldThr(threshold) > 0，这就是 map 初始化的时候，第一次调用 resize的情况//而 oldThr的值等于 threshold，此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例)。//因此，需要把 oldThr 的值，也就是 threshold ，赋值给新数组的容量 newCap，以保证数组的容量是2的n次幂。//所以我们可以得出结论，当map第一次 put 元素的时候，就会走到这个分支，把数组的容量设置为正确的值（2的n次幂)//但是，此时 threshold 的值也是2的n次幂，这不对啊，它应该是数组的容量乘以加载因子才对。别着急，这个会在③处理。else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//3.到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的，//于是，数组的容量和阈值都取默认值就可以了，即 16 和 12。else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//③ 这里就是处理第2种情况，因为只有这种情况 newThr 才为0，//因此计算 newThr（用 newCap即16 乘以加载因子 0.75，得到 12） ，并把它赋值给 thresholdif (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//赋予 threshold 正确的值，表示数组下次需要扩容的阈值（此时就把原来的 16 修正为了 12）。threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})//我们可以发现，在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候，才会把数组创建出来。这是为了延迟加载，提高效率。Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//如果原来的数组不为空，那么我们就需要把原来数组中的元素重新分配到新的数组中//如果是第2种情况，由于是第一次调用resize，此时数组肯定是空的，因此也就不需要重新分配元素。if (oldTab != null) {//遍历旧数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//取到当前下标的第一个元素，如果存在，则分三种情况重新分配位置if ((e = oldTab[j]) != null) {oldTab[j] = null;//1.如果当前元素的下一个元素为空，则说明此处只有一个元素//则直接用它的hash()值和新数组的容量取模就可以了，得到新的下标位置。if (e.next == null)newTab[e.hash & (newCap - 1)] = e;//2.如果是红黑树结构，则拆分红黑树，必要时有可能退化为链表else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//3.到这里说明，这是一个长度大于 1 的普通链表，则需要计算并//判断当前位置的链表是否需要移动到新的位置else { // preserve order// loHead 和 loTail 分别代表链表旧位置的头尾节点Node<K,V> loHead = null, loTail = null;// hiHead 和 hiTail 分别代表链表移动到新位置的头尾节点Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;//如果当前元素的hash值和oldCap做与运算为0，则原位置不变if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}//否则，需要移动到新的位置else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//原位置不变的一条链表，数组下标不变if (loTail != null) {loTail.next = null;newTab[j] = loHead;}//移动到新位置的一条链表，数组下标为原下标加上旧数组的容量if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

2.2.2 HashMap常用的变量

//默认的初始化容量为16，必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//最大容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;//默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。
//为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。
//若小于0.75如0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，
//若大于0.75如0.8，则会增大hash冲突的概率，影响查询效率。
static final float DEFAULT_LOAD_FACTOR = 0.75f;//刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树
static final int TREEIFY_THRESHOLD = 8;//当红黑树上的元素个数，减少到6个时，就退化为链表
static final int UNTREEIFY_THRESHOLD = 6;//链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。
//这是为了避免，数组扩容和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;//存放所有Node节点的数组
transient Node<K,V>[] table;//存放所有的键值对
transient Set<Map.Entry<K,V>> entrySet;//map中的实际键值对个数，即数组中元素个数
transient int size;//每次结构改变时，都会自增，fail-fast机制，这是一种错误检测机制。
//当迭代集合的时候，如果结构发生改变，则会发生 fail-fast，抛出异常。
transient int modCount;//数组扩容阈值
int threshold;//加载因子
final float loadFactor;					//普通单向链表节点类
static class Node<K,V> implements Map.Entry<K,V> {//key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置final int hash;final K key;V value;//指向单链表的下一个节点Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}
}//转化为红黑树的节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {//当前节点的父节点TreeNode<K,V> parent;  //左孩子节点TreeNode<K,V> left;//右孩子节点TreeNode<K,V> right;//指向前一个节点TreeNode<K,V> prev;    // needed to unlink next upon deletion//当前节点是红色或者黑色的标识boolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}//返回当前节点的根节点final TreeNode<k,v> root() {for (TreeNode<k,v> r = this, p;;) {if ((p = r.parent) == null)return r;r = p;}}
}	

2.2.3 HashMap构造函数

HashMap有四个构造函数可供我们使用：

//默认无参构造，指定一个默认的加载因子
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; 
}//可指定容量的有参构造，但是需要注意当前我们指定的容量并不一定就是实际的容量，下面会说
public HashMap(int initialCapacity) {//同样使用默认加载因子this(initialCapacity, DEFAULT_LOAD_FACTOR);
}//可指定容量和加载因子，但是笔者不建议自己手动指定非0.75的加载因子
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//这里就是把我们指定的容量改为一个大于它的的最小的2次幂值，如传过来的容量是14，则返回16//注意这里，按理说返回的值应该赋值给 capacity，即保证数组容量总是2的n次幂，为什么这里赋值给了 threshold 呢？//先卖个关子，等到 resize 的时候再说this.threshold = tableSizeFor(initialCapacity);
}//可传入一个已有的map
public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}//把传入的map里边的元素都加载到当前map
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {int s = m.size();if (s > 0) {if (table == null) { // pre-sizefloat ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t > threshold)threshold = tableSizeFor(t);}else if (s > threshold)resize();for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();//put方法的具体实现，后边讲putVal(hash(key), key, value, false, evict);}}
}

tableSizeFor()
上边的第三个构造函数中，调用了 tableSizeFor 方法，这个方法是怎么实现的呢？

static final int tableSizeFor(int cap) {int n = cap - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

可以看到这个方法是针对整型数据进行的操作！
int n = cap - 1;
不知道为什么要减去1，实际上这只是针对二的整数幂进行的退位操作

先单独看这段代码：

	假设 n = 5时n |= n >>> 1;0000 01010000 00100000 0111n |= n >>> 2;0000 01110000 00010000 0111n |= n >>> 4;0000 01110000 00000000 0111...最后无符号右移再或等结果都是0000 0111这样就得到了5最高非0位下的最大值即 0000 0111对其加一的结果就是 0000 1000即大于5的最小二的整数幂 8

其实这个算法的思路就是将该数字的最高非0位后面全置为1！其利用了“拷贝”的方式：

	 n=     ;  1000 0000  0000 0000  0000 0000  0000 0000
n |= n >>> 1;  1100 0000  0000 0000  0000 0000  0000 0000  将最高位拷贝到下1位
n |= n >>> 2;  1111 0000  0000 0000  0000 0000  0000 0000  将上述2位拷贝到紧接着的2位
n |= n >>> 4;  1111 1111  0000 0000  0000 0000  0000 0000  将上述4位拷贝到紧接着的4位
n |= n >>> 8;  1111 1111  1111 1111  0000 0000  0000 0000  将上述8位拷贝到紧接着的8位
n |= n >>> 16; 1111 1111  1111 1111  1111 1111  1111 1111  将上述16位拷贝到紧接着的16位

由上面可以看出其通过这五次的计算，最后的结果刚好可以填满32位的空间，也就是一个int类型的空间，这就是为什么必须是int类型，且最多只无符号右移16位！

  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

其中的MAXIMUM_CAPACITY 是HashMap的最大空间为1 << 30，即2^30刚好一个G，所以HashMap大小不是取决于堆内存！

为什么要减一：

 以 n = 8为例0000 1000最后的结果为：0000 1111对其加一得到的是16，显然没有把自身包含进去若减一n = 70000 0111最后的结果为：0000 0111对其加一得到的是8

所以在一开始进行减一的操作是为了防止出现二的整数幂时，没有把自身包含进范围！

2.3 JDK1.8之前存在的问题

JDK1.8之前，HashMap底层实现用的是数组+链表。（JDK1.8以后用数组+链表+红黑树）。

HashMap通过hash方法计算key的哈希码，然后通过（n-1）&hash 公式（n为数组长度,初始化数组默认长度为16），得到key在数组中存放的下标。

当两个key在数组中存在的下标一致时（哈希冲突，哈希碰撞），数据将以链表的方式存储。

在链表中查找数据必须从第一个元素开始一层一层往下找，直到找到为止，时间复杂度为O(N)，所以当链表长度越来越长时，HashMap的效率越来越低。

2.4 HashMap红黑树原理

红黑树除了插入操作慢，其他操作都比链表快，当hash表的单一链表长度超过 8 个的时候，数组长度大于64，链表结构就会转为红黑树结构。当红黑树上的节点数量小于6个，会重新把红黑树变成单向链表数据结构。
为什么要这样设计呢？好处就是避免在最极端的情况下链表变得很长很长，在查询的时候，效率会非常慢。

• 红黑树查询：其访问性能近似于折半查找，时间复杂度 O(logn)；
• 链表查询：这种情况下，需要遍历全部元素才行，时间复杂度 O(n)；

简单的说，红黑树是一种近似平衡的二叉查找树，其主要的优点就是“平衡“，即左右子树高度几乎一致，以此来防止树退化为链表，通过这种方式来保障查找的时间复杂度为 log(n)。

关于红黑树的内容，网上给出的内容非常多，主要有以下几个特性：
1、每个节点要么是红色，要么是黑色，但根节点永远是黑色的；
2、每个红色节点的两个子节点一定都是黑色；
3、红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）；
4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；
5、所有的叶子节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件 3 或条件 4，需要通过调整使得查找树重新满足红黑树的条件。

3. 哈希表(散列)

3.1 什么是哈希表

根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数H(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash)表，函数H(key)为哈希(Hash)函数。

3.2 什么是哈希冲突(面试题)

根据一定的规则放进存放哈希值的数组中，然后下标为1的数组已经有值了，后面根据规则，判定某个数也需要放到下标为1的数组中，这样就导致了只有一个位置两个人都要坐，就引起了冲突。(不同的key值产生的H(key)是一样的)。

3.3 解决哈希冲突的方法(面试题)

(1) 开放地址法

插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。

Hi=(H(key)+di)%m  //开放地址法计算下标公式
Hi：下标(储存的地址)
H(key)：哈希函数(计算哈希值)
di：增量
%：取模
m：哈希表的长度

探查方法如下

① 线性探查

di=1,2,3,…m-1；冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

②二次探查

di=1^2, -1^2, 2^2, -2^2 …k^2, -k^2,(k<=m/2)； 冲突发生时，在表的左右进行跳跃式探测，比较灵活。

③随机探查

di=伪随机数序列；冲突发生时，建立一个伪随机数发生器（如i=(i+p) % m），p是质数(在m范围取得质数)，生成一个伪随机序列，并给定一个随机数做起点，每次加上伪随机数++就行。

为了更好的理解，我们举一个例子

设哈希表长为14，哈希函数为H(key)=key%11。表中现有数据15、38、61和84，其余位置为空，如果用二次探测再散列处理冲突，则49的位置是？使用线性探测法位置是？解：因为H(key)=key%11
所以15的位置 = 15 % 11=4; 38的位置 = 38 % 11=5; 61的位置 = 61 % 11=6; 84的位置 = 84 % 11=7;(证明哈希表4,5,6,7已经有元素)因为计算下标的公式为：Hi=(H(key)+di)mod%m
使用二次探测法
H(1) = (49%11 + 1^1) = 6;冲突      
H(-1) = (49%11 + (-1^2)) = 4;冲突   注意 -1^2 = -1; (-1)^2 = 1;
H(2) = (49%11 + 2^2) = 9;不冲突
二次探测法49的位置就是哈希表的9。使用线性探测
H(1) = (49%11 + 1) = 6;冲突
H(2) = (49%11 + 2) = 7;冲突
H(3) = (49%11 + 3) = 8;不冲突
线性探测法49的位置就是哈希表的8。

(2) 再哈希法

再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

(3) 链地址法

每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。
比如 66和88这两个元素哈希值都是1，这就发生了哈希冲突，采用链地址法，可以把 66和88放在同一个链表中。如下图

(4)建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

4. HashMap

4.1 HashMap的hash()算法(面试)

(1)为什么不是h = key.hashCode()直接返回，而要 h = key.hashCode() ^ (h >>> 16)来计算哈希值呢？

回答：减少哈希冲突

	//源码：计算哈希值的方法 H(key)static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}   //^ (异或运算) 相同的二进制数位上，数字相同，结果为0，不同为1。  举例如下：0 ^ 0 = 00 ^ 1 = 11 ^ 1 = 01 ^ 0 = 1// &(与运算)  相同的二进制数位上，都是1的时候，结果为1，否则为零。 举例如下：0 & 0 = 00 & 1 = 01 & 0 = 01 & 1 = 1

h = key.hashCode() ^ (h >>> 16)意思是先获得key的哈希值h，然后 h 和 h右移十六位做异或运算，运算结果再和数组长度 - 1进行与运算，计算出储存下标的位置。具体原理如下：

综下所述 储存下标 = 哈希值 & 数组长度 - 1//jdk1.7中计算数组下标的HashMap源码
static int indexFor(int h, int length) {//计算储存元素的数组下标return h & (length-1);
}//jdk1.8中去掉了indexFor()函数，改为如下
i = (n - 1) & hash //i就是元素存储的数组下标 

某个key的哈希值为 ：1111 1111 1110 1111 0101 0101 0111 0101，数组初始长度也是16，如果没有 ^ h >>> 16，计算下标如下

          1111 1111 1110 1111 0101 0101 0111 0101  //h = hashcode()&  0000 0000 0000 0000 0000 0000 0000 1111  //数组长度 - 1 = 15 (15的二进制就是 1111)------------------------------------------0000 0000 0000 0000 0000 0000 0000 0101  //key的储存下标为5由上面可知，只相当于取了后面几位进行运算，所以哈希冲突的可能大大增加。

以上条件不变，加上异或h >>> 16，之后在进行下标计算

          1111 1111 1110 1111 0101 0101 0111 0101  //h = hashcode()^  0000 0000 0000 0000 1111 1111 1110 1111  //h >>> 16------------------------------------------1111 1111 1110 1111 1010 1010 1001 1010  //h = key.hashCode() ^ (h >>> 16) &   0000 0000 0000 0000 0000 0000 0000 1111  //数组长度 - 1 = 15 (15的二进制就是 1111)------------------------------------------0000 0000 0000 0000 0000 0000 0000 1010  //key的存储下标为10重要：由上可知，因为哈希值得高16位和低16位进行异或运算，混合之后的哈希值，低位也可能掺杂了高位的一部分特性(就是变化性增加了)，这样就减少了哈希冲突。

(2)为什么HashMap的初始容量和扩容都是2的次幂

回答：也是为了减少哈希冲突。

原理：
因为判断储存位置的下标为 ：i = (n - 1) & hash，n就是数组的长度。
2的次幂 - 1，其二进制都是1，比如 2^4 -1= 15(1111)，2^5-1 = 31(11111)。
因为n-1和hash进行与运算，只有 1 & 1 ，才为1。
因为n-1永远是2的次幂-1，(n - 1) & hash的结果就是 hash的低位的值。

          1111 1111 1110 1111 0101 0101 0111 0101  //hash值&  0000 0000 0000 0000 0000 0000 0000 1111  //数组长度 - 1 = 15 (15的二进制就是 1111)------------------------------------------0000 0000 0000 0000 0000 0000 0000 0101  //高位全部清零，只保留末四位(就相当于保留了hash的低位)

如果容量不是2次幂会怎么样呢？如下图表

• 2次幂的时候，数组长度为16，n-1 = 16 -1 = 15(1111)

hash	(n-1) & hash	储存下标
0	1111 & 0000	0
1	1111 & 0001	1
2	1111 & 0010	2
3	1111 & 0011	3
4	1111 & 0100	4
5	1111 & 0101	5

• 非2次幂的时候，数组长度为10，n-1 = 10 -1 = 9(1001)

hash	(n-1) & hash	储存下标
0	1001 & 0000	0
1	1001 & 0001	1
2	1001 & 0010	0
3	1001 & 0011	1
4	1001 & 0100	0
5	1001 & 0101	1

重要：由上看出，n为2的次幂，哈希冲突会更少，保证元素的均匀插入。

(3)如果指定了不是2的次幂的容量会发生什么？

回答：会获得一个大于指定的初始值的最接近2的次幂的值作为初始容量。
比如：输入 9 获得 16，输入 5 获得 8。
原理如下：

    static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子static final int MAXIMUM_CAPACITY = 1 << 30;//初始容量最大为 2的30次方/*** @param initialCapacity 初始容量*/public HashMap(int initialCapacity) {//此处通过把第二个参数负载因子使用默认值0.75f，然后调用有两个参数的构造方法this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用函数一}/*** 函数一* @param initialCapacity 初始容量* @param loadFactor  负载因子*/public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)   //如果初始容量小于0，抛出异常throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)  //如果初始容量超过最大容量（1<<30）initialCapacity = MAXIMUM_CAPACITY;  //则使用最大容量作为初始容量if (loadFactor <= 0 || Float.isNaN(loadFactor))  //如果负载因子小于等于0或者不是数字，则抛出异常throw new IllegalArgumentException("Illegal load factor: " + loadFactor);this.loadFactor = loadFactor;                //把负载因子赋值给成员变量loadFactor//调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果，并赋给成员变量thresholdthis.threshold = tableSizeFor(initialCapacity); //调用函数二}/*** 函数二* @param cap 初始容量*/static final int tableSizeFor(int cap) { //这里我们假设我们初始容量是 10//容量减1，为了防止初始化容量已经是2的幂的情况，在最后有n+1的操作。  n = 10 - 1 = 9int n = cap - 1;      //n = (n | n >>> 1) 带入得   n = (1001 | 0100) = 1101 n |= n >>> 1;        //n = (n | n >>> 2) 带入得   n = (1101 | 0011) = 1111 n |= n >>> 2;       //n = (n | n >>> 4) 带入得   n = (1111 | 0000) = 1111 n |= n >>> 4; //n = (n | n >>> 8) 带入得   n = (1111 | 0000) = 1111 n |= n >>> 8;       //n = (n | n >>> 16) 带入得  n = (1111 | 0000) = 1111 = 15n |= n >>> 16;        /**如果入参cap为小于或等于0的数，那么经过cap-1之后n为负数，n经过无符号右移和或操作后仍未负数,所以如果n<0,则返回1;如果n大于或等于最大容量，则返回最大容量;否则返回n+1。n = 15 + 1 = 16，咱们传进来是初始容量10，会自动转为16容量。**/return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;相当于下面这段代码if(n < 0){return 1;}else{if(n >= MAXIMUM_CAPACITY){return MAXIMUM_CAPACITY; }else{return n + 1;}}}

4.2 HashMap为什么线程不安全(面试题)

(1) 多线程下扩容造成的死循环和数据丢失(jdk1.7)

在jdk1.7中，链表采用的是头插法(每次插入节点都是从头插入)。

① 假设这里有两个线程同时执行了put()操作(扩容)，并进入了transfer()方法。线程A先进行操作

② 线程A在执行到newTable[i] = e后被挂起，因为newTable[i] = null,又因为 e.next = newTable[i]，所以e.next = null

transfer()方法部分源码：while(null !=e){Entry<K,V> next =e.next; //next = 3.next = 7e.next = newTable[i]; //3.next = nullnewTable[i] = e;//线程A执行到这里被挂起了e = next;}

③ 开始执行线程B，并完成了扩容。这时候 7.next = 3；3.next = null；

④ 继续执行线程A，执行newTable[i] = e，因为当时 e = 3，所以将3放到对应位置，此时执行e = next，因为next = 7(第②步)，所以e = 7

while(null !=e){Entry<K,V> next =e.next; //next = 3.next = 7e.next = newTable[i]; //3.next = nullnewTable[i] = e;//继续从这里执行  newTable[i] = 3e = next; //e = 7}

⑤ 上轮循环之后e=7，从主内存中读取e.next时发现主内存中7.next=3，此时next=3，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环。

while(null !=e){Entry<K,V> next =e.next; //next = 7.next = 3e.next = newTable[i]; //7.next = 3newTable[i] = e;//newTable[i] = 7e = next; //e = 3}

⑥上轮循环7.next=3，而e=3，执行下一次循环可以发现，因为3.next=null，所以循环之后 e = null，所以循环会退出。

while(null !=e){Entry<K,V> next =e.next; // next = 3.next = nulle.next = newTable[i];  //3.next = 7 (此处3指向7,同时之前7也指向了3,所以会形成闭环)newTable[i] = e;       //newTable[i] = 3e = next;              //e = null(退出循环条件)}

(2)数据覆盖(jdk1.8)

jdk1.8中已经不再采用头插法，改为尾插法，即直接插入链表尾部，因此不会出现死循环和数据丢失，但是在多线程环境下仍然会有数据覆盖的问题。

当你调用put()方法时，putVal()方法里面有两处代码会产生数据覆盖。

① 假设两个线程都进行put操作，线程A和线程B通过哈希函数算出的储存下标是一致的，当线程A判断完之后，然后挂起，然后线程B判断完进入，把元素放到储存位置，然后线程A继续执行，把元素放到储存位置，因为线程A和线程B存储位置一样，所以线程A会覆盖线程B的元素。

② 同样在putVal()方法里。两个线程，假设HashMap的size为15，线程A从主内存获得15，准备进行++的操作的时候，被挂起，然后线程B拿到size并执行++操作，并写回主内存，这时size是16，然后线程A继续执行(这时A线程内存size还是15)++操作，然后写回主内存，即线程A和线程B都进行了put操作，然后size值增加了1，所以数据被覆盖了。

4.3 HashMap解决线程不安全(面试题)

(1) 使用HashTable解决线程不安全问题(弃用)

因为HashTable解决线程不安全就是在其方法加上同步关键字(synchronized)，会导致效率很低下。

(2)HashMap和HashTable的区别

①线程是否安全
HashMap线程不安全。
HashTable线程安全，但是效率较低。

②是否null
HashMap中key只能有一个null，value可以多个为null。
HashTable不允许键或值为null。

③容量
HashMap底层数组长度必须为2的幂（16，32，128…），默认为16。
HashTable底层数组长度可以为任意值，导致hash算法散射不均匀，容易造成hash冲突，默认为11。

④底层区别
HashMap是底层由数组+链表形成，在JDK1.8之后链表长度大于8时转化为红黑树。
HashTable一直都是数组+链表。

⑤继承关系
HashTable继承自Dictionary类。
HashMap继承自AbstractMap类。

(3)Collections.synchronizedMap(不常用)

Map<String,String> map = Collections.synchronizedMap(new HashMap<>());

可以看到SynchronizedMap 是一个实现了Map接口的代理类，该类中对Map接口中的方法使用synchronized同步关键字来保证对Map的操作是线程安全的。

(4)ConcurrentHashMap(常用)

① jdk1.7使用分段锁，底层采用数组+链表的存储结构，包括两个核心静态内部类 Segment(锁角色) 和 HashEntry(存放键值对)。

分段锁：Segment(继承ReentrantLock来加锁)数组中，一个Segment对象就是一把锁,对应n个HashEntry数组,不同HashEntry数组的读写互不干扰。

② JDK 1.8抛弃了原有的 Segment 分段锁，来保证采用Node + CAS + Synchronized来保证并发安全性。取消Segment类，直接用数组存储键值对。

4.4 为什么使用synchronized替换ReentrantLock锁呢？

① 减少内存开销。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承AQS(队列同步器)来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
② 获得JVM的支持。可重入锁毕竟是API这个级别的，后续的性能优化空间很小。 synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。
③在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。

AQS：是一个队列同步器，同步队列是一个双向链表，有一个状态标志位state，如果state为1的时候，表示有线程占用，其他线程会进入同步队列等待，如果有的线程需要等待一个条件，会进入等待队列，当满足这个条件的时候才进入同步队列，ReentrantLock就是基于AQS实现的

锁升级方式：就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为CAS(compare and swap 原子操作) 轻量级锁，如果失败就会短暂自旋(不停的判断比较，看能否将值交换)，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。

• 偏向锁：减少无竞争且只有一个线程使用锁的情况下，使用轻量级锁产生的性能消耗。轻量级锁每次申请、释放锁都至少需要一次CAS，但偏向锁只有初始化时需要一次CAS。
• 轻量级锁：当有两个线程，竞争的时候就会升级为轻量级锁。轻量级锁的目标是，减少无实际竞争情况下，使用重量级锁产生的性能消耗，包括系统调用引起的内核态与用户态切换、线程阻塞造成的线程切换等。
• 重量级锁：大多数情况下，在同一时间点，常常有多个线程竞争同一把锁，悲观锁的方式，竞争失败的线程会不停的在阻塞及被唤醒态之间切换，代价比较大。

4.5 HashMap底层 数组 + 链表 / 红黑树(面试题)

红黑树：平衡二叉查找树

(1)HashMap为什么引入链表

因为HashMap在put()操作时，会进行哈希值得计算，算出储存下标要放在数组那个位置时，当多个元素要放在同一位置时就会出现哈希冲突，然后引进链表，把相同位置的元素放进同一个链表(链地址法)。

(2)HashMap为什么引入红黑树

因为当链表长度大于8时，链表遍历查询速度比较慢，所以引入红黑树。

(3)为什么不一开始就使用红黑树

因为树相对链表维护成本更大，红黑树在插入新数据之后，可能会通过左旋、右旋、变色来保持平衡，造成维护成本过高，故链路较短时，不适合用红黑树。

(4)说说你对红黑树的理解

红黑树是一种平衡二叉查找树，是一种数据结构。除了具备二叉查找树特性以外，还具备以下特性

• 1.根节点是黑色
• 2.节点是黑色或红色
• 3.每个叶子节点是黑色
• 4.红色节点的子节点都是黑色
• 5.从任意节点到其叶子节点的所有路径都包含相同数目的黑色节点
  补充：以上性质强制了红黑树的关键性质从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。保证了红黑树的高效。

(5) 红黑树为什么要变色、左旋和右旋操作

当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。
过程：先变色如果变色还不满足红黑树的性质，那就进行左旋或者右旋，然后继续变色，以此循环直至符合红黑树的性质。

4.6 HashMap链表和红黑树转换(面试题)

• 链表长度大于8，并且表的长度大于64   数组 + 红黑树
• 链表长度大于8，并且表的长度不大于64  数组 + 链表 会扩容
• 当数的节点小于6             数组 + 链表

(1) 为什么链表长度大于8，并且表的长度大于64的时候，链表会转换成红黑树？

因为链表长度符合泊松分布，长度越长哈希冲突概率就越小，当链表长度为8时，概率仅为 0.00000006，这时是一个千万分之一的概率，然后我们map也不会存储那么多的数据，所以链表长度不超过8没有必要转换成红黑树。如果出现这种大量数据的话，转为红黑树可以增加查询和插入效率。长度大于64，只是注释写了 最低要在 4*8，我也没弄懂，请大佬指导。
原理如下：

In usages with well-distributed user hashCodes, tree bins 
are rarely used.  Ideally, under random hashCodes, the 
frequency of nodes in bins follows a Poisson distribution 
(http://en.wikipedia.org/wiki/Poisson_distribution) with a 
parameter of about 0.5 on average for the default resizing 
threshold of 0.75, although with a large variance because 
of resizing granularity. Ignoring variance, the expected 
occurrences of list size k are (exp(-0.5) * pow(0.5, k) / 
factorial(k)). The first values are:0:    0.606530661:    0.303265332:    0.075816333:    0.012636064:    0.001579525:    0.000157956:    0.000013167:    0.000000948:    0.00000006more: less than 1 in ten million  //翻译：更多：少于千万分之一负载因子是0.75和长度为8转为红黑树的原理：由上面我们可以看出 当负载因子为0.75时，哈希冲突出现的频率遵循参数为0.5的泊松分布。
常数0.5是作为参数代入泊松分布来计算的，而加载因子0.75是作为一个条件。泊松分布是一种离散概率分布，泊松分布的概率质量函数：x=(0,1,2,...)。
λ：单位时间内随机事件的平均发生率。因为我们从上面知道平均发生率是0.5
e^(-0.5) = 0.60653065971264  //e的负0.5次方
阶乘：指从1乘以2乘以3乘以4一直乘到所要求的数。比如 3！ = 1 * 2 * 3

• P(0) = (0.50 * e-0.5) / 0! ≈ 0.60653066
• P(1) = (0.51 * e-0.5) / 1! ≈ 0.30326533
• P(2) = (0.52 * e-0.5) / 2! ≈ 0.07581633

(2) 为什么转成红黑树是8呢？而重新转为链表阈值是6呢？

如果转为链表也是8，那如果在8这个位置发生哈希冲突，那红黑树和链表就会频繁切换，就会浪费资源。

(3) 为什么负载因子是0.75？

根据上面的泊松分布来看，表长度达到8个元素的时候，概率为0.00000006，几乎是一个不可能事件，减少了哈希冲突。

加载因子 = 填入表中的元素个数 / 散列表的长度

加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大；

加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费更多，而且还会提高扩容rehash操作的次数。

“冲突的机会”与“空间利用率”之间，寻找一种平衡与折中。

4.6 HashMap扩容(面试题)

(1)什么时候会发生扩容？

元素个数 > 数组长度 * 负载因子 例如 16 * 0.75 = 12,当元素超过12个时就会扩容。
链表长度大于8并且表长小于64，也会扩容

(2)为什么不是满了扩容？

因为元素越接近数组长度，哈希冲突概率就越大，所以不是满了扩容。

(3)扩容过程

• jdk1.7
  创建一个新的table，并调用transfer()方法把旧数组中的数据迁移到新数组中，使用的是头插法，也就是说，新table中链表的顺序和旧列表中是相反的，在HashMap线程不安全的情况下，这种头插法可能会导致死链和数据丢失现象。
• jdk1.8
  ①在resize()方法中，定义了oldCap参数，记录了原table的长度，定义了newCap参数，记录新table长度，newCap是oldCap长度的2倍，然后循环原table，把原table中的每个链表中的每个元素放入新table。
  ②计算索引做了优化：hash（原始hash） & oldCap（原始容量） == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap（原始容量）。

注意

• 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
• HashMap的容量达到2的30次方，就不会在进行扩容了。