无知的我终于深入接触到了HashMap。。。。
如果有遇到有任何无法进展问题或者疑惑的地方，应该在讨论区留言 或者 其他途径以寻求及时的帮助，以加快学习效率 或者 培养独立解决问题的能力、扫清盲点、补充细节
历程
存储机制
好处就是 能够实现快速查找。这是因为“a”与存储到的数组位置一 一对应
缺陷就是 不同的值可以储存到数组的相同的位置。这些值以链表的方式存储。如下图
解决上面所说的缺陷的两种思路
做法
让元素个数到达数组容量的3/4。如下图
扩容缩减链表的长度 原理是什么？
这是因为当数组扩容的时候，所有的元素会根据新的数组容量计算桶下标。如下图
缺陷是 如果值得原始hash一致，那么它们不会随着扩容而改变原来的桶下标。原因显而易见
如果当前数组容量没有 >= 64
如果当前数组容量 >= 64
可知，红黑树是什么
红黑树能否提升查找效率？
根据上图，可以知道，如果要查找“8”，那么只需要比较3次。时间复杂度是O(log2^n) //原本的时间复杂度是O(n)
**红黑树中10、11的位置是怎么回事？**如下图
这是因为红黑树是按照字符串排序的
底层数据结构，1.7和1.8有何不同？
何时会树化？
为什么不一开始树化？
为什么要使用红黑树？
树化阈值为什么是“8”？
那么链表个数超过8的情况是什么？
=>hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小
在扩容时，如果树元素个数 <= 6 则会退化为链表
as 扩容前
扩容后
不会因为扩容而退化的情况
remove 树节点前，若 root、root.left、root.right、root.left.left 有一个为 null ，移除之后会退化为链表。
as 移除前（此时左孙子都没了）
移除“7”后
as2
移除“8”、“6”、“3”后
计算步骤
引出问题-在最后一步骤使用 & (capacity – 1 =>得到索引 的前提
数组容量为何是 2 的 n 次幂时更好
数组容量是 2 的 n 次幂时的其他注意事项
@hash 的分散性不好 证明如下
1.8 二次哈希源码
1.7 二次哈希源码
模拟 1.8 二次哈希源码
模拟 1.7 二次哈希源码
通过代码实验，可以知道二次哈希的作用是
使得链表的长度更短（或者说元素分布更均匀）
put 流程
1.7 与 1.8 的区别
创建两个线程，打算分别往“1”处存入数据
package day01.map;
import java.util.HashMap;
public class HashMapMissData {
public static void main(String[] args) throws InterruptedException {
HashMap<String, Object> map = new HashMap<>();
Thread t1 = new Thread(() -> {
map.put("a", new Object()); // 97 => 1
}, "t1");
Thread t2 = new Thread(() -> {
map.put("1", new Object()); // 49 => 1
}, "t2");
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println(map);
}
}
设置断点，打算让“t2”线程先存入
让“t2”线程存入
再让“t1”线程存入
可以知道，“t1”线程存入的数据覆盖了之前“t2”线程存入的数据
扩容死链（1.7 会存在）
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;
}
}
}
数据错乱（1.7，1.8 都会存在）
略
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);
}
}
}
这是因为在查找时，需要根据key值计算索引来查找，但是修改key值后，会使得查找索引也发生改变
目标是达到较为均匀的散列效果，每个字符串的 hashCode 足够独特
//字符串中的每个字符都可以通过查询码表表现为一个数字，称为 S i S_i Si，其中 i 的范围是 0 ~ n - 1
为什么每次乘于 31 而不是其他数字
证明 31 代入公式有较好的散列特性？
对比乘于 11 的效果
对比乘于 41 的效果
涉及资料