JDK版本:1.8
首先我们看HashMap的类图
类图
源码中涉及到大量的位运算符 我们复习下:
&(与)运算符：全真为真
1&1=1 , 1&0=0 , 0&1=0 , 0&0=0
public static void main(String[] args) {
//5的二进制表示为 0101
//3的二进制表示为 0011
//&运算的结果应为 0001 对应1
System.out.println(5&3);
}
结果:
1
|(或) 运算符: 一真为真
1 | 1=1，1 | 0 =1，0 | 0 =0，0 | 1 =1
public static void main(String[] args) {
//8的二进制表示为 1000
//9的二进制表示为 1001
//|运算的结果应为 1001
System.out.println(8|9);
}
结果:
9
^（异或）:不同为真
public static void main(String[] args) {
//8的二进制表示为 1000
//9的二进制表示为 1001
//^运算的结果应为 0001
System.out.println(8^9);
}
结果:
1
阅读HashMap源码我们要秉承一个精神:
元素分布要符合散列性，啥叫散列性，读完源码后我的理解就是【雨露均沾】
HashMap源自于Map接口
我们还是从构造函数开始了解,无参构造:
HashMap()
public HashMap() {
/**
* HashMap的元素数量
*/
transient int size;
/**
* 无参构造函数中默认的负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 负载因子 为什么会有一个负载因子存在 此处涉及到HashMap的扩容方式
* 我们知道ArrayList在添加时需要判断size的大小是否合适
* 而HashMap在扩容时多了一个条件:size * loadFactor,目前这个负载因子为0.75f，假如size为100，那么
* 100*0.75=75 HashMap容量到达75时就需要进行扩容，明明没有装满 但是却需要增加容量，这是为啥
* 我们先记着
*
*/
final float loadFactor;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 默认负载因子为0.75f
}
一头雾水，一个空的构造函数只是初始化了一个负载因子，其他什么事都没做，这不得不让我们先看看添加时到底做了什么操作
put(key,val)
public V put(K key, V value) {
//将key做了一次hash运算，然后把运算结果作为参数传给了PutVal方法
return putVal(hash(key), key, value, false, true);
}
//Hash运算
static final int hash(Object key) {
int h;
//首先h =key.hashCode() 得到一个整型值
//将整型的值 异或 整型值右移16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
......
......
}
这个put方法辣么复杂，我们暂且不去分析，但是从putVal方法中仿佛也看到了关键的信息，所有的操作都和table这个数组有关
//定义一个Node数组
transient Node<K,V>[] table;
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
//元素key对应的hash值 其实就是一个整型
final int hash;
//Key的值
final K key;
//Value的值
V value;
//下一个Node元素 经历过链表结构 这个就非常熟悉了 它是单向链表
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;
}
下面我们尝试描述这个存储结构:一个链表的数组
HashMap
它是一个数组，每个数组里的元素类型是一个单向链表
元素的属性包含 hash、key、value和一个指向下一个元素的next
搞出这样的一个数据结构有什么优势呢
我们知道 数组在访问元素时很快，快是因为他通过下标去找元素，时间复杂度为O(1);这让HashMap在查找元素时会很快，但是添加元素确有所不同
很明显HashMap并不是像ArrayList Add元素时那样 连续添加，而是以一种力求均匀的随机添加，好像烤羊肉串撒调料一样，尽量均匀，咸淡才适当
那么怎么样的算法是一种均匀的算法咧
putVal方法给我们的指示如下:
public V put(K key, V value) {
//将key做了一次hash运算，然后把运算结果作为参数传给了PutVal方法
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;
if ((p = tab[i = (n - 1) & hash]) == null) //这里是重点这里是重点这里是重点
tab[i] = newNode(hash, key, value, null);
else {
......
......
}
均匀的算法源码写的是:
①HashMap中的hash()方法封装泛型本身的hash值
②将hash()方法得到的hash值 & 数组的Size-1
(n-1) & hash
我们先看这个hash是个什么东西
随便看几个数的Hash值:
public static void main(String[] args) {
String hashStr1 ="a";
System.out.println(hashStr1.hashCode());
String hashStr2 ="A";
System.out.println(hashStr2.hashCode());
String hashStr3 ="ddf";
System.out.println(hashStr3.hashCode());
Integer hashInt1 =1;
System.out.println(hashInt1.hashCode());
Integer hashInt2 =1024;
System.out.println(hashInt2.hashCode());
}
结果是:
97
65
99302
1
1024
单个英文字符是ASCCII码，而整型数字为它自己本身，一个字符串的HashCode是一个比较大的整数值 。
一般我们使用字符串作为键值时比较多，我们回过头来看HashMap针对hash也有一套自己的逻辑:
public V put(K key, V value) {
//将key做了一次hash运算，然后把运算结果作为参数传给了PutVal方法
return putVal(hash(key), key, value, false, true);
}
//Hash运算
static final int hash(Object key) {
int h;
//首先h =key.hashCode() 得到一个整型值
//将整型的值 异或 整型值右移16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashcode =hashcode ^ hashcode >>>16
既然都将hashCode的实现交给具体的类型了，为什么还要进行右移16位呢，我们做个实现 就拿"ddf"对应的hashcode 99302做试验:
99302的二进制和99302右移后的结果做 "异或"（因为一个整型是4个字节 最大一共32位 我们把位都写齐了）:
0000 0000 0000 0001 1000 0011 1110 0110
^
0000 0000 0000 0000 0000 0000 0000 0001
=
0000 0000 0000 0001 1000 0011 1110 0111
结果为99303 这一通不明所以的操作也没看懂，我们先提前预知一些指示帮助理解:
问:我想让一个比较大的数(就像99302) 按照一定的规则转换为 一个比较小的数(目的是算出数组的索引位置)，比如99302这个数 我想让它按照一定规则转换成小于8的数，方案是什么？
答:用99302除以8 取余数 因为余数一定小于8
这个小于8的数其实就是HashMap根据hashcode计算索引的原理，只不过他用了一个性能更加牛逼的位运算
tab[i = (n - 1) & hash])
这里可能会引起一些小朋友的质疑，这个hash值"与"上数组的长度减一的操作，结果一定会和计算取余的操作 结果保持一致吗，根据李永乐老师的经验，一个东西有没有效果,我们需要做对比试验
99302%31=9 99302 & (31-1)=6 ×
99302%11=5 99302 & (11-1)=2 ×
99302%20=2 99302 & (20-1)=2 ×
99302%16=6 99302 & (16-1)=6 √
这几组数据中，只有99302 和 16可以形成 99302%16 == 99302 & (16-1)这个条件，而 16-1=15,15对应的二进制为:
0000 0000 0000 0000 0000 0000 0000 1111
运算过程如下:
0000 0000 0000 0001 1000 0011 1110 0110
&
0000 0000 0000 0000 0000 0000 0000 1111
=
0000 0000 0000 0000 0000 0000 0000 0110
做 & 运算时，全1为1 也就是99302对应的二进制
0000 0000 0000 0001 1000 0011 1110 0110
中前24位都被干掉了,我们留住的是99302的低4位 "0110" 正好为6,这个并不是巧合
这个16恰为数组的长度，要想 (长度-1)对应的二进制能保证和 hashCode &运算后结果的低x位的值不变，这个长度只能是
像以下这种刚好进位的数，也就是2的n次方
0000 0000 0000 0000 0000 0000 0000 0001
0000 0000 0000 0000 0000 0000 0000 0010
0000 0000 0000 0000 0000 0000 0000 0100
0000 0000 0000 0000 0000 0000 0000 1000
0000 0000 0000 0000 1000 0000 0000 0000
喔，数组的长度需要是二的N次方，能保证&运算计算索引位置速度的最大化
但是，这样的计算方式不够哈希(可以看下String这个包装类型实现的hashcode方法，里面用了一个字符串的每一个字符去做了运算 计算出来了hash值),原因是取余运算(与运算)计算数组索引时造成的
但是我们这个 & 操作 仅仅大概率上使用了 hashcode的 低16位去做了运算，
PS:低16位就能造出来至少2的16次方 65536 大小的数组 一般数组我们用不到这么大，导致
hashcode的高16位更没有参与运算
于是我们看到了这个骚操作:
//因本身的hashcode不够hash，在取余运算(与运算时)不够hash，因此我们决定再算一遍 这也是够
//任性了
static final int hash(Object key) {
int h;
//首先h =key.hashCode() 得到一个整型值
//将整型的值 异或 整型值右移16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我将自己的高16位和自己的低16位相互"异或":再去让他们做取余(与运算) 这样的结果才够hash!
举一个分蛋糕的例子:
一个蛋糕要分给20个人，但是问题是蛋糕被放在一个屋里，屋里只有10个座位，每次只能有10个人进去讨论如何分蛋糕
也就是每次分只有10个人可以发表意见，屋外一直会有10个人不能发表意见，
为了公平起见，大家决定进屋里的10个人先和外面10个人交换意见，再走进屋里分蛋糕。
PS:这里可能会有小朋友问了，为啥用的是异或而不是& |呢，因为 位运算符一共是我们上面介绍的三种:
& 运算符倾向于计算结果为0
| 运算符倾向于计算结果为1
^ 运算符看命 比较中庸
以上大段解决了两个问题:
①hash方法中为什么存在 右移16位的操作
②为什么 (n - 1) & hash 可以代替 直接取余的操作
③为什么数组的长度都是2的N次方
这个问题卡了我们这么久，继续往下看putVal方法:
//hashmap的添加操作
//参数分别为 右移16位后的hash值
//键
//值
//false
//true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab获取table属性 p代表索引对应的Node节点 n代表数组的长度 i是算出来的索引
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果为空数组 则进行扩容 空数组扩容 初始长度为16
if ((tab = table) == null || (n = tab.length) == 0)
//首次扩容长度为16
n = (tab = resize()).length;
//判断索引位置是否已经被占用
if ((p = tab[i = (n - 1) & hash]) == null)
//如果没被占用则创建一个新节点
tab[i] = newNode(hash, key, value, null);
else {
//说明索引位置已经有一个Node
Node<K,V> e; K k;
//判断存在的Node对应的hash值 键值是否相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果相等 将其取出
e = p;
//如果p节点不为空并属于树形结构 则按照树形结构规则添加值
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//非树形结构并且 对应的key不同(比如扩容时挪过来的key) 开始计算
for (int binCount = 0; ; ++binCount) {
//如果当前节点的下一个节点为空
if ((e = p.next) == null) {
//创建新的节点
p.next = newNode(hash, key, value, null);
//判断链表的长度是否大于 一个阈值 -1
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//大于阈值则进行类型转换 将链表节点转换为红黑树
treeifyBin(tab, hash);
break;
}
//判断p.next节点的Node对应的hash值 键值与新节点是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果相等 跳出循环
break;
//将node节点下移一位 继续循环
p = e;
}
}
//替换已存在的节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent是false 我传了false 意思是替换此节点
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//此处可以理解成一个空方法
afterNodeAccess(e);
//如果是修改的话 直接返回 并且不动修改次数和size啥的
return oldValue;
}
}
//增加修改次数
++modCount;
if (++size > threshold)
//如果size要超了 继续扩容
resize();
//此处可以理解成一个空方法 为后来者预留接口
afterNodeInsertion(evict);
return null;
}
总结:
①首次添加需扩容
②非首次添加需判断是否发生hash冲突，如果有冲突，则修改或继续添加链表的节点
添加或修改链表节点时，如果超过一个阈值 链表转换为红黑树，为啥要转红黑树捏，因为我们知道链表的 查询时间复杂度为O(n),数目大了查询慢，jdk7就没有转红黑树的过程
树这个东西得单独拿出来再去写
这里就先这么一说，后面在这里补传送门
我们把扩容的resize()方法过一遍:
final Node<K,V>[] resize() {
//获取当前数组 首次扩容table为null
Node<K,V>[] oldTab = table;
//获取老数组的容量 也就是length 首次扩容为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取老数组的阈值 首次threshold为0
int oldThr = threshold;]
//新的容量 和新的扩容阈值
int newCap, newThr = 0;
if (oldCap > 0) {
//老数组不为空 且数组长度大于2的30次方
if (oldCap >= MAXIMUM_CAPACITY) {
//更新阈值
threshold = Integer.MAX_VALUE;
//没有扩容 直接返回
return oldTab;
}
//老数组长度的2倍小于2的30次方且大于16 (非首次扩容)
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//扩容阈值乘以2
newThr = oldThr << 1; // double threshold
}
//调用了那个非空 可初始化容量的构造函数时 就用调用者自带的容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//空构造走这个case
else {
//newCap =16
newCap = DEFAULT_INITIAL_CAPACITY;
//newThr =16*0.75 =12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//补漏 如果新阈值没有 则默认给newCap*loadFactor
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 = newTab;
//下面将老数组的值挪到新数组来
if (oldTab != null) {
//遍历老数组
for (int j = 0; j < oldCap; ++j) {
//定义中间变量
Node<K,V> e;
//节点非空时 给到中间变量e
if ((e = oldTab[j]) != null) {
//老节点置空 让GC干活儿
oldTab[j] = null;
//老的Node 就自己一个节点
if (e.next == null)
//将老的值选一个新的位置并存入扩容后的数组
newTab[e.hash & (newCap - 1)] = e;
//老节点时一个树类型
else if (e instanceof TreeNode)
//红黑树警告
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//老节点链表数量大于1
else {
//定义原索引位置头结点尾节点 头节点只是为了最后为数组某位置赋值时方便记录 尾节点用于计算
Node<K,V> loHead = null, loTail = null;
//定义新索引位置(元索引+老数组容量)
Node<K,V> hiHead = null, hiTail = null;
//下一个节点
Node<K,V> next;
do {
//指向链表的下一个元素
next = e.next;
//&操作是倾向于0的 这里的结果不是0就是oldCap，此处把链表分为两种
//一种放在数组的原位置
//另一种放在当前索引+老容量的位置，让扩容后的分布更加均匀 这里肯定可以忽略向红黑
//树的转换逻辑 因为扩容前属于
//树节点的 扩容后依旧是树节点，也就是目前的变量最多为7次
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) {
//让gc干活儿
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
总结:某个数组Node较长时扩容需要将此链表进行拆分，将拆出来的链表放到新的位置
扩容也将hash的散列性考虑了进去,一个原则:
扩容也符合散列 也要够Hash
折腾了这一大通，只是因为我们在构造函数里啥也没看出来，现在，我们综合上面的分析，来看看这个空构造函数初始化的DEFAULT_LOAD_FACTOR有什么用
首先它是一个浮点型:
static final float DEFAULT_LOAD_FACTOR = 0.75f;
这个0.75f和扩容的阈值有关
threshold =DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY;
也就是
threshold =0.75*16=12
咱的HashMap初始容量大小是16 为什么到了12个元素时就需要进行扩容呢 我们看三个例子:
假设 初始容量是8 当我们把 LOAD_FACTOR定为 1时:
阈值 =8 乘以 1 等于8
相当于长度为8的数组要盛放8个元素
它的结构可能为以下两个状态:
理想状态:索引位置全部沾满 概率较小
状态1
常规状态:部分索引位置沾满
状态2
状态1是理想的情况，hash分布均匀,get元素时 时间复杂度为O(1)
状态2是常态，get元素时可能会遭遇从链表中获取 时间复杂度为O(n)
调整LOAD_FACTOR为4
阈值为8 乘以4等于32
相当于长度为8的数组要盛放32个元素
可能会出现以下状态:
理想状态:
理想状态
常规状态:
部分结构会转为红黑树这里不做讨论
PS:这图画的我有点不好了....
这样的数据结构可能会省下一定的空间 但根本不是我们想要的，因为他在索引上会浪费数组的优势
调整LOAD_FACTOR为小于1的数我们就不做讨论了
我们能总结出来一个结论:
负载因子的存在能让我们在空间和时间上去权衡一个HashMap的效率，LOAD_FACTOR大于1更能利用空间而执行效率较低，而LOAD_FACTOR小于1则是冗余的使用一些空间执行效率较高
看完了空构造函数和add方法 我们看下get方法的源码:
get(key)
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) {
//定义tab来取table数组 first是 hash值算完某索引上的元素
//e是某索引的元素的next节点
//n是tab的lenth
//k是某个key的hash值
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) {
//判断找的元素是否为首个Node
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//如果是则返回
return first;
if ((e = first.next) != null) {
//判断首个Node是否是树结构
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;
}
整个过程在我们阅读完添加后 还是比较明朗的
1.计算索引取出Node
2.比较Node的hash值与查找的hash值
3.遍历链表或者红黑树继续查找
remove(object)
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;
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;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//上面除了变量名字不同 基本逻辑都是按照get()来的
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
//如果删的元素恰好是首元素 则将首元素的next元素赋给索引位
tab[index] = node.next;
else
//非首元素则将p的next节点指向p 找到的元素的next节点
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
1.找到要删除的元素
2.替换元素
网友评论