HashMap
2020-03-31 本文已影响0人
打杂的_e2c9
本文就HashMap主要介绍一下几点：
1. HashMap 基础
2. HashMap 1.7 & 1.8
3. HashMap 源码解析
4. HashMap 面试
HashMap 基础
- HashMap 是无序的，即插入和读取的顺序不一致，这个和HashMap 的存取方式有关在后面源码分析时可以很容易理解这个问题，如想保证键值对有序可以使用LinkedHashMap
- HashMap 是非线程安全的，如果需要使用线程安全的Map,可以使用
HashTable
Collections.synchronizedMap(new HashMap(...))
ConcurrentHashMap
当然最推荐使用的还是ConcurrentHashMap，因为前两个线程线程安全的Map都是简单的使用了Synchronized在put 和 set方法上，一个线程在读写元素，其余线程必须等待，降低了性能，而ConcurrentHashMap采用 分段锁的机制，实现并发的更新操作 - 允许空key 和空value
- 在迭代过程中，如果 HashMap 的结构被修改，会快速失败即fail-fast 机制[https://blog.csdn.net/chenssy/article/details/38151189]
HashMap 1.7 & 1.8
- JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法,避免多线程操作死循环问题
- 出现hash 冲突时，JDK1.7采用链表存储，1.8 先采用链表存储，当链表长度超过8时转换为红黑树
- JDK1.8 初始化是在第一次插入数据时才初始化，而1.7是在构造的时候进行的初始化
HashMap 源码解析<基于1.8>
源码分析我们主要关注一下几点：
- 重要参数
- put 实现
- get 实现
- hash 实现
- resize 实现
重要参数
//初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子默认值： 提高空间利用率和 减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//bin(桶)容量大于等于8时，链表转化成红黑树()
static final int TREEIFY_THRESHOLD = 8;
//bin(桶)容量小于等于6时，红黑树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//容量最小64时才会转会成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
// 扩容的门槛，如果初始化时，给定数组大小的话，通过tableSizeFor 方法计算，永远接近于 2 的幂次方
// 如果是通过 resize 方法进行扩容后，大小 = 数组容量 * 0.75
int threshold;
//存放数据的数组
transient Node<K,V>[] table;
put 实现
- put(key,value)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
可以看到主要实现的方法是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;
//如果数组为空，初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// hashCode的算法先右移16 在并上数组大小-1
// 如果当前索引位置是空的，直接生成新的节点在当前索引位置上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果hash冲突，当前索引上有值
else {
Node<K,V> e; K k;
// 如果key equals都相等，那么当前节点就是我们要新增的
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是新增的节点，但是e仍然是null
//e和p.next都是持有对null的引用,即使p.next后来赋予了值
// 只是改变了p.next指向的引用，和e没有关系
p.next = newNode(hash, key, value, null);
//新增时，链表的长度大于等于8时，链表转红黑树
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;
}
}
//说明新增的元素table中原来就有
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 当前节点移动到队尾
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果kv的实际大小大于扩容的门槛，开始扩容
if (++size > threshold)
resize();
// 删除不经常使用的元素
afterNodeInsertion(evict);
return null;
}
从以上代码我们对put 方法进行总结：
- 检查table 数组是否为空，如果为空则初始化[table 的初始化是在第一次进行赋值的时候进行的]
- 计算key 的索引，如果计算出索引没有值则直接新增赋值
- 如果hash 冲突则分为3种情况：
-如果hash冲突的结点的key 与新插入的key相等，则当前节点就是我们要新增的，只要改变其value即可，将当前值赋值给e,代之后统一赋值
- 如果是红黑树，则采用红黑树的新增方式，同样如果存在当前的key，赋值代之后处理
- 如果为链表，则循环链表进行插入，第一种情况如果之前链表没有与此key相同的结点，则插入到链表最后，此时如果容量>=8则执行treeifyBin(tab, hash)<此函数稍后进行分析...>转换为红黑树；第二种情况如果循环过程中发现有与此key相同的结点，则赋值给e，代之后赋值value
- 查看e 是否有值，如果有则说明我们插入的结点在之前的桶中存在相同key值的结点，则直接改变其value，并返回结点中原来的value
- 如果是新添加的结点，则进行++size 操作并检查是否需要扩容
在插入节点的过程中我们看到有链表转红黑树的操作，我们看下这个函数：
// 链表转化成红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 当表的长度小于64 时不会进行转换，而是进行扩容
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);
}
}
因此我们需要注意一点：当table的的长度<64时并不会转换为红黑树，而是进行扩容！
get 实现
get(Object key)
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
getNode(int hash, Object key)
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 的 hash 相等，直接返回
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//hash不等，看看当前节点的 next 是否有值
if ((e = first.next) != null) {
// 使用红黑树的查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 采用自旋方式从链表中查找 key，e 为链表的头节点
do {
// 如果当前节点 hash == key 的 hash，并且 equals 相等，当前节点就是我们要找的节点
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值相同，则直接返回
- 如果存在next ：
结点为红黑树，采用红黑树的获取方式获取值
结点为链表结点，循环对比获取值
hash 和 索引的实现
- hash 实现
//可以看到这个函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以使高16位和低16位都参与运算，减少碰撞的概率，此外当key=null 时，hash 为0 ，从下面计算index 的方法可以看出，key 为空时index = 0,则放到了数组的第一个位置。
- 获取索引
// hash 值 & table 长度-1
(n - 1) & hash
结合设置链表的长度为2的幂，在扩容的时候可以保证index为之前或者oldIndex+oldlength ,即之前的位置加上之前数组的长度的位置
resize 实现
首先我们可以通过反射获取到HashMap的容量大小
HashMap map = new HashMap();
Class mapC = map.getClass();
Field filed = mapC.getDeclaredField("table");
filed.setAccessible(true);
Object object = filed.get(map);
Log.i(TAG, "onCreate: "+Array.getLength(object));
接下来我们看下resize 的实现
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
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
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
//初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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其实是个空值，get有可能是空的
table = newTab;
if (oldTab != null) {
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);
//规避了8版本以下的成环问题
else { // preserve order
// loHead 表示老值,老值的意思是扩容后，该链表中计算出索引位置不变的元素
// hiHead 表示新值，新值的意思是扩容后，计算出索引位置发生变化的元素
// 举个例子，数组大小是 8 ，在数组索引位置是 1 的地方挂着两个值，两个值的 hashcode 是9和33。
// 当数组发生扩容时，新数组的大小是 16，此时 hashcode 是 33 的值计算出来的数组索引位置仍然是 1，我们称为老值
// hashcode 是 9 的值计算出来的数组索引位置是 9，就发生了变化，我们称为新值。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// java 7 是在 while 循环里面，单个计算好数组索引位置后，单个的插入数组中，在多线程情况下，会有成环问题
// java 8 是等链表整个 while 循环结束后，才给数组赋值，所以多线程情况下，也不会成环
do {
next = e.next;
// (e.hash & oldCap) == 0 表示老值链表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// (e.hash & oldCap) == 0 表示新值链表
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;
}
接下来我们总结下具体的过程：
- 初始化或者双倍扩容，如果是空的，按照初始容量进行初始化
- 扩容采用双倍扩容机制
- 扩容后将老数组中的值移到新的表中，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap，分为三种情况：
- 如果原来位置只有一个值，则重新计算index 直接赋值到新数组中
- 如果为红黑树，则采用红黑树的split 方法将结点重新赋值到新数组
- 如果是链表，采用尾插后赋值法将链表中的值移动到新的数组
面试题
- 什么时候使用HashMap，它有什么特点
- HashMap JDK1.8 做了哪些优化
- HashMap 中的hash 算法以及为什么这么设计
- HashMap 的扩容机制
- 默认初始容量和加载因子是多少，为什么？
- HashMap 和 HashTable 的区别
HashMap和Hashtable的区别
HashMap 线程不安全，Hashtable线程安全
计算hash 值的方式不同
扩容方式不同
HashMap 的Key 可以为空，HashTable 不可以
HashMap1.8后解决冲突的方式不同
- 扩展问题：为什么重写equals 方法时要重写hashcode 方法？
[这个问题在网上搜到一篇不错的文章]
https://www.cnblogs.com/yuxiaole/p/9570850.html
