HashMap完成原理和源码详细分析
ps：本blog根据Jdk1.8
学习培训关键点：
1、了解HashMap的数据结构
2、掌握HashMap中的散列优化算法
3、了解HashMap中put、remove、get的源代码完成
4、HashMap的hach矛盾是啥？怎么处理的？
5、了解HashMap的扩充体制
1、什么叫HashMap？
HashMap 根据哈希表的 Map 插口完成，是以 key-value 储存方式存有 ，HashMap 的建立并不是同歩的，这代表它并不是线程安全的。它的 key、value 都能够为 null，除此之外，HashMap 中的投射并不是井然有序的。
2、HashMap的特点
- Hash储存混乱的
- key和value都能够储存null值，可是key只有存唯一的一个null值
- jdk8以前的数据结构是二维数组 链表，Jdk8以后变为二维数组 链表 红黑树
- 阈值超过8而且数组长度超过64才会变为红黑树
3、HashMap的数据结构
JDK7的状况，是二维数组加连接，hash矛盾情况下，就转化为链表：
jdk8的状况，jdk8再加上了红黑树，链表的数目超过8并且数组长度超过64以后，就转化为红黑树，红黑树连接点低于6以后，就又转化为链表：
翻下HashMap源码，相匹配的连接点信息内容：
static class Node<K,V> implements Map.Entry<K,V> {
// hashCode
final int hash;
final K key;
V value;
// 链表的next表针就不以null
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;
}
// ...
} 4、HashMap复位实际操作
4.1、成员变量
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/**
* 系列号版本信息
*/
private static final long serialVersionUID = 362498820763181265L;
/**
* 复位容积，为16=2的4次幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 较大容积，为2的30次幂
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认设置的负荷因素，初始值是0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表连接点树超出8就变为为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 红黑树连接点低于6就再变换回链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶中构造转换为红黑树相匹配的数组长度最少的值
*/
static final int MIN_TREEIFY_CAPACITY = 64;
// ...
/**
* HashMap储存原素的二维数组
*/
transient Node<K,V>[] table;
/**
* 用于储放缓存文件
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* HashMap储放原素的数量
*/
transient int size;
/**
* 用于纪录HashMap的更改频次
*/
transient int modCount;
/**
* 用于调节尺寸下一个容积的值（容量*负荷因素）
*/
int threshold;
/**
* Hash表的负荷因素
*/
final float loadFactor;
} 4.2、 构造函数
public HashMap(int initialCapacity, float loadFactor) {
// 原始容积不可以低于0，小于0立即抛出去IllegalArgumentException
if (initialCapacity < 0)
throw new IllegalArgumentException(\"Illegal initial capacity: \"
initialCapacity);
// 原始容积超过较大容积的情况下，取较大容积做为原始容积
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 负荷因素不可以低于0，并且如果标值种类，isNan:true,表明就是是非非标值种类
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(\"Illegal load factor: \"
loadFactor);
// 将选定的负荷因素取值给局部变量
this.loadFactor = loadFactor;
// threshold = (容积) * (负荷因素)
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
// 复位容积和默认设置负荷因素
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
// 默认设置的负荷因素为0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
}随后，我们知道HashMap的默认设置容积是16，随后是在哪儿取值的？从上边这一编码就可以了解this.threshold = tableSizeFor(initialCapacity);
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;
}这儿牵涉到电子计算机基础知识的，偏移计算和或运算，下边得出图示：根据较为繁琐的测算得到n为16
往编码里翻，还寻找下边这一构造函数public HashMap(Map<? extends K, ? extends V> m)：这一构造函数是用来结构一个镜像关联与特定 Map 同样的新 HashMap：
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}看一下putMapEntries这一方式：
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 传到的结合长短
int s = m.size();
if (s > 0) {
// 分辨table是不是已经复位解决
if (table == null) { // pre-size 未复位的状况
// 再加上1.0F的目的性是对小数向上取整，确保较大容积，降低resize的启用频次
float ft = ((float)s / loadFactor) 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 推算出来的t大于HashMap的阈值，开展tableSizeFor
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold) // 已经复位的状况，开展扩充resize
resize();
// 解析xml，将map中的全部要素都加上到hashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}5、Jdk8中HashMap的优化算法
5.1、HashMap中散列算法
在HashMap的java.util.HashMap#hash，这一方式中有特殊的用来测算哈希值的方式：这一办法的功效？这一办法便是用以hashMap当put相匹配的key以后，测算指定的hashCode，随后再(n-1)&hash测算相应的二维数组table的字符，这一后边跟一下HashMap源代码才非常清楚：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}看上去编码仅有二行，随后实际上蕴涵了一种散列优化算法的观念，下边简易剖析一下：这儿先将源代码开展分拆，看上去清楚点：
static final int hash(Object key) {
// 传到的key为null，回到初始值0
if (key == null) return 0;
// 测算hachcode
int h = key.hashCode();
// 将推算出来的hashCode偏移16位，等同于乘以(1/2)的16次方
int t = h >>> 16;
// 将2个值做异或运算随后回到
return h ^ t;
}实际上里边要做的事儿是先估算出hashCode，随后将hashCode偏移16位，随后这两个数再做异或运算。看上去是那么一回事儿，随后创作者的目的是啥？最先即然是散列优化算法，散列算法的目标也是因为让数据信息联合分布
从图可以看得出，应用异或运算，发生0和1的几率是相同的，因此这就是为什么要应用异或运算的缘故，散列算法的基本特征目地也是因为让数据信息联合分布，应用异或运算得到的哈希值由于较为匀称散列遍布，因此发生hach矛盾的可能性就小许多
填补：
与运算：两个数相对应的位数据全是1，与运算后是1，其他状况是0；或运算：两个数相对应的位数据只需有1个是1，或运算后是1，不然是0；异或运算：两个数相对应的位数据同样，結果是0，不然是1；
随后为什么再开展偏移16位？我们知道，int类型较大的标值是2的32次方，随后可以分成高16位再加上低16位，偏移16位便是使标值缩小了，“左大右小”，这个是位移运算的规则
5.2、什么叫HashMap中hach矛盾？
hach矛盾还可以称作哈希碰撞，理论上的hach矛盾就是指推算出来的哈希值一样，造成矛盾了，但是在HashMap中的hach矛盾实际就是指(n-1)&hash，这一值是hashMap里二维数组的字符。Jdk8以前的处置方式 是根据单链表解决，只需hash矛盾了，便会将连接点加上到单链表尾端；jdk8以后的作法是根据单链表 红黑树的方式，最初hach矛盾了，也是用单链表，随后单链表连接点做到8个，数组长度超出64的状况，转成红黑树，这一可以在源代码里找到答案
翻下源码，HashMap#putVal，里边的逻辑性，先校检推算出来的，二维数组tab的字符，i=(n-1)&hash是不是矛盾了，不冲突就新增加连接点，矛盾的状况，转单链表或是红黑树
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);6、Jdk8中HashMap的put实际操作
- put方式的关键步骤
- 依据hashcode测算二维数组的字符
- 相匹配字符二维数组为空的状况，新增加连接点
- 不然便是hach矛盾了，假如桶应用单链表连接点，就新增加到单链表连接点尾端，应用了红黑树就新增加到红黑树里
上边是主要的步骤，忽视了存有相同的键，则为该键更换新值 value， size 超过阀值 threshold，则开展扩充这些这种状况
ok，或是跟一下put源代码：
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;
// 第1次新增加，原始数据信息resize
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 分辨是不是发生hash矛盾
if ((p = tab[i = (n - 1) & hash]) == null)
// hash不冲突，新增加连接点
tab[i] = newNode(hash, key, value, null);
else { // hach矛盾的状况，应用单链表或是红黑树解决
Node<K,V> e; K k;
// 存有相同的键的状况，key和hash都相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将旧的连接点目标取值给新的e
e = p;
else if (p instanceof TreeNode) // 应用了红黑树连接点
// 将节点放进红黑树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 单链表的状况
// 不断循环
for (int binCount = 0; ; binCount) {
// 一直解析xml，寻找尾连接点
if ((e = p.next) == null) {
// 将新节点加上到尾端
p.next = newNode(hash, key, value, null);
// 连接点总数超过8，变为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 跳出循环
break;
}
// 也是为了防止hashCode和key一样的状况
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 再次取值，用以单链表的解析xml
p = e;
}
}
// 桶中寻找的key、hash相同的状况，也就是找到反复的键，要应用新值更换旧值
if (e != null) { // existing mapping for key
// 纪录e的值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 用新值更换旧值
e.value = value;
// 浏览后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 纪录改动次数
modCount;
// size大于threshole，开展扩容
if ( size > threshold)
resize();
// 回调方式
afterNodeInsertion(evict);
return null;
}随后是怎么变换为红黑树的？红黑树的专业知识相对性比较复杂
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY数值64，换句话说数组长度低于64是不可能真真正正转红黑树的
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 扩容方式
resize();
// 转红黑树实际操作
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 红黑树的头连接点hd和尾节点t1
TreeNode<K,V> hd = null, tl = null;
do {
// 搭建树连接点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
// 新节点p取值给红黑树的头连接点
hd = p;
else {
// 新节点的前连接点便是原本的尾连接点t1
p.prev = tl;
// 尾端连接点t1的next节点便是新连接点
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 让二维数组的连接点实行新创建的树连接点，以后这一连接点就变为TreeNode
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}7、HashMap的扩容体制
这一知识是HashMap中的一个关键之一，也是一个较为难的问题
7.1、何时必须扩容？
当hashMap中原素数量超出threshold，threshold为数组长度乘于负荷因素loadFactor，loadFactor默认设置是0.75f
7.2、什么叫HashMap的扩容？
resize这一方式 是HashMap的扩容方式，是非常用时的。HashMap在扩容时，全是翻二倍，例如16的容积扩张到32,。HashMap开展扩容的办法是较为恰当的，扩容后，与原先的字符(n-1)&hash相对性，实际上就是多了1bit位。扩容后连接点要不是在原先部位，听起来仿佛很懵，因此或是用心看下面的剖析：
下边得出事例，例如从容积为16扩容到32时，绘图表明：
开展扩容，扩张到以前的二倍：
到这一步，字符(n-1) & hash，扩容后的数据信息10101和原先的00101对比，实际上便是多了1bit，10101是十进制的21，而21=5 16，就是“原部位 旧容积”，也有此外一种情形是维持为0的状况，这样的事情不是更改部位的
下边得出一份报表，数据信息如下图：
容积为16的状况
有底位的2个表针loHead、lloTail，低位的2个表针hiHead、hiTail
扩容到32以后，再2个单链表加到相匹配部位。各自有2种状况，维持原先部位的和“原位置 旧容积”这一部位
因此，扩容的全过程，相匹配的连接点部位更改是如此的全过程：
7.3、resize的源代码完成
通过上边较为详尽的剖析，这一完成逻辑性是可以在源代码里寻找相应的，ok，跟一下对应的源代码：
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) { // 超出较大容积 即 1 <<< 30
// 超出较大容积也不扩大了，改动阈值为较大容积
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) // initial capacity was placed in threshold
// 老阈值取值给新的数组长度
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 应用初始值16
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 再次测算阈值，随后要取值给threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 新的阈值，原先默认设置是12，如今变成24
threshold = newThr;
// 建立新的连接点, newCap是新的数组长度，为32
@SuppressWarnings({\"rawtypes\",\"unchecked\"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
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)
// 是红黑树连接点，启用split方式
((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;
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偏向要挪动的节点e
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
// 部位不会改变
newTab[j] = loHead;
}
if (hiTail != null) {
// hiTail偏向null
hiTail.next = null;
// oldCap是旧容积 ，挪动到“原部位 旧容积”这一部位
newTab[j oldCap] = hiHead;
}
}
}
}
}
return newTab;
}8、Jdk8中HashMap的remove实际操作
remove方式，这儿构思是先要寻找原素的部位，如果是单链表，解析xml单链表remove元素就可以，红黑树的情形就解析xml红黑树寻找连接点，随后remove树连接点，假如此刻树连接点数低于6，这样的事情就需要转单链表
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 数组下标是(n-1)&hash，能找获得原素的状况
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 桶上的连接点便是要找的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将Node偏向该连接点
node = p;
else if ((e = p.next) != null) { // 单链表或是是红黑树连接点的状况
if (p instanceof TreeNode)
// 寻找红黑树连接点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { // 单链表的状况
// 解析xml单链表，寻找必须找的连接点
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 寻找连接点以后
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
// 红黑树remove连接点
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
// 单链表remove，根据更改表针
tab[index] = node.next;
else
p.next = node.next;
// 纪录改动频次
modCount;
// 变化的总数
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}9、Jdk8中HashMap的get实际操作
get方式：根据key寻找value，这一方式很容易了解
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; Node<K,V> first, e; int n; K k;
// 假如哈希表不以空而且key相匹配的桶上不以空
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) { // 并不是第1个节点的状况，那就有可能是链表或是红黑树节点
if (first instanceof TreeNode)
// 依据getTreeNode获取红黑树节点
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 链表的状况，只有解析xml链表
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}10、HashMap有关面试问题
- HashMap的算法设计是啥？
- 在jdk8以前是二维数组 链表，jdk8以后是二维数组 链表 红黑树
- HashMap 中 hash 函数公式是怎么完成的？
- 先根据jdk的hashCode()方式获取hashCode，偏移16位，随后这两个数再做异或运算
- 什么叫HashMap中的hach矛盾？
- hach矛盾，还可以称作哈希碰撞，一般是值测算出的哈希值一样的，在HashMap中是依据测算出的hash，再去计算二维数组table字符(n-1)&hash一样了，也就是矛盾了
- HashMap是如何处理hach矛盾问题的？
- 在jdk8以前是根据链表的方式，jdk8以后是根据链表 红黑树的方式
- HashMap是线程安全的？
- HashMap并不是线程安全的，由于源代码里没加同步锁也没其他确保线程安全的实际操作
- HashMap并不是线程安全的，随后有什么方法？
- 可以应用ConcurrentHashMap
- ConcurrentHashMap是怎么确保线程安全的？
- ConcurrentHashMap在Jdk8中 应用了CAS再加上synchronized同步锁来确保线程安全
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
