面试题 -- hashmap
参考：https://www.jianshu.com/p/9ca74bdfdb6b
1.HashMap底层实现原理
2.HashMap工作原理
3.HashMap冲突产生及解决
4.HashMap不同步原因分析及解决办法
首先，我学习时JDK版本为1.8(在网上搜的，因为我学的时候已经是1.8了，自行百度了解，有错误指出谢谢)
JDK1.8中对Hashmap做了以下改动。
- 引入红黑树，优化数据结构
- 使用一个Node数组来存储数据,但这个Node可能是链表结构,也可能是红黑树结构。
- 将链表头插法改为尾插法
- 优化hash算法
- 出现哈希冲突时，1.7把数据存放在链表，1.8是先放在链表，链表长度超过8就转成红黑树
源码
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {}
基本属性
private static final long serialVersionUID = 362498820763181265L; // ***
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // （默认数组长度）初始容量为16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大数组容量2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 在构造函数中未指定时使用的负载因子。默认负载因子0.75
static final int TREEIFY_THRESHOLD = 8; // （链表转红黑树的阈值） 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
static final int UNTREEIFY_THRESHOLD = 6; // （扩容时红黑树转链表的阈值）桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
// 否则，若桶内元素太多时，则直接扩容，而不是树形化
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
transient Node<K,V>[] table; // 存储元素的数组，允许长度为0，总是2的幂次倍
transient Set<Map.Entry<K,V>> entrySet; // key-value集合
transient int size; // 映射中包含的键-值映射的数目（存放元素的数组，但是不等于数组的长度！！！）
transient int modCount; // 每次扩容或更改map结构的计数器
int threshold; // 临界值，当实际大小(容量*装载系数)超过临界值时，会进行扩容。
构造函数
1.初始容量（未定义）负载因子（未定义）
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于0，否则会报错
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量大于最大值，只能为最大值，不能再扩容了
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 负载因子不能小于0或者不为数字，抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor; // 初始化负载因子
this.threshold = tableSizeFor(initialCapacity); // 初始化临界值
}
2.初始容量（未定义）负载因子（0.75默认）
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3.初始容量（16默认）负载因子（0.75默认）
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他字段为默认值
}HashMap是数组+链表/红黑树（JDK1.8增加了红黑树部分）实现的
HashMap是基于hash算法实现的，通过put(key,value)存储，get(key)获取。当传入key时，HashMap会根据key.hashcode（）计算出hash值，根据hash值将value保存在bucket里。当计算出的hash值相同时，我们称之为hash冲突，HashMap的做法是用链表或红黑树存储相同hash值的value。
bucket桶：桶是每个所指数组的元素。在较早的Java版本中，每个存储桶都包含一个Map条目的链接列表。在新的Java版本（1.8版本）中，每个存储桶都包含条目的树结构或条目链接列表。
工作原理
1.put(key,value)存储对象
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}HashMap并没有直接提供putVal接口给用户调用，而是提供的put函数，而put函数就是通过putVal来插入元素的。
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未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 扩容
// 情况A：桶为空，直接将元素放入当前位置
//（n-1）&hash确定元素放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 情况B：桶中已存在元素，将当前结点记作P
else {
Node<K,V> e; K k;
// 情况一：判断是否直接覆盖（判断是否是同一个key）
// 比较桶中第一个元素（数组中的结点）的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋给e，用e来记录
e = p;
// 情况二：判断插入红黑树
// hash值不相等，即key不相等；为红黑树结点
else if (p instanceof TreeNode)
// // 放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 情况三：判断插入链表
// 为链表结点
else {
// 在链表最末插入结点
for (int binCount = 0; ; ++binCount) {
// 到达链表的尾部
if ((e = p.next) == null) {
// 在尾部插入新结点
p.next = newNode(hash, key, value, null);
// 结点数量达到阈值，转化为红黑树（阈值>8）（链表长度达到8，进行链表转红黑树）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循环
break;
// 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
p = e;
}
}
// 表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) { // existing mapping for key
// 记录e的value
V oldValue = e.value;
// onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
// 用新值替换旧值
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 结构性修改
++modCount;
// // 实际大小大于阈值则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}1.1Node<K,V>
Node是HashMap的一个静态内部类。实现了Map.Entry接口，本质是就是一个映射(键值对),主要包括 hash、key、value 和 next 的属性。
我们使用 put 方法像其中加键值对的时候，就会转换成 Node 类型。其实就是newNode(hash, key, value, null);
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;
}
}1.2TreeNode<K,V>
当桶内链表到达 8 的时候，会将链表转换成红黑树，就是 TreeNode类型，它也是 HashMap中定义的静态内部类。
三个相关参数:
TREEIFY_THRESHOLD=8 指的是链表的长度大于8 的时候进行树化，
UNTREEIFY_THRESHOLD=6 说的是当元素被删除后链表的长度小于6 的时候进行退化，由红黑树退化成链表
MIN_TREEIFY_CAPACITY=64 意思是数组中元素的个数必须大于等于64之后才能进行树化
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}1.3put()方法中调用hash(key)方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
1.4进入putVal()方法后
1.5resize()扩容
在初始化HashMap的时候，应该尽量指定其大小。尤其是当你已知map中存放的元素个数时。（《阿里巴巴Java开发规约》）
扩容会消耗内存，因为每次扩容时，首先先复制原来的数据，在添加新数据。可以在初始时计算出所需容量给定长度以防消耗内存。
resize 方法是会返回扩容后的数组的
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 保存当前table
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 保存table的大小
int oldThr = threshold; // 保存当前阈值
int newCap, newThr = 0;
// 之前table容量大于0
if (oldCap > 0) {
// 之前table大于最大容量时
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值为最大整形
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍，使用左移，效率更高
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 阈值*2
newThr = oldThr << 1; // double threshold
}
// 之前阈值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// // oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个元素会调用resize函数，会进入这一步）
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新阈值为0
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 初始化table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
之前的table已经初始化了
if (oldTab != null) {
// 复制元素，重新进行hash
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成rehash
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}说明：进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。
resize 不是无限的，当到达resize 的上限，也就是2^30 之后，不再扩容。
resize 方法只有三种情况下调用
- 第一种 是在首次插入元素的时候完成数组的初始化
- 第二种 是在元素插入完成后判断是否需要数组扩容，如果是的话则调用
- 第三种 是在元素插入链表尾部之后，进入树化方法之后，如果不树化则进行resize
1.6树化treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}2.get(key)获取对象
说明：HashMap并没有直接提供getNode接口给用户调用，而是提供的get函数，而get函数就是通过getNode来取得元素的
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// table已经初始化，长度大于0，根据hash寻找table中的项也不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 桶中第一项(数组元素)相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 桶中不止一个结点
if ((e = first.next) != null) {
// 为红黑树结点
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);
}
}
return null;
}解决hash冲突（在学习补充中）
当不同的元素key.hashcode()计算出的hash值相同时
存储对象时put()方法中调用的hash(key)方法中的key.hashcode()调用的是Object的hashcode()方法
参考：https://blog.csdn.net/weixin_43689776/article/details/99999126
HashMap不同步
解决HashMap的线程安全问题：
- Hashtable
- Java的
Collections库中的synchronizedMap()方法 Map map2 = Collections.SynchronizedMap(new HashMap()); - 使用
ConcurrentHashMapMap map3 = new ConcurrentHashMap();
Hashtable
Hashtable源码中是使用 synchronized 来保证线程安全的，比如下面的 get 方法和 put 方法：
public synchronized V get(Object key) {}
public synchronized V put(K key, V value) {}ConcurrentHashMap
package java.util.concurrent;
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {}
- 当你程序需要高度的并行化的时候，你应该使用
ConcurrentHashMap - 尽管没有同步整个Map，但是它仍然是线程安全的
- 读操作非常快，而写操作则是通过加锁完成的
- 在对象层次上不存在锁（即不会阻塞线程）
- 锁的粒度设置的非常好，只对哈希表的某一个key加锁
-
ConcurrentHashMap不会抛出ConcurrentModificationException，即使一个线程在遍历的同时，另一个线程尝试进行修改。 -
ConcurrentHashMap会使用多个锁
SynchronizedHashMap
package java.util;
public class Collections {
private static class SynchronizedMap<K,V>
implements Map<K,V>, Serializable {}
}- 会同步整个对象
- 每一次的读写操作都需要加锁
- 对整个对象加锁会极大降低性能
- 这相当于只允许同一时间内至多一个线程操作整个Map，而其他线程必须等待
- 它有可能造成资源冲突（某些线程等待较长时间）
-
SynchronizedHashMap会返回Iterator，当遍历时进行修改会抛出异常
https://www.cnblogs.com/shamo89/p/6700353.html
上一篇： IDEA WEB项目，网页出现乱码问题