一、关键属性
1.静态属性
/**
* HashMap的默认初始容量
* 1 << 4相当于2的4次方,即16,因为位运算效率高,所以如此写
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* HashMap的最大容量
* 1 << 30相当于2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表转红黑树的阈值
* 当链表长度达到8时,转化为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 红黑树转链表的阈值
* 当红黑树的节点数达到6时,退化为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 最小树形化容量
* 当数组容量达到64时,转化为红黑树
*/
static final int MIN_TREEIFY_CAPACITY = 64;
2.非静态属性
/**
* 存放数据的数组
*/
transient Node<K,V>[] table;
/**
* 存放元素的个数
*/
transient int size;
/*
* modCount:记录当前集合被修改的次数
* (1)添加
* (2)删除
* 这两个操作都会影响元素的个数。
*
* 当我们使用迭代器或foreach遍历时,如果你在foreach遍历时,自动调用迭代器的迭代方法,
* 此时在遍历过程中调用了集合的add,remove方法时,modCount就会改变,
* 而迭代器记录的modCount是开始迭代之前的,如果两个不一致,就会报异常,
* 说明有两个线路(线程)同时操作集合。这种操作有风险,为了保证结果的正确性,
* 避免这样的情况发生,一旦发现modCount与expectedModCount不一致,立即保错。
*
* 此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的:
* 在创建迭代器之后,除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改,
* 否则在任何时间以任何方式对列表进行修改,
* 迭代器都会抛出 ConcurrentModificationException。
* 因此,面对并发的修改,迭代器很快就会完全失败,
* 而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
*/
transient int modCount;
/**
* 阈值
* 初始容量默认为16,为table分配内存空间后,threshold一般为capacity*loadFactory
* HashMap在进行扩容时需要参考threshold
* 初始化时阈值等于容量,当放入第一个元素后,重新计算阈值,新的阈值=容量*负载因子
*/
int threshold;
/**
* 负载因子,代表着table的填充程度
* 加载因子越大,填满的元素越多
* 好处:空间利用率高了;
* 坏处:冲突的机会加大了,链表长度会越来越长,查找效率降低;
* 加载因子越小,填满的元素越少
* 好处:冲突的机会减小了;
* 坏处:空间浪费多了,表中的数据将过于稀疏(很多空间还没用,就开始扩容了);
* 所以就是时间和空间之间的抉择;不过一般我们用默认的0.75f就好了;
*/
final float loadFactor;
二、hash方法
/**
* 如果key是空的话,就放在table下标是0的位置上,所以HashMap是允许key是空的
* h = key.hashCode() 是key对象的hashCode
* h >>> 16 是把h无符号右移16位
* 相当于key的hashCode无符号右移16位之后再与自己异或
* 我们知道这么做的目的是为了让低16位更有散列性,但是为什么不用“与运算”,“或运算”呢?
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
0 1 1 0
0 1 0 1
---------------
与 0 1 0 0 两个都是1,结果是1,其他情况是0
或 0 1 1 1 有1结果就是1,其余是0
异或 0 0 1 1 两个相同,结果是0,不相同结果是1
可以看出来,“与运算”结果更倾向于0,“或运算”结果更倾向于1,只有“异或运算”0和1的概率是一样的,所以异或运算的散列效果更好
总的来说,“与运算”的结果趋向于得到小的值,“或运算”的结果趋向于得到大的值,异或运算的结果大小值比较均匀分散
三、tableSizeFor方法
/**
* 因为HashMap的容量必须是2的整数幂,这个方法是找到大于等于cap最大的2的整数幂
* 如cap等于10,返回16; cap是25,返回32
*
* 2的整数幂用2进制表示其实就是最高有效位为1,其余全是0
* 如8的2进制: 1000; 32的2进制: 100000
*
* 所以对任意十进制数转换为2的整数幂,结果是这个数本身的最高有效位的前一位变成1,
* 最高有效位以及其后的位都变为0;
*
* 所以思路就是先将最高有效位以及其后的位都变为1,然后再+1,就进位到前一位变成1,
* 其后所有的满2变0,所以关键是如何将最高有效位后面都变为1;
*/
static final int tableSizeFor(int cap) {
//之所以在开始移位前先将容量-1,是为了避免给定容量已经是8,16这样2的幂时,
//不减一直接移位会导致得到的结果比预期大,比如预期16得到应该是16,
//直接移位的话会得到32。
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//判断n小于0的话,就按1算,超过最大容量,按最大容量算,其他情况+1,因为一开始减了1
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
下面举例说明位移后或运算,X表示可能是0或者1
1xxxxxxxxxxxxxxxxxxxxxxxxxxx
第一次右移 01xxxxxxxxxxxxxxxxxxxxxxxxxx
或运算之后 11xxxxxxxxxxxxxxxxxxxxxxxxxx
第二次右移 0011xxxxxxxxxxxxxxxxxxxxxxxx
或运算之后 1111xxxxxxxxxxxxxxxxxxxxxxxx
第三次右移 00001111xxxxxxxxxxxxxxxxxxxx
或运算之后 11111111xxxxxxxxxxxxxxxxxxxx
第四次右移 0000000011111111xxxxxxxxxxxx
或运算之后 1111111111111111xxxxxxxxxxxx
第五次右移 0000000000000000111111111111
或运算之后 1111111111111111111111111111
可以看到,不管x是多少完成5次“右移”和“或运算”之后,最高有效位及其后的位都变成了1,这时候只要加上1,就会得到2的整数幂,只不过在int值较小的时候,后面几次的位移是多余的
四、构造方法
public HashMap();
public HashMap(int initialCapacity);
public HashMap(int initialCapacity, float loadFactor);
//HashMap的实现中,通过threshold字段来判断HashMap的最大容量;
//threshold = capacity * loadFactor;
五、getNode方法
final Node<K,V> getNode(int hash, Object key) {
//将哈希表赋值给tab
Node<K,V>[] tab;
//通过hashCode和数组长度取模,找到对应下标数组的第一个节点
Node<K,V> first;
//当前节点的下一个节点
Node<K,V> e;
//hash表长度
int n;
//当前节点的key
K k;
/**
* 将哈希表赋值给tab然后判断是否为空
* &&将哈希表的长度赋值给n判断是否大于0
* &&通过hashCode和数组长度取模,找到对应下标数组的node赋值给fisrt然后判断不为空
*
* 因为n是2的整数幂,所以 (n-1) & hash 等同于 hash % n (即hash除以n的余数)
*/
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
/**
* 拿到第一个结点(first)的hash值和key,跟传入的hash值和key作比较,如果相同返回first结点
*/
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
/**
* 该索引下面存储多个节点的情况下:将first的下一个结点赋值给e,判断e是否为空
*/
if ((e = first.next) != null) {
//判断是链表还是红黑树
if (first instanceof TreeNode)
//如果是红黑树,调用红黑树的查找方法
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果是链表,遍历该节点下面的所有结点
do {
//判断当前节点的hash和key是否和传入的相同,相同就返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//如果没找到,就返回null
return null;
}
下面详细将一下取模方法为什么不用 hash % n,而用 (n - 1) & hash
假如n = 4, hash = 11
我们将n和hash转成2进制
11 1011
4 0100
4-1 0011
11&(4-1) 0011
11的二进制最高位的1代表的是十进制的8,而我们知道长度n一定是2的整数幂,那么高位一定可能整除低位,就像例子中的8一定可以整除4,那么可以将高位舍弃掉,取模相当于就是将低位取出来,而n是2的整数幂,减1之后刚好可以得到全是1的二进制数,而“与运算”的特性是&1得到自己,那就正好可以将低位的数取出来
六、putVal方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//将哈希表赋值给tab
Node<K,V>[] tab;
//用于赋值通过hashCode和数组长度取模之后找到的节点
Node<K,V> p;
//hash表长度
int n;
//存放hashCode和数组长度取模后得到的数组下标
int i;
if ((tab = table) == null || (n = tab.length) == 0)
//赋值tab和n,判断table如果是空的,调用resize方法初始化
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//如果要插入的数据所在的位置为空
//创建一个新的数据,这个数据没有下一条,并将数据放到当前这个位置
tab[i] = newNode(hash, key, value, null);
else {
//如果要插入的数据所在的位置有内容
//当前节点的下一个节点
Node<K,V> e;
//当前节点的key
K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//对比hash和key,如果都相同,就替换
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) {
//如果当前节点的下一个是空的,就代表没有后面的数据了
//创建一个新的node,放到当前节点的下一个节点
p.next = newNode(hash, key, value, null);
//判断链表长度是否超过了阈值,如果超过了,调用treeifyBin转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//如果当前遍历到的数据和要插入的数据的key是一样,跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//如果值不一样,就将下一个节点赋值给当前节点,继续循环
p = e;
}
}
if (e != null) {
//如果当前节点不为空,覆盖内容
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//替换值
e.value = value;
//空方法
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//增加修改次数
++modCount;
if (++size > threshold)
//如果长度超过阈值,就扩容
resize();
//空方法
afterNodeInsertion(evict);
return null;
}
七、resize方法
final Node<K,V>[] resize() {
//旧的table
Node<K,V>[] oldTab = table;
//旧table的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧table的阈值
int oldThr = threshold;
//新table的长度和阈值
int newCap, newThr = 0;
//旧容量大于0
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//如果旧容量大于等于了允许的最大值,赋值为int最大值
threshold = Integer.MAX_VALUE;
//因为不会再扩容了,所以返回旧table
return oldTab;
}
// << 1相当于扩容为原来的2倍,如果扩容后的容量比最大值小,且旧容量大于等于初始化容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新的阈值为旧的阈值的2倍
newThr = oldThr << 1;
}
//旧容量不大于0,说明旧table是空的,再判断旧的阈值大于0
else if (oldThr > 0)
/**
* 将旧阈值作为新容量,因为此时的阈值就是容量(初始化时阈值等于容量)
* 所以直接将原阈值赋值给新容量
*/
newCap = oldThr;
else {
/**
* 如果原容量不大于0,并且原阈值也不大于0,说明调用的无参构造方法,还没有完全初始化
* 只有在put数据时才完成全部初始化
*/
//默认容量作为新容量
newCap = DEFAULT_INITIAL_CAPACITY;
//默认容量*负载因子作为新阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//原容量不大于0且旧阈值大于0
if (newThr == 0) {
//临时阈值 = 新容量 * 负载因子
float ft = (float)newCap * loadFactor;
//如果新容量和阈值都小于最大容量就用临时阈值作为新阈值,否则就用int最大值作为新阈值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将新的阈值赋给threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//按照新的容量创建新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将新建的数组赋给table
table = newTab;
if (oldTab != null) {
//旧的table里还有值,需要取出放到新的table中,遍历旧table
for (int j = 0; j < oldCap; ++j) {
//当前节点
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//如果旧table中有值,先置为null,方便gc
oldTab[j] = null;
//如果下一个位置是空的,说明后面没有连着链表或红黑树,只有一个节点
if (e.next == null)
//用hash和新table的长度取模获取在新table的数组下标,并赋值
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;
do {
//开始遍历
next = e.next;
//判断位置是否发生变化
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
/*
其实if 和else 中做的事情是一样的,本质上就是将不需要更新位置的节点加入到loHead为头节点的低位链表中,将需要更新位置的节点加入到hiHead为头结点的高位链表中。
我们看到有loHead和loTail两个Node,loHead为头节点,然后loTail是尾节点,在遍历的时候用来维护loHead,即每次循环,更新loHead的next。我们来举个例子,比如原来的链表是A->B->C->D->E。
我们这里把->假设成next关系,这五个Node中,只有C的hash & oldCap != 0 ,
然后这个代码执行过程就是:
第一次循环: 先拿到A,把A赋给loHead,然后loTail也是A
第二次循环: 此时e的为B,而且loTail != null,也就是进入上面的else分支,把loTail.next = B,此时loTail中即A->B,同样反应在loHead中也是A->B,然后把loTail = B
第三次循环: 此时e = C,由于C不满足 (e.hash & oldCap) == 0,进入到了我们下面的else分支,其实做的事情和当前分支的意思一样,只不过维护的是hiHead和hiTail。
第四次循环: 此时e的为D,loTail != null,进入上面的else分支,把loTail.next = D,此时loTail中即B->D,同样反应在loHead中也是A->B->D,然后把loTail = D
*/
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//遍历结束,即把table[j]中所有的Node处理完
//如果loTail不为空
if (loTail != null) {
//此时把loTail的next置空,将低位链表构造完成
loTail.next = null;
//把loHead放在newTab数组的第j个位置上
//也就是这些节点保持在数组中的原位置不变
newTab[j] = loHead;
}
//同理,只不过hiHead中节点放的位置是j+oldCap
if (hiTail != null) {
hiTail.next = null;
//hiHead链表中的节点都是需要更新位置的节点
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//最后返回newTab
return newTab;
}
扩容的流程图如下:
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/154523.html