hashmap在jdk 1.7之前是数组+链表结构,而jdk1.8之后变为是数组+(链表|红黑树)
树化意义:
树化规则
退化规则
总结:
通常情况下,除非是恶意伪造大量hash相同的元素,否则一般情况下链表长度最长也就是6左右,但是为了应对恶意伪造数据进行攻击的情况,引入了红黑树在链表长度达到指定阈值8时,进行替换;当然,如果此时数组长度没有大于等于64,那么会先尝试通过扩容数组大小来减少链表长度。扩容时,如果某个树的元素个数小于了6,那么红黑树会退化为链表,或者红黑树根节点的左右孩子或者左孙子中有一个为null,也会退化为链表。
传统的BST二叉搜索树需要满足根节点大于左子树小于右子树的条件,并且查询和插入复杂度为0(logn),但是极端情况下二叉搜索树会退化为线性结构,此时查询和插入复杂度变为o(n)。
AVL自平衡二叉树在二叉搜索树的基础上进行了优化,需要满足左右子树的高度差小于等于1,AVL树的最差查询和插入复杂度也为O(logn)。
AVL自平衡二叉树对"平衡"的定义非常严格,在插入和删除非常频繁的场景下,会产生大量的旋转操作,性能会受到很大影响。
红黑树:
1.每个节点非红即黑
2.root节点必须是黑节点
3.null节点会被视为叶子节点,叶子节点必须是黑节点
4.红节点的子节点必须是黑节点
5.新插入的节点是红节点
6.从任意一个节点出发到叶子节点的任意路径上,黑色节点的个数都是相等的
红黑树和AVL树所要求的严格的"平衡"条件不同,红黑树最大允许左右节点数相差一倍(左子树全部都是黑色节点,右子树一红一黑), 红黑树对"平衡"的条件要求不是那么苛刻,因此红黑树在插入和删除节点时,产生的旋转变换操作会更少,性能更高,并且红黑树整体复杂度依然为0(logn);
索引计算方法
hashmap的二次哈希方法中会对key的hashcode进行扰动计算,防止不同的hashcode的高位不同但低位相同导致hash冲突。简单来说,就是为了把高位的特征和低位的特征组合起来,降低哈希冲突的概率,也就是说,尽量做到任何一位的变化都能对最终得到的结果产生影响。
数组容量为何是 2 的 n 次幂
注意
偶数对偶数进行取模得到的结果还是偶数,因此容量为2的n次幂最大的缺点就是hash分布不均匀,因此,如果追求的是更好的hash分散性,应该采用质数作为数组容量; 但是2的n次幂可以提供很多优化特性,追求性能,还是可以考虑的。
1.hashMap是懒惰创建数组的,首次使用时才会创建 2.计算索引(桶下标)–>hashcode–>二次哈希–>与运算 3.如果桶下标没人占用,创建Node占位返回 4.如果桶下标已经被占用了 4.1 已经是TreeNode走红黑树添加或者更新逻辑 4.2 是普通的Node,走连接的添加或更新逻辑 4.2.1 如果链表长度超过树化阈值8,并且当前数组容量是小于64,那么会首先通过扩容,减少链表长度 4.2.2 如果链表长度超过树化阈值8,并且当前数组容器是大于等于64,那么会将链表转换为红黑树,走树化逻辑 5.返回前检查容量是否超过扩容阈值,一旦超过进行扩容
jdk 1.7和jdk1.8的不同:
1.插入节点时,jdk1.7采用头插法,1.8采用尾插法 2…1.7是大于等于阈值并且计算出的索引不是空位的情况下才进行扩容,而1.8是大于阈值就扩容 3. 1.7和1.8在在扩容计算Node索引时进行优化,会通过 hash & oldCap == 0 的元素留在原来位置 ,否则新位置 = 旧位置 + oldCap
hashMap本身并不是线程安全的,所以无论是jdk 1.7 还是 jdk 1.8,都存在并发丢失数据的风险:
如果存在两个并发线程1和2都同时向hashmap中put一对键值对,并且key计算出来的hash值都是相同的,那么线程1和线程2同时来到判断索引位是否为空的逻辑,发现为空,填充数据,此时就存在线程2覆盖线程1的数据导致丢失数据的风险。
1.7 源码如下:
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
第一次循环
第二次循环
第三次循环
总结: 由于jdk 1.7的hashmap采用的是头插法,所以当存在两个并发线程同时尝试对hash数组进行扩容时,会出现线程1先扩容完毕,将原本的元素A指向B顺序,颠倒为B指向A。而由于线程2无法感知该变化,因此依然按照A指向B的顺序迁移元素到新数组,最终会产生a指向b,b指向a的死链。
key 的设计要求
如果 key 可变,例如修改了 age 会导致再次查询时查询不到
public class HashMapMutableKey {
public static void main(String[] args) {
HashMap<Student, Object> map = new HashMap<>();
Student stu = new Student("张三", 18);
map.put(stu, new Object());
System.out.println(map.get(stu));
stu.age = 19;
System.out.println(map.get(stu));
}
static class Student {
String name;
int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return age == student.age && Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}
}
String 对象的 hashCode() 设计