java手撕HashMap

---

入门hashMap

1.数组的优势/劣势

优势 1.查询快，通过下标
劣势 1.数组不能扩容，如果创建在放入，浪费性能
1
2

2.链表的优势/劣势

优势 1.增删快
劣势 1.索引查询慢
1
2

3.有没有一种方式整合两种数据结构的优势？散列表

4.散列表有什么特点？

优势 1.整合了 数组和链表的优势
1

5.什么是哈希？

基本原理就是：把任意长度的输入，通过hash算法变成固定长度的输出。
这个映射的规则，就是hash算法，而原始数据映射后的二进制就算哈希值。

Hash的特点:
1.从hash值不可以反向推导出原始的数据
2.输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值
3.哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
4.hash算法的冲突概率要小

由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。

抽屉原理:桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果这一现象就是我们所说的“抽屉原理”。
1
2
3
4
5
6
7
8
9

HashMap原理讲解

1.HashMap的继承体系是什么样的？

2.Node数据结构介绍？

静态内部类
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        
		.......
}
1
2
3
4
5
6
7
8
9

hash字段 和 哈希值有区别
hash --处理> 真的哈希
key字段 和 value字段 是hashMap中输入的<K,V>
Node<K,V>类型的next字段 为了形成链表

3.底层存储结构介绍？

jdk1.8以前是
链表+数组

4.put数据原理分析？

5.什么是Hash碰撞？

两个hash值相同，
形成一个链表
理想状态下hashMap时间复杂度是o（1） 但是如果链表很长就会变成o（n）

6.什么是链化？

同一个hash值的Node太多，链表化。

7.jdk8为什么引入红黑树？

为了解决链化，提高效率

8.HashMap扩容原理？

扩容为了提高查找的性能，
以空间换时间

手撕源码

1.Hash核心属性分析（threshold，loadFactory，size，modCount）

常量字段

比如说：初始化大小 1<<4 二进制左移四位  必须是2的幂
最大 1<<30 二进制左移三十位  必须是2的幂
负载因子：75%
树化阈值：8
树退化成链表阈值：6
最小树化容量：64
1
2
3
4
5
6

非常量字段

threshold 扩容阈值，当哈希表元素超过阈值时，触发扩容
threshold  =  capacity(哈希表数组长度，默认16) * loadFactor 
loadFactor 负载因子 （默认常量是0.75 ，但是可以设置）
1
2
3

四个构造方法

HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap()
public HashMap(Map<? extends K, ? extends V> m)
1
2
3
4

2.构造方法分析

HashMap(int initialCapacity, float loadFactor)

public HashMap(int initialCapacity, float loadFactor) {
		//进行简单的值域判断，
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
        this.loadFactor = loadFactor;
        //tableSizeFor方法把进入的长度给规整化 只能是2的幂
        this.threshold = tableSizeFor(initialCapacity);
    }
1
2
3
4
5
6
7
8
9
10
11
12

3.put方法分析=>putVal方法分析

//put 调用的是 putVal方法 
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}

里面有一个值是 hash(key) 
作用：让key的hash值的高16位也参与路由运算
无符号右移16位 异或 hashCode值
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hashCode并不是java写的
public native int hashCode();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第一次调用putVal的时候会初始化HashMap对象中的最耗内存的散列表，等于是一个懒初始化。里面走了一个路由算法，（n-1）& hash，和路由寻址
需要判断，存储的时候 是不是放入数组，或者链表，或者红黑树。

4.resize扩容方法分析

为了解决hash冲突导致的链化影响查询效率的问题，扩容会缓解问题。

final Node<K,V>[] resize() {
		//oldTab 引用扩容前的哈希表
        Node<K,V>[] oldTab = table;
        //oldCap 扩容之前table数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //oldThr 扩容之前的阈值
        int oldThr = threshold;
        //newCap  扩 容之后想要的大小 
        //newThr  扩容之后下次触发扩容的条件
        int newCap, newThr = 0;
        
        //hashMap的散列表已经初始化过了，是正常的扩容
        if (oldCap > 0) {
        	//扩容前的大小已经达到，最大阈值，则不扩容了，设置扩容条件为int最大值
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //oldCap 左移一位 其实就是二进制翻倍，并且小于数组最大值限制，数组大小大于16（默认为16），下一次扩容的阈值也跟着翻倍。
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
		//oldCap ==0，说明hashMap的散列表是null
		//1.new hashMap(initCap,loadFactor)
		//2.new hashMap(initCap)
		//3.new hashMap(map) map有数据
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // oldCap ==0，oldThr ==0
        //new hashMap(); 
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;	//16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);	//12
        }
        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;
        //本次扩容之前，table不为null
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
            	//当前node节点
                Node<K,V> e;
                //树的头结点赋值给了e，桶位中有数据，但是这个数据是 链表？红黑树？还是单个数据？不知道
                if ((e = oldTab[j]) != null) {
                	//方便JVM GC时回收内存
                    oldTab[j] = null;
                    //第一种情况桶位只有一个元素，未发生碰撞，直接计算出元素位置，然后丢进去
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //当前节点已经树化
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                   	//链表
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            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) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

什么时候进行resize操作？

有两种情况会进行resize：1、初始化table；2、在size超过threshold之后进行扩容
1

扩容后的新数组容量为多大比较合适？

扩容后的数组应该为原数组的两倍，并且这里的数组大小必须是2的幂
1

节点在转移的过程中是一个个节点复制还是一串一串的转移？

从源码中我们可以看出，扩容时是先找到拆分后处于同一个桶的节点，将这些节点连接好，然后把头节点存入桶中即可
1

5.remove方法分析

去除 key值

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
1
2
3
4
5

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        //hashmap中的散列表   当前node值    n散列表数组长度   寻址结果
        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);
                }
            }
            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)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

6.get方法分析

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}
1
2
3
4

final Node<K,V> getNode(int hash, Object key) {
		//tab 引用当前的散列表
		//first 桶位头元素
		//e 临时 node
		//n table数组长度
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //第一种情况，定位出的桶位元素就是需要get的数据
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //第二种情况，要么是树要么是链，需要排查寻找
            if ((e = first.next) != null) {
                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);
            }
        }
        //第三种情况，如果没有就返回null
        return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

存入的时候需要hash 取值的时候肯定也得 hash，不然你拿出来的值和存入的时候不一样。

7.replace方法分析 替换

    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);
            return true;
        }
        return false;
    }

    @Override
    public V replace(K key, V value) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23