可访问个人网站进行阅读最新版本，精力有限无法多网站同步更新，更新只会在个人网站进行
文章目录
- 面试题
- 一、底层数据结构
- 1.1 构造函数
- 二、存取机制
- 2.1 put(K key, V value)
- 2.1.1 hash()方法与hashcode()方法
- 2.1.2 Fail-Fast 机制
- 2.2 get(key)
- 2.3 面试题
- 2.3.1 hashcode()与equals()区别
- 2.3.2 为什么要重写equals()方法？
- 2.3.3 为什么改写了equals()，也需要改写hashcode()
- 2.3.4 为什么改写了hashcode()，也需要改写equals()
- 三、扩容机制
- 3.1 resize()
- 四、面试题
- 4.1 扩容为什么是2倍？
- 4.2 为什么String, Interger这样的wrapper类适合作为键？
- 4.3 线程不安全的原因
- 4.4 你了解重新调整HashMap大小存在什么问题吗？
面试题
先来看看常问的面试题有哪些
- 底层数据结构
- hash冲突解决
- 1.7和1.8区别
- 扩容机制（为什么是2倍）
- rehash过程
- 红黑树的左右旋
一、底层数据结构
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;//最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;//填充比，占满0.75进行resize
static final int TREEIFY_THRESHOLD = 8; // 链表长度达到8时将链表转换为红黑树
static final int UNTREEIFY_THRESHOLD = 6; // 树大小为6，就转回链表
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<k,v>[] table;//存储元素的数组
transient Set<map.entry<k,v>> entrySet;
transient int size;//存放元素的个数
transient int modCount;//被修改的次数fast-fail机制
int threshold;//临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容
final float loadFactor;//填充比
// 1.位桶数组
transient Node<k,v>[] table;//存储（位桶）的数组</k,v>
// 2.数组元素Node<K,V>实现了Entry接口
//Node是单向链表，它实现了Map.Entry接口
static class Node<k,v> implements Map.Entry<k,v> {
final int hash;
final K key;
V value;
Node<k,v> next;
//构造函数Hash值 键 值 下一个节点
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 V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true
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;
}
}
// 3.红黑树
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;
}
}
}
总结：1.7的hashmap是由位桶数组+链表组成，1.8之后的hashmap由位桶数组+链表+红黑树组成。其中数组指bucket数组，数组中的元素是实现了map.Entry<k,v>接口的Node<k,v>，每个Node<k,v>包含key，value，next指针，hash值。当put元素时会调用hashcode计算hash值，相同key而value不同的元素会发生哈希碰撞，采用拉链拉解决，将该元素插入到链表中。当TREEIFY_THRESHOLD>8时，会转化成红黑树。
1.1 构造函数
//构造函数1
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;
this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值
}
//构造函数2
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造函数3
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//构造函数4用m的元素初始化散列映射
public HashMap(Map<!--? extends K, ? extends V--> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
二、存取机制
在明白它是怎么取之前需要先明白是怎么存的
2.1 put(K key, V value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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; // resize()不仅用来调整大小，还用来进行初始化配置
// （n-1）&hash相当于hash%(n-1)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e;
K k;
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) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，
//treeifyBin首先判断当前hashMap的长度，如果不足64，只进行
//resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
// 继续向后
p = e;
}
}
if (e != null) { // existing mapping for key，就是key的Value存在
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;//返回存在的Value值
}
}
++modCount; // 修改次数+1
if (++size > threshold)
resize();//扩容两倍
afterNodeInsertion(evict);
return null;
}
下面简单说下添加键值对put(key,value)的过程：
-
判断位桶数组是否为空数组，是则通过resize初始化
-
通过hash(key)计算hash值判断该Node<k,v>应该插入的位置(不同的key可能有相同的hashcode)
-
如果该位置还没插入值，则直接插入；如果已存在值
- 判断key是否相同，是：则用e记录该结点；
- 否：则判断table[i]是否为树结点，
- 是：则以红黑树的方式插入，用e记录；
- 否：则遍历链表插入到链尾（如果长度>8转成红黑树)；遇到已存该元素的情况下，用e记录，并退出
-
在上述步骤中，都有用e记录了数组中或链表或红黑树已存在该元素的信息。通过修改e来覆盖原值
-
判断加入结点后是否超过门限值，是否需要扩容
2.1.1 hash()方法与hashcode()方法
我们通过hash方法计算索引，得到数组中保存的位置
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
以看到HashMap中的hash算法是通过key的hashcode值与其hashcode右移16位后得到的值进行异或运算得到的，那么为什么不直接使用key.hashCode()，而要进行异或操作？我们知道hash的目的是为了得到进行索引，而hash是有可能冲突的，也就是不同的key得到了同样的hash值，这样就很容易产业碰撞，如何减少这种情况的发生呢，就通过上述的hash(Object key)算法将hashcode 与 hashcode的低16位做异或运算，混合了高位和低位得出的最终hash值，冲突的概率就小多了
2.1.2 Fail-Fast 机制
我们知道 java.util.HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 Map：注意到 modCount 声明为 volatile，保证线程之间修改的可见性。
所以在这里和大家建议，当大家遍历那些非线程安全的数据结构时，尽量使用迭代器
2.2 get(key)
通过put过程，我们已经知道Node(k,v)是怎么保存到map中的，现在来看看怎么取
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;//Entry对象数组
Node<K,V> first,e; //在tab数组中经过散列的第一个位置
int n;
K k;
//也就是说在一条链上的hash值相同的
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))))//判断条件是hash值要相同，key值要相同
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)找到bucket数组中该hash值的位置，判断该位置的元素也就是first的key是否与要找的这个key相同
- 是：则返回该first元素
- 否：判断first是否是树节点
- 是：则通过红黑树的方式进行查找
- 否：遍历链表查找到key相同的Node并返回
- 如果没找到，则返回null
2.3 面试题
2.3.1 hashcode()与equals()区别
get()查找元素的过程：计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。
Object的equals()是基于比较内存地址实现的，hashcode()是比较内存地址的hash值
在map中，hashcode(实际是hash方法，封装了hashcode和低16位异或运算)用来计算key应该放在数组中的哪个位置，equals是用在有多个hashcode相同的情况下查找需要的key。
2.3.2 为什么要重写equals()方法？
因为object中的equals()方法比较的是对象的引用地址是否相等，如何你需要判断对象里的内容是否相等，则需要重写equals()方法。
2.3.3 为什么改写了equals()，也需要改写hashcode()
如果你重载了equals，比如说是基于对象的内容实现的，而保留hashCode的实现（基于内存地址的hash值）不变，那么在添加进map中时需要比对hashcode，很可能某两个对象明明是“相等”，而hashCode却不一样。
2.3.4 为什么改写了hashcode()，也需要改写equals()
Hashmap的key可以是任何类型的对象，例如User这种对象，为了保证两个具有相同属性的user的hashcode相同，我们就需要改写hashcode方法，比方把hashcode值的计算与User对象的id关联起来，那么只要user对象拥有相同id，那么他们的hashcode也能保持一致了，这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素，还需要用key的equals方法在对应位置的链表中找到需要的元素，所以只改写了hashcode方法是不够的，equals方法也是需要改写。
在改写equals方法的时候，需要满足以下三点：
(1) 自反性：就是说a.equals(a)必须为true。
(2) 对称性：就是说a.equals(b)=true的话，b.equals(a)也必须为true。
(3) 传递性：就是说a.equals(b)=true，并且b.equals©=true的话，a.equals©也必须为true。
通过改写key对象的equals和hashcode方法，我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。
三、扩容机制
当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大为原来2倍，然后重新调用hash方法找到新的bucket位置。
3.1 resize()
jdk1.7的源码：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
......
// 创建一个新的 Hash Table
Entry[] newTable = new Entry[newCapacity];
// 将 Old Hash Table 上的数据迁移到 New Hash Table 上
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
// 迁移数组
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
//下面这段代码的意思是：
// 从OldTable里摘一个元素出来，然后放到NewTable中
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
迁移过程：
单线程下的迁移：在扩容之后，重新计算hash定位到新数组中，相同hash值的元素照样连接成链表，只是链表相对位置进行了反转。
多线程下的迁移：
线程1在获取next结点之后被挂起，Thread 1 的 e 指向了 key(3)，而 next 指向了 key(7)。线程2顺利完成rehash过程，链表反转。
do {
Entry<K,V> next = e.next; // 假设线程一执行到这里就被调度挂起了
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
线程1继续执行，仍会把线程二的新表当成原始的hash表，将原来e指向的key(3)节点当成是线程二中的key(3)，放在自己所建newTable[3]的头节点，线程1的next仍然指向key(7)，此时key(3)的next已经是null。
e.next = newTable[i]; // key(3)的 next 指向了线程1的新 Hash 表，因为新 Hash 表为空，所以e.next = null
newTable[i] = e; // 线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。e 处理完毕
e = next; // 将 e 指向 next，所以新的 e 是 key(7)
线程1的e指向了上一次循环的next，也就是key(7)，此时key(7)的next已经是key(3)。将key(7)插入到table[0]的头节点，并且将key(7)的next设置为key(3), e 和next继续往下移。此时仍然没有问题。
继续下一次循环，e.next = newTable[i] 导致 key(3).next 指向了 key(7)，但此时的 key(7).next 已经指向了 key(3)， 环形链表就这样出现了。
jdk1.8的源码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//以前的容量大于0，也就是hashMap中已经有元素了，或者new对象的时候设置了初始容量
if (oldCap > 0) {
//如果以前的容量大于限制的最大容量1<<30,则设置临界值为int的最大值2^31-1
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0)
newCap = oldThr;
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//对临界值做判断，确保其不为0，因为在上面第二种情况(oldThr > 0)，并没有计算newThr
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将刚创建的新表赋值给table
table = newTab;
if (oldTab != null) {
//遍历将原来table中的数据放到扩容后的新表中来
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//没有链表Node节点，直接放到新的table中下标为[e.hash & (newCap - 1)]位置即可
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是treeNode节点，则树上的节点放到newTab中
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果e后面还有链表节点，则遍历e所在的链表，
else { // 保证顺序
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
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;
}
总结：
-
如果table == null, 则为HashMap的初始化, 生成空table返回即可;
-
如果table不为空, 需要重新计算table的长度, newLength = oldLength << 1(注, 如果原oldLength已经到了上限, 则newLength = oldLength);
-
遍历oldTable，oldTable[i]为空，遍历下一个
- 否：判断oldTable[i].next是否为空
- 是：存放到newTable中newTab[
e.hash & (newCap - 1)] - 否：判断是否红黑树
- 是：走红黑树的重定位
- 否：JAVA7时还需要重新计算hash位, 但是JAVA8做了优化, 通过
(e.hash & oldCap)== 0来判断节点位置通过再次hash算法后，是否会发生改变- 是：移动到当前hash槽位 + oldCap的位置
- 否：移动到新表中原下标的位置
- 是：存放到newTable中newTab[
- 否：判断oldTable[i].next是否为空
注：newCap/oldCap为容量
四、面试题
4.1 扩容为什么是2倍？
主要与HashMap计算添加元素的位置时，使用的位运算有关，这是特别高效的运算；HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低。
4.2 为什么String, Interger这样的wrapper类适合作为键？
如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能，也就适合做Hashmap的键。因为获取对象的时候要用到equals()和hashCode()方法，键对象正确的重写这两个方法是非常重要的。
因此，String，Interger这样的wrapper类作为HashMap的键是再适合不过了，而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象
4.3 线程不安全的原因
HashMap在并发场景下可能存在以下问题：
死循环：在jdk1.7中，resize过程中，从旧数组重新迁移至新数组的过程中，仍可能会发生hash冲突，形成链表，链表的相对位置发生了反转，那么在并发环境下，容易出现多线程同时resize的情况，那么就有可能在迁移过程中发生闭环，一旦发生闭环，进行get()操作的时候就会陷入死循环。在jdk1.8中，用 head 和 tail 来保证链表的顺序和之前一样，因此不会出现发生闭环的情况。
数据丢失：
-
如果多个线程同时使用 put 方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞（根据 hash 值计算的 bucket 一样），那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程 put 的数据被覆盖
-
如果多个线程同时检测到元素个数超过数组大小 * loadFactor，这样就会发生多个线程同时对 Node 数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table，也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失
4.4 你了解重新调整HashMap大小存在什么问题吗？
Jdk1.7 当多线程的情况下，可能产生条件竞争(race condition)。
当重新调整HashMap大小的时候，如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调 整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部， 这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。
注：尾部遍历（避免尾部遍历是为了避免在新列表插入数据时，遍历队尾的位置。因为，直接插入的效率更高。）
死循环的发生
