底层源码分析-HashMap源码详解
- HashMap JDK7 与JDK8的差异
- HashMap put()详解
- HashMap resize()详解
- HashMap域
- HashMap重要方法
-
- put(K key, V value)
- treeifyBin()树化
- resize() 扩容
- split() 扩容树的分发方式
-
HashMap JDK7 与JDK8的差异
数据结构的改变
- JDK8新增了红黑树的数据结构（解决Hash冲突链表过长）
插入方法中的改变
- JDK7中链表的插入是用的头插法，而JDK8中则改为了尾插法。是为了扩容的数据转移
- JDK8中的因为使用了红黑树保证了插入和查询了效率，所以实际上JDK8中的Hash算法实现的复杂度降低了
- JDK 8的hash函数比JDK 7的简单减少CPU的损耗
扩容中的改变
- JDK8中数组扩容的条件也发了变化，**只会判断是否当前元素个数是否查过了阈值，**而不再判断当前put进来的元素对应的数组下标位置是否有值。还有一个就是树化时候低于64 个的时候。
- JDK 7中扩容是一个一个转移 而JDK8 中是先遍历链表 分成两个直接去转移
- 扩容的过程中JDK7中有可能会重新对key进行哈希（重新Hash跟哈希种子有关系），而JDK8中没有这部分逻辑
HashMap put()详解
- 通过key计算出一个hashcode ，如果table=null，创建table。
- 通过hashcode与“与操作”计算出一个数组下标 注意:这里需要数组长度是2的幂次。
- 判断数组下标对应的位置，是不是空，如果是空则把new一个entry直接存在该数组位置。
- 如果该下标对应的位置不为空，则需要把new一个entry插入到链表中(JDK 8 是插入链表或者树)。
- 并且还需要判断该链表中是否存在相同的key，如果存在，则更新value，并且返回oldValue。
- 如果是JDK7，则使用头插法
- 如果是JDK8，则会遍历链表，并且在遍历链表的过程中，统计当前链表的元素个数，如果超过8个，则先把链表转变为红黑树.(变为红黑树还有另一个条件:看数组长度是不是达到64 )
- 如果添加成功，size大于加载因子，扩容
HashMap resize()详解
- HashMap的扩容指的就是数组的扩容， 因为数组占用的是连续内存空间，所以数组的扩容其实只能新开一个新的数组，然后把老数组上的元素转移到新数组上来，这样才是数组的扩容
- 在HashMap中也是一样，先新建一个2倍数组大小的数组
- 然后遍历老数组上的每一个位置，如果这个位置上是一个链表，就把这个链表上的元素转移到新数组上去
- 在这个过程中就需要遍历链表，当然jdk7，和jdk8在这个实现时是有不一样的，jdk7就是简单的遍历链表上的每一个元素，然后按每个元素的hashcode结合新数组的长度重新计算得出一个下标，而重新得到的这个数组下标很可能和之前的数组下标是不一样的，这样子就达到了一种效果，就是扩容之后，某个链表会变短，这也就达到了扩容的目的，缩短链表长度，提高了查询效率
- 而在jdk8中，因为涉及到红黑树，这个其实比较复杂，jdk8中其实还会用到一个双向链表来维护红黑树中的元素，所以jdk8中在转移某个位置上的元素时，会去判断如果这个位置是一个红黑树，那么会遍历该位置的双向链表，遍历双向链表统计哪些元素在扩容完之后还是原位置，哪些元素在扩容之后在新位置，这样遍历完双向链表后，就会得到两个子链表，一个放在原下标位置，一个放在新下标位置，如果原下标位置或新下标位置没有元素，则红黑树不用拆分，否则判断这两个子链表的长度，如果不小于6，则转成红黑树放到对应的位置，否则转化为单向链表放到对应的位置。
- 元素转移完了之后，在把新数组对象赋值给HashMap的table属性，老数组会被回收到。
HashMap域
- DEFAULT_INITIAL_CAPACITY = 1 << 4; Hash表默认初始容量
- MAXIMUM_CAPACITY = 1 << 30; 最大Hash表容量
- DEFAULT_LOAD_FACTOR = 0.75f；默认加载因子
- TREEIFY_THRESHOLD = 8；链表转红黑树阈值
- UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值
- MIN_TREEIFY_CAPACITY = 64；链表转红黑树时hash表最小容量阈值，达不到优先扩容。
HashMap重要方法
put(K key, V value)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断是否为空 如果是则new出table //表的懒加载
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果找到的位置是空那么直接建立
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 就去 变红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果已经存有这个key 退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e != null 的意思就是没有遍历到最后就退出循环，也就是有一样的值 就覆盖并且返回 老数字
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//控制访问顺序的函数
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
//控制插入顺序的函数
afterNodeInsertion(evict);
return null;
}
treeifyBin()树化
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果当前Hash表容量小于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 {
//把原来的链表变为一条双向链表
<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);
}
}
resize() 扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//记录老Hash表大小，和 加载因子
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//若老Hash表不是Null
if (oldCap > 0) {
//若超过最大设置容量，不会扩容
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) // 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的 属性
table = newTab;
if (oldTab != null) {
//循环遍历Hash的table
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 {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//遍历 链表,因为扩容后原来的链表会因为hash不一样被拆成2个所以 先成两条链再去添加到新table中去
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;
}
split() 扩容树的分发方式
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//因为我们的书也还是双向链表，循环分两链表
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//如果小于等于6 那么链化
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
//如果有一个是空的 就把另一个直接放入
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
三级目录
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)