前言
网上有很多HashMap的视频和一大堆HashMap的文章，所以，今天这篇文章我并不打算从头过源码(只看1.8的)，而是带着问题去带你深入了解HashMap。
需求
设计一个用户信息记录，key是手机号码后5位，value是该用户的信息资料。现在要求添加、删除、搜索的复杂度都是o(1)。
- 我们可以这么做
private Person[] persons=new Person[100000];
public void add(int phone,Person person){
persons[phone]=person;
}
public void remove(int phone){
persons[phone]=null;
}
我们会发现一个严重的问题，空间浪费太大，使用率低
image.png
- 既然这样我们是不是可以将索引进行一定计算，将其转成比较小的值。这就可以使用到Hash表
哈希表(Hash Table)的实现者——HashMap
Hash表也叫做散列表，那么它是如何实现高效的处理数据的？
image.png
利用Hash计算将key生成数组对应的index(索引),然后就可以根据index进行定位数组元素
HashMap底层结构
数组+链表+红黑树
image.png
上面图片我们看出，当两个hash值一样的时候，就会出现hash碰撞。
为什么链表是将数据添加到尾而不是头？
比如这时候已经存在一个链表数据Node<String,Value> A，我们把数据B加入的时候,首先需要和A进行判断，判断的时候指针会进行后移。如果key一样就覆盖，但是如果不一样就添加到尾部。
怎么解决Hash碰撞
HashMap处理方式是添加元素的时候，将数据以链表的形式存储。当链表的大小大于等于9并且哈希表的容量>64的时候会将链表转成红黑树，而当红黑树的大小小于6的时候又会转成链表
哈希表中哈希函数的实现步骤
- 1、先生成整数型的key的哈希值
- 2、再让key的哈希值与数组大小进行相关运算，生成索引值(数组的长度是2的幂次方)
hash(key) % (table.length );
为提高运算&可以替代%运算
hash(key) & (table.length - 1);
&:全是1为1，反之为0
- 为什么数组的长度需要是2的幂次方
如：2^2 -1实际二进制是11，2^3-1的二进制是111 ，2^4 -1=1111 。此时数据11001010(202)&1111和11001100(204) &1111的结果如下
| 11001010 | 11001100 |
|---|---|
| &1111 | &1111 |
| 1010 | 1100 |
我们会发现我们结果一定会小于1111也就是我们的数组的大小，而且我们会发现 202%16 =202&15，也就是说，hash(key)& (table.length - 1)==hash(key)%table.index
如何生成key的哈希值
key的种类
整数，浮点数，字符串，自定义对象
不同的种类生成的hash值方式不一样，但是目的都是尽量让每个key的hash值不一样，且尽量让所有信息参与运算
- 整数的hash值
因为是int类型，所以可以直接拿int当作hash值
我们可以直接看Integer的源码
public int hashCode() {
return hashCode(this.value);
}
- 浮点数的hash值
直接看源码
Float
public static int hashCode(float var0) {
return floatToIntBits(var0);
}
Double
public static int hashCode(double var0) {
long var2 = doubleToLongBits(var0);
return (int)(var2 ^ var2 >>> 32);
}
- long类型的hash值
public static int hashCode(long var0) {
return (int)(var0 ^ var0 >>> 32);
}
关于>>> 和^的作用:
^表示异或，相同为0，不同为1而>>>表示无符号位移
我们都知道，long和doublue都是64位的，那么>>>32再^则表示64位的数据的高位32位和低位32位进行异或处理，以达到充分利用所有信息计算出hash值
| value | 1111 1111 1111 1111 1111 1111 1111 1111 1011 0110 0011 1001 0110 1111 1100 1010 |
|---|---|
| value>>>32 | 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 1111 1111 1111 1111 |
| value^value>>>32 | 1111 1111 1111 1111 1111 1111 1111 1111 0100 1001 1100 0110 1001 0000 0011 0101 |
- String的hash值怎么计算
字符串是由若干个字符组成的 ,每个字符本质就是一个整数，可以进行计算
如字符串jack的哈希值可以表示为 j ∗ n^3 + a ∗ n^2 + c ∗ n^1 + k ∗ n^0，等价于 [ ( j ∗ n + a ) ∗ n + c ] ∗ n + k
在jdk中这个n是31，那么为什么是31呢?
- 31是个奇偶数，因为它只能被1和本身除。而且它符合2^n - 1
- 素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突
- 不用17是因为1-20的数较小，会增加hash值的冲突
自定义对象作为 key，最好同时重写 hashCode 、equals 方法
- 1、如果不重写hashCode，默认复写的是内存地址的hashCode
- 2、equals默认比较的是内存地址是否相等
- 3、如果之重写hashCode,如下面代码
@Override
public int hashCode() {
return age/10;
}
这时候我们在年龄是0-19这个年龄端，他们的值都是0，也就是说hash值一样，那么在HashMap中这时候并不知道，是添加链表的尾部，还是直接覆盖当前的值
- 4、同理，如果只复写了equals，HashMap并不保证，当前hash值一样，如果hash值都不一样，也就没有判断一说
一些代码问题分析
1、为什么h要先>>>16位
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先，我们知道int是4字节，总共32位，那如果>>>16位是不是和刚才long>>>32位情况一样，都是保证key高位和低位进行异或运算
2、默认加载因子为什么是0.75？
static final float DEFAULT_LOAD_FACTOR = 0.75f;
假设该值为0.5,则每次当大于数组的长度的一半的时候都会扩容，这样就相当于每次有一半的空间浪费了,但是查询效率会比较高
那如果该值为1，我们会发现空间利用率最大，但是查询效率会比较低
- 下面代码表示大于8的时候才转成红黑树而不是大于等于8
static final int TREEIFY_THRESHOLD = 8;
- 下面代码表示为6红黑树转成为链表
static final int UNTREEIFY_THRESHOLD = 6;
一些代码分析
put源码
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)//1
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//2
tab[i] = newNode(hash, key, value, null);
else {//3
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);//4
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
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;
}
}
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;
}
- n 是数组的长度，我们之前说了，n是2的幂次方
- p = tab[i = (n - 1) & hash]我相信大家也知道了，实际就是根据index获取到节点。如果为空则创建一个根节点
- 当我们发现有节点了，就会进入注释3这步
1、如果hash值一样，并且如果key相等，则直接替换
2、如果hash值或者key不相等，则判断是不是TreeNode，是则会进入到注释4（待会解释）
3、for循环实际就是判断是否转成红黑树,bigCount和链表相差2，假设binCount为3，则链表为5，所以当bigCount>=7的时候链表的数量是9,treeifyBin需要注意这行代码
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//数组的大小小于64
分析注释4的代码
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
上面的代码主要做的就是:
首先两个hash需要判断是否相等，随后赋值，赋值的目的是后面遍历，如果小于则节点向左查询，大于则向右查询，如果key相等则直接返回。如果不相等，则判断是否就有可比较性，并且没有进行扫描过，则随后进行左右子树扫描查询，如果找到直接返回，找不到则根据内存地址大小决定是向左还是向右
查找节点的代码分析
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}`
1、如果判断的hash大于根节点的hash则向左搜索，如果小于则向右搜索，如果key相等则直接返回
2、p1等于null则表示左子树为空，向右搜索
3、pr为空，则表示右子树为空，向左搜索
4、左右子树都不为空那个，则判断是否具有可比较性，如果有，则判断进入左子树还是右子树
5、如果不具有可比较性，则向右子树搜索
6、如果右子树找不到，则向左子树搜索
最后
因为hashMap设计的东西，一篇文章不可能全部涉及到，希望对大家有所帮助。
网友评论