|
1、版本变化的问题
（1）JDK1.8之前：数组+链表
（2）JDK1.8之后：数组+链表/红黑树
2、JDK1.7以及之前的HashMap
（1）为什么要使用数组？
优点：可以根据[下标]能够快速的访问到某个元素，效率非常高。
如何利用这个优点？
①所有的对象都有一个hashCode值（因为Object类有public int hashCode()方法，那么所有对象都有这个方法，就可以得到hashCode值）。
hashCode值是int类型。
②理论上，每一个不同的对象，它的hashCode值是唯一的。
JDK开发团队就想 ?能不能创建一个足够大的“数组”，然后每一个放到HashMap中的（key,value）键值对，
根据key的hashCode值，来决定它放到这个“数组”中的下标
想法： hashCode值 = 这个足够大的数组的[下标]
根据这个想法，就可以快速的“存”和“取”这个（key,value）键值对。
但是因为一些原因，要考虑数组的问题？
③实际中，可能存在两个不同的对象，但是它们的hashCode值一样（虽然散列函数能够保证大多数不一样，但是仍然是有一部分是很难避免重复）
? 另外，数组没办法真正实现“足够大”，总是要考虑内存的有限性。
如何解决这个问题？
即当两个不同的对象的hashCode值相同了怎么办？ ?==> 可以在同一个数组的元素位置存储多个不同的对象（hashCode一样，equals不一样），
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 通过“链表”来链接这些对象
? 或者说，数组不能足够大怎么办？==> 假设数组的长度为16.
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hashCode % 数组的长度 的结果范围 [0, 数组的长度-1]
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hashCode & 数组的长度-1 的结果范围 [0, 数组的长度-1]
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hashCode值 ?xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx ? 二进制
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 16-1=15 ? ? 00000000 00000000 00000000 00001111 ? 二进制
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &-------------------------------------------------------
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00000000 ? 0
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00000001 ? 1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00000010 ? 2
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00000011 ? 3
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 。。。。。。。。。。。。。。。。。。。。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00001111 ? 15
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 假设数组的长度为10
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hashCode % 数组的长度 的结果范围 [0, 数组的长度-1]
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hashCode & 数组的长度-1 的结果范围 [0, 数组的长度-1] 但是只有它们中的几个可能
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hashCode值 ?xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx ? 二进制
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 10-1=9 ? ?00000000 00000000 00000000 00001001 ? 二进制
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &-------------------------------------------------------
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00000000 ? 0
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00000001 ? 1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00001000 ? 8
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 00000000 00000000 00000000 00001001 ? 9
? ? 这就解决了一个问题，数组哪怕 不是足够大，我们也可以用hashCode值 & （数组的长度-1） 得到一个[下标]，找到它在数组中的位置。
? ? 这里hash冲突有两种可能：（1）hashCode原值一样
? ? ? ? ? ? ? ? ? ? ? ? ? （2）hashCode原值不一样，但是 ?hashCode值 & （数组的长度-1） 一样
? ?如何解决hash冲突？使用“链表”来解决这个问题。
（2）为什么要用链表？
可能存在hash冲突的问题。
（3）HashMap的底层存储特点：
数组的元素此时不是依次存储的，因为存的[下标]是根据 ?key的 hashCode值 & （数组的长度-1）得到的。
数组[下标]的元素中可能是多个对象，多个对象使用“链表”结构进行连接。这多个对象的特点是hash冲突。
（4）如何设计数组的长度更好？
发现，如果数组的长度为2的n次方的话，数组的长度-1这个值的二进制有一个特征：它的最右边几位的二进制数字都是1.
? ? 例如：16 ? 16-1=15 ?00000000 00000000 00000000 00001111
? ? 例如：32 ? 32-1=31 ?00000000 00000000 00000000 00011111
? ? 例如：64 ? 64-1=63 ?00000000 00000000 00000000 00111111
? ? 这样的二进制值，可以保证 ?hashCode值 ?xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx ? 二进制
? ? ? ? ? ? ? ? ? ? ? ? ? ?数组的长度-1 00000000 00000000 00000000 00111111
? ? ? ? ? ? ? ? ? ? ? ? ? ?&----------------------------------------------
? ? ? ? ? ? ? ? ? ? ? ? ? ?结果是[0,数组的长度-1]范围内，而且是每一种都可能，即是相对均匀的。
HashMap的底层数组的长度就是设计为2的n次方。
HashMap的无参构造，构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
? ? ? ? ? ? 如果你指定的初始容量不是2的n次方，那么内部会给你纠正为 >= 指定初始容量的一个2的n次方的数字。
（5）理想情况下是希望，(key,value)能够均匀的存储到内部数组中，尽量不要出现某个数组名[下标]下面有多个的(key,value)连接情况，
因为这样的话，会造成效率降低（无论是添加、删除、查找）。
? ?只有提高hashCode值均匀的情况，以及数组的长度是2的n次方，来尽量的减少（但是不能避免）冲突。
3、JDK1.8的HashMap
（1）JDK1.8为什么要修改底层的设计，从数组+链表升级为数组+链表/红黑树？
虽然我们做了一些努力，能够尽量减少hash冲突，但是还是不能避免，所以可能存在某个数组名[下标]下的有很长的“链表”，
这个时候的效率低下。
为了提高效率，把链表升级为查询效率更高的红黑树。
（2）为什么不直接用 数组 + 红黑树，而是用数组+链表/红黑树？
红黑树：
? ? 优点：查询效率高
? ? 缺点：始终保持平衡关系，一旦“添加”“删除”这个操作影响了它的平衡性，就要“旋转等处理”，这样效率就低了。
所以，当 ? ?数组名[下标]下的链表不是特别的长的时，就仍然用“链表”
所以，当 ? ?数组名[下标]下的链表特别长时，就改用用“红黑树”
（3）什么时候，链表会变为红黑树？
TREEIFY_THRESHOLD：树化临界值 8
（4）是否 数组名[下标]下的链表长度一达到8个就立刻树化呢？
答案：不是
如果此时数组的长度还不够长，那么我可以尝试先对数组进行“扩容”。
例如：一开始长度假设为16，下标范围[0,15]
? ? ?如果把数组长度扩容一倍，长度变为32，下标范围[0,31]
这里hash冲突有两种可能：（1）hashCode原值一样 ? ? ? ? ? 扩容没用
? ? ? ? ? ? ? ? ? ? ? （2）hashCode原值不一样，但是 ?hashCode值 & （数组的长度-1） 一样 ? 当数组扩容后，可能减少一部分冲突
? ? ? ? ? ? ? ? ? ? ? 例如： ? ? ? hashCode值的二进制 ?00000000 00000000 00000000 00111001
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 16-1 ? ? ? ? ? ? 00000000 00000000 00000000 00001111
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &----------------------------------------------------
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000 00000000 00000000 00001001
? ? ? ? ? ? ? ? ? ? ? 例如： ? ? ? hashCode值的二进制 ?00000000 00000000 00000000 00111001
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 32-1 ? ? ? ? ? ? 00000000 00000000 00000000 00011111
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? &----------------------------------------------------
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?00000000 00000000 00000000 00011001
（5）数组扩容到什么时候，就不是用扩容来解决“冲突”问题，而是树化？
MIN_TREEIFY_CAPACITY=64 ?最小树化容量临界值64
结论：
? ? 当数组[下标]链表长度<8个时，还用链表。
? ? 当数组[下标]链表长度>8个时，先考虑扩容，如果数组的长度<64，仍然用链表。
? ? 当数组[下标]链表长度>8个时，如果数组的长度>=64，链表改为红黑树。
（6）当 ?数组[下标]下面的结点(key,value)数量越来越少了，会不会从红黑树变回链表呢？
答案：会的
（7）什么时候考虑反树化？
UNTREEIFY_THRESHOLD：6
当红黑树的结点数量<=6个时，可能会反树化。
删除过程中触发从树->链表的条件是： 树的根空了，或是树的左或右空了，树的左的左结点空了，才会触发。
删除后再添加时，需要遇到下一次扩容，扩容过程中，检查table[下标]下的结点个数是<=UNTREEIFY_THRESHOLD，会触发树转为链表的条件。
public class TestHashMap {
public static void main(String[] args) {
HashMap map1 = new HashMap();//默认初始容量 (16)
HashMap map2 = new HashMap(32);//指定初始容量20
map2.put(1,"hello");
System.out.println(Integer.highestOneBit((32 - 1) << 1));
}
}
4、存储到Map中的是(key,value)键值对，那么底层是如何表示这个键值对的呢？ ?
HashMap中的数组叫做table，这个table的元素类型是什么？
答：Map.Entry接口的实现类，不同的版本，实现类的名字不一样。
JDK1.7：Entry<K,V>[] table;
? ? Entry是1.7版HashMap一个内部类，它实现Map.Entry<K,V>接口。
? ? static class Entry<K,V> implements Map.Entry<K,V> {
? ? ? ? final K key;
? ? ? ? V value;
? ? ? ? Entry<K,V> next; ? 如果table[下标]有冲突，记录下一个结点的地址，这是链表结构
? ? ? ? int hash; ? 是key的hash，这里先备注一下，它不是key调用hashCode()直接得到值，而是再运算后的一个结果。
? ? ? ? ...
? ? }
JDK1.8：Node<K,V>[] table;
? ? Node是1.8版HashMap一个内部类，它实现了Map.Entry<K,V>接口。
? ? static class Node<K,V> implements Map.Entry<K,V> {
? ? ? ? final int hash; ?是key的hash，这里先备注一下，它不是key调用hashCode()直接得到值，而是再运算后的一个结果。
? ? ? ? final K key;
? ? ? ? V value;
? ? ? ? Node<K,V> next; ? 如果table[下标]有冲突，记录下一个结点的地址，这是链表结构
? ? ? ? ...
? ? }
? ? TreeNode也是HashMap一个内部类，它继承了LinkedHashMap.Entry<K,V>，它又继承了HashMap.Node<K,V>。
? ? TreeNode是Node的子类。
? ? static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
? ? ? ? TreeNode<K,V> parent; ?// red-black tree links ?父结点
? ? ? ? TreeNode<K,V> left; ? ? //左结点
? ? ? ? TreeNode<K,V> right; ? ?//右结点
? ? ? ? TreeNode<K,V> prev; ? ?// needed to unlink next upon deletion ? //前一个结点
? ? ? ? boolean red; ? ? ? ? ?//红或黑结点的标识
? ? ? ? ....
? ? }
5、Debug演示一下HashMap的内部结构
以JDK1.8为例
说明：为了演示“hash"冲突问题，那么我们要造一个自己的key类型，叫做MyKey。
如果按照正常的hashCode的计算，“hash"冲突比较低，想要看到 table[下标]下的结点个数达到8个比较难。
MyKey这个类型的hashCode方法，我故意写成 return 1;
所有的MyKey的hashCode值都是1，全部都是冲突的。
public class TestHashMap2 {
@Test
public void test01(){
HashMap<Integer,String> map = new HashMap<>();
map.put(1,"hello");
map.put(2,"java");
//遍历方式，
//(1)遍历所有key,
Set<Integer> integers = map.keySet();
//(2)遍历所有value
Collection<String> values = map.values();
//(3)遍历所有键值对
Set<Map.Entry<Integer, String>> entries = map.entrySet();
}
@Test
public void test02(){
HashMap<MyKey,String> map = new HashMap<>();
for(int i=1; i<=20; i++){
map.put(new MyKey(i),"value"+i);
}
}
@Test
public void test03(){
HashMap<MyKey,String> map = new HashMap<>();
for(int i=1; i<=20; i++){
map.put(new MyKey(i),"value"+i);
}
//经过上面的for，size=20
for(int i=1; i<=13; i++){
map.remove(new MyKey(i));
}
//经过上面的for，size=4,5,6
for(int i=30; i<=100; i++) {
map.put(new MyKey(i), "value" + i);
}
}
}
class MyKey{
private int k;
public MyKey(int k) {
this.k = k;
}
@Override
public String toString() {
return "MyKey{" +
"k=" + k +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MyKey myKey = (MyKey) o;
return k == myKey.k;
}
@Override
public int hashCode() {
// return Objects.hash(k);
// return 1;
if(k>20){
return 2;
}
return 1;
}
}
6、什么时候会扩容？
（1）JDK1.8时
A：当table[i]下面的链表的结点个数>=8，再添加新的结点到同一个table[i]下，也就是说链表的长度可能要达到9个时，
如果此时table的长度<64，会扩容
B：当size达到“扩容阈值threshold”
threshold = table.length * loadFactor
loadFactor：加载因子，默认值0.75
假设table.length是16，threshold = 16*0.75=12
假设table.length是32，threshold = 32*0.75=24
假设table.length是64，threshold = 64*0.75=48
（2）JDK1.7时
当size达到“扩容阈值threshold”
threshold = table.length * loadFactor
loadFactor：加载因子，默认值0.75
假设table.length是16，threshold = 16*0.75=12
假设table.length是32，threshold = 32*0.75=24
假设table.length是64，threshold = 64*0.75=48
扩容的条件是A：size>=threshold B: null != table[bucketIndex]
? ? ? ? bucketIndex：下标，新的(key,value)要存储的table数组的下标位置
public class TestHashMap3 {
@Test
public void test01(){
HashMap<Integer,String> map = new HashMap<>();//默认容量16
for(int i=1; i<=30; i++){
map.put(i,"value"+i);
}
}
@Test
public void test02(){
HashMap<MyClass,String> map = new HashMap<>();//默认容量16
for(int i=1; i<=30; i++){
map.put(new MyClass(i),"value"+i);
}
}
}
class MyClass{
private int k;
public MyClass(int k) {
this.k = k;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MyClass myClass = (MyClass) o;
return k == myClass.k;
}
@Override
public int hashCode() {
//
if(k<=10){
return Objects.hash(k);
}else{
return 1;
}
}
}
7、hashCode值
问？ ?(key,value)的存储位置如何计算的？
?之前分析设计思路： ? key的hashCode值 & table.length-1
?JDK1.7：
? ? ? ? int hash = hash(key);
? ? ? ? int i = indexFor(hash, table.length);
? ? ? ? ? ? ? ? static int indexFor(int h, int length) {
? ? ? ? ? ? ? ? ? ? return h & (length-1);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? final int hash(Object k) {
? ? ? ? ? ? ? ? ? ? int h = hashSeed;
? ? ? ? ? ? ? ? ? ? if (0 != h && k instanceof String) {
? ? ? ? ? ? ? ? ? ? ? ? return sun.misc.Hashing.stringHash32((String) k);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? h ^= k.hashCode(); ?//^= ?按位异或 ?h = h^k.hashCode();
? ? ? ? ? ? ? ? ? ? h ^= (h >>> 20) ^ (h >>> 12); // h = h ^ ( (h >>> 20) ^ (h >>> 12))
? ? ? ? ? ? ? ? ? ? return h ^ (h >>> 7) ^ (h >>> 4);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? 为什么不是直接拿k.hashCode()方法返回的值，直接与table.length-1直接做与运算，而是要经过各种^，>>>处理呢？
? ? ? ? ? ? ? ? 目的是让认为如果直接拿hashCode值()进行计算的话，会导致hashCode值的二进制的高位部分永远也用不上。
? ? ? ? ? ? ? ? ? ? ? ? hashCode值 ?xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
? ? ? ? ? ? ? ? ? ? ? ? 16-1 ? ? ? ?00000000 00000000 00000000 00001111
? ? ? ? ? ? ? ? 即如果直接拿hashCode值()进行计算的话，hash冲突的概率会增加。
? ? ? ? ? ? ? ? 如果加入了hashCode值的二进制高位数字特征（高位通过>>>右移后，会参与到&运算中来)，使得高位数字被用上，
? ? ? ? ? ? ? ? 增加干扰因素，使得冲突概率降低。
JDK1.8版：
? ? hash(key)
? ? n = (tab = resize()).length;
? ? tab[i = (n - 1) & hash]
? ? static final int hash(Object key) {
? ? ? ? int h;
? ? ? ? return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
? ? ? ? //相当于与key.hashCode值的高16位与低16位做了 ^ 运算，产生干扰
? ? }
结论：没有直接使用key的hashCode值 & table.length-1
? ?而是把key的hashCode值处理了一些（调用hash方法）之后，得到一个hash，hash ?& table.length-1，
? ?目的是希望冲突概率降低。
8、问？ 无论是JDK1.7中的HashMap.Entry类型，还是JDK1.8的HashMap.Node类型中都存储了计算后的hash，
? ? ? 为什么？
A：每一次添加新的(key,value)，我们要保证map中的key是不重复的。
? ? 需要用新的(key,value) ?中的key，与map中已经存在的所有的(key,value)做比较，看是否重复。
? ? ①先找到新的(key,value) 的存储位置[index]，此时我们只需要和[index]中的的(key,value)的key做比较，
? ? ? ? 因为如果存储位置不同，说明他们的hash值肯定不同，hash值不同，肯定是不同key对象。
? ? ②如果 ? ?[index]中已经有多个(key,value)，那么需要先比较这些key与新的key的hash值
? ? ? 如果此时我们没有hash，意味着我每次比较时，都要先调用key.hashCode()方法，得到原始的hashCode值，然后在调用hash()计算之后再比较。
? ? ? 如果每次都要算的话，效率就太低了。既然之前添加时，已经算好了，就存储起来，下次直接获取hash值，比较就可以了。
? ? ? ? hashCode()和equals方法一定要一起重写。
? ? ? ? 并且要遵循如下原则：
? ? ? ? A：如果两个对象的equals方法调用结果是true，那么它俩的hashCode值一定要一样
? ? ? ? B：如果两个对象的hashCode值不同，那么equals方法一定要返回false
? ? ? ? C：如果两个对象的hashCode值相同，那么equals方法的结果可能是true，可能是false
? ? ? ? 例如："Aa"和"BB"字符串 的hashCode值相同，但是equals却是false
? ? ? ? 例如："Aa"和"Aa"字符串 的hashCode值相同，equals也是true
B：查找时，如果hash已经存储了，根据key去调用get(key)查找键值对的时候，就可以快递的找到这个键值对。
比较时，就不用重新计算hash值。
9、问：为什么(key,value)存储到map中后，key就不能修改了？
因为key在存储时，hash已经存储了，你如果修改了key，会导致hashCode值变了，变了之后，原来的hash和新的key不匹配，就会导致找不到。
|