Java-手写HashMap

[TOC]

Java-手写HashMap

1
2
3
public class MyHashMap{
  
}

我将顺着下面的这些问题，一步步完成MyHashMap的实现。（没有实现红黑树）

一、HashMap 为什么选择数组+链表作为底层数据结构？

  • 数组的查询复杂度是 O(1)，但插入效率（尤其是中间和头部插入）较低。
  • 链表的查询复杂度是 O(n)，但插入复杂度为 O(1)。
  • 结合数组和链表的优点，提高了查询和插入效率。
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
package myHashMap;


import java.util.HashMap;
import java.util.Objects;

/**
 * @author Michael
 */
public class MyHashMap<K,V> {

    Node<K,V>[] table;
  
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;

        public Node(K key,V value,Node<K,V> next){
            this.key=key;
            this.value=value;
            this.next=next;
        }
    }

}

二、数组的大小怎么规定？

源码中规定，数组的大小必须等于2^n，这是因为：

  1. 如果 table 的长度是 2^n，元素在数组中的索引计算 index = hash % table.length 可等效为 index = hash & (table.length - 1)，用位运算替代取模运算，提高计算效率。

  2. 当数组扩容时，如果元素原本分布均匀，扩容后也能保持均匀分布。例如：

    • 假设某元素的哈希值为 10101100

    • 旧数组计算索引：

      1
      2
      3
      makefile复制编辑hash        = 10101100  
      length - 1  = 00000111  
      index       = 00000100  (4)

    • 新数组计算索引：

      1
      2
      3
      makefile复制编辑hash        = 10101100  
      length - 1  = 00001111  
      index       = 00001100  (12)

    • 观察第四位（从右数）：

      • 高位为 0：位置不变。
      • 高位为 1：移动到新位置（原索引位置 + 原容量）。

源码中，初始化的数组大小为16。

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
package myHashMap;


import java.util.HashMap;
import java.util.Objects;

/**
 * @author Michael
 */
public class MyHashMap<K,V> {

    Node<K,V>[] table;
    int DEFAULT_INITIAL_CAPACITY=1<<4;

    public MyHashMap(){
        table=new Node[DEFAULT_INITIAL_CAPACITY];
    }

  
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;

        public Node(K key,V value,Node<K,V> next){
            this.key=key;
            this.value=value;
            this.next=next;
        }
    }

}

三、数组什么时候进行扩容？

我们定义一个size来存储【数组当前实际存储的元素个数】，然后有两个问题：

1）什么时候进行扩容？

2）扩容扩到多少？

对于问题一，HashMap的源码中，是当size=table.length*0.75时，就进行扩容。

  • 我们将0.75称为负载因子，定义LOAD_FACTOR；
  • table.length*LOAD_FACTOR就称为阈值，定义threshold。

对于问题二，HashMap的源码中是将数组大小翻倍，这样保证扩容后的数组长度依然是2^n。

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
package myHashMap;


import java.util.HashMap;
import java.util.Objects;

/**
 * @author Michael
 */
public class MyHashMap<K,V> {

    Node<K,V>[] table;
    int DEFAULT_INITIAL_CAPACITY=1<<4;
    float LOAD_FACTOR=0.75f;
    int size=0;
    int threshold=(int)(DEFAULT_INITIAL_CAPACITY*LOAD_FACTOR);

    public MyHashMap(){
        table=new Node[DEFAULT_INITIAL_CAPACITY];
    }


    public int getThreshold(){
        return table==null?0:(int)(table.length*LOAD_FACTOR);
    }

    class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;

        public Node(K key,V value,Node<K,V> next){
            this.key=key;
            this.value=value;
            this.next=next;
        }
    }

}

四、元素的 hash 值是直接返回 hashCode() 吗？

  • 若 hash = obj.hashCode()，索引计算 index = hash & (length - 1) 仅受 hashCode() 低位影响，高位不起作用，容易导致冲突。

  • 为了让高位也参与计算，我们这样计算 hash 值：

    1
    2
    hash = (hashCode) ^ (hashCode >>> 16)
    index = hash & (length - 1)
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
package myHashMap;


import java.util.HashMap;
import java.util.Objects;

/**
 * @author Michael
 */
public class MyHashMap<K,V> {

    Node<K,V>[] table;
    int DEFAULT_INITIAL_CAPACITY=1<<4;
    float LOAD_FACTOR=0.75f;
    int size=0;
    int threshold=(int)(DEFAULT_INITIAL_CAPACITY*LOAD_FACTOR);

    public MyHashMap(){
        table=new Node[DEFAULT_INITIAL_CAPACITY];
    }

    public int hash(Object key){
        int h;
        return key==null?0:(h=key.hashCode())^(h>>>16);
    }

    public int getIndex(int hash){
        return hash&(table.length-1);
    }

    public int getThreshold(){
        return table==null?0:(int)(table.length*LOAD_FACTOR);
    }

    class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;

        public Node(K key,V value,Node<K,V> next){
            this.key=key;
            this.value=value;
            this.next=next;
        }
    }

}

五、HashMap 的 put()、get()、resize() 方法

put()方法：

  1. table 是否已初始化，若未初始化则先进行初始化。
  2. 是否超过阈值，若超出则先扩容resize()。
  3. 计算在数组中的索引值。
  4. 若索引位置为空，直接插入。
  5. 若索引位置不为空，则遍历链表：
    • 若 key 相同，直接覆盖。这里 key 相同指的是：内存地址相同；或者，如果内存地址不同，那么通过equals()判断值是否相同；
    • 若 key 不同且已遍历到链表尾部，则新增节点插入链表尾部。

get()与resize()方法流程不再叙述，resize()就是按创建一个更长（翻倍）的数组，然后进行复制。

直接看代码吧！

六、最终版本

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
package myHashMap;


import java.util.HashMap;
import java.util.Objects;

/**
 * @author Michael
 */
public class MyHashMap<K,V> {

    Node<K,V>[] table;
    int DEFAULT_INITIAL_CAPACITY=1<<4;
    float LOAD_FACTOR=0.75f;
    int size=0;
    int threshold=(int)(DEFAULT_INITIAL_CAPACITY*LOAD_FACTOR);

    public MyHashMap(){
        table=new Node[DEFAULT_INITIAL_CAPACITY];
    }

    public int hash(Object key){
        int h;
        return key==null?0:(h=key.hashCode())^(h>>>16);
    }

    public int getIndex(int hash){
        return hash&(table.length-1);
    }

    public void put(K key,V value){
        //1. table是否已初始化，如果没有，则要先初始化table
        if(table==null){
            table=new Node[DEFAULT_INITIAL_CAPACITY];
        }
        //2. 是否会超过阈值，如果是，则要先扩容
        if(size+1>getThreshold()){
            resize();
        }
        //3. 计算得到在数组中的索引值
        int index=getIndex(hash(key));
        //4. 索引处如果为空，则直接插入
        Node<K, V> node = table[index];
        if(node==null){
            node=new Node<>(key,value,null);
            size+=1;
        }
        //5. 索引处如果不为空，则从第一个链表节点开始遍历：
        // 5.1 如果有key值相同，则直接返回。这里 key 相同指的是：内存地址相同；或者，如果内存地址不同，那么通过`equals()`判断值是否相同；
        // 5.2 如果没有key值相同，则此时已经在链表尾部，那就新创建节点，并插入到索引处链表的尾部
        else{
            Node<K,V> prev=node;
            while(node!=null){
                if(Objects.equals(node.key, key)){
                    return;
                }
                prev=node;
                node=node.next;
            }
            Node newNode = new Node(key, value, null);
            prev.next=newNode;
            size+=1;
        }
    }

    public V get(K key){
        if(table==null||table.length<1){
            return null;
        }
        int index=getIndex(hash(key));
        Node<K, V> node = table[index];
        if(node==null){
            return null;
        }else{
            while(node!=null){
                if(node.key==key||Objects.equals(node.key,key)){
                    return node.value;
                }
                node=node.next;
            }
        }
        return null;
    }

    public void resize(){
        if(table==null){
            table=new Node[DEFAULT_INITIAL_CAPACITY];
            return;
        }
        Node<K,V>[] oldTab=table;
        int newCapacity=oldTab.length<<2;
        Node<K,V>[] newTab=new Node[newCapacity];
        table=newTab;
        for(int i=0;i< oldTab.length;i++){
            Node<K, V> node = oldTab[i];
            while(node!=null){
                put(node.key,node.value);
                node=node.next;
            }
        }
    }

    public int getThreshold(){
        return table==null?0:(int)(table.length*LOAD_FACTOR);
    }

    class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;

        public Node(K key,V value,Node<K,V> next){
            this.key=key;
            this.value=value;
            this.next=next;
        }
    }

}

六、为什么 Java 8 更新，链表长度达到 8 时转换为红黑树？

当链表过长时，由于链表的查询复杂度是O(n)，会导致查询效率降低；所以用时间复杂度为O(log n)的红黑树进行优化。

但事实上，根据泊松分布公式，出现8个 hash 冲突的几率非常低；所以一旦出现8个以上 hash 冲突，多半是误操作或者漏洞攻击。

之前就有利用 HashMap 这种链表结构攻击，导致服务器崩溃，所以这个变红黑树其实是补漏洞。正常操作很难出现红黑树。

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

去把这个不完美的故事，变成你所期望的样子。