手撕HashMap（原理）

请说一下HashMap的底层原理。。。相信很多小伙伴都从面试官那里通过这句话。本文将带领大家一步步脱掉HashMap的外衣，写一个自己的HashMap
放在前面：什么是hash？

首先HashMap绝对不是一个简单的存储键值对的集合，如果面试的时候回答键值对基本上凉一半，，，正确答案是：HashMap是一个线性链表结构，由数组和链表共同构建而成。
如图：

可以看到纵向的是数组，横向的是链表，数组和链表有机结合组成了HashMap。
这里有一个问题：为什么要使用数组和链表？大家还记不记得数组和链表的特性,数组查询速度快存取速度不行，链表增删速度快查找慢，那么有没有一种结构能够查询和存取速度都相对理想，不像数组和链表这么偏科呢？HashMap！
HashMap是这么存储的：先计算（K，V）中的K的哈希值，然后对（数组长度-1）取摩确定要存储的纵向数组上的位置，这里横向上是一个链表结构。首先判断该链表否为空，为空就放进去并使next指针指向null，不为空时就利用临时变量把新来的元素插到原数据的前面。这样HashMap的存储就完成了。那么HashMap是怎么存储的大家肯定心里多多少少都有点逼数了吧。同样先使用K计算后先找出纵向位置，然后比较K是否与当前地址一致，一致就取出，不一致就next，直至找出该元素。这样兼顾数组与链表的长处查的时候使用数组特性多一点，取得时候使用链表。这里我们想一下，如果横向链表过长，当查询时是不是充分利用了链表低效率的查询特性。。。。那么是不是应该控制这种横向链表的无益增长，怎么做，答案是使用负载因子 一旦超出临界值就扩容，然后重新装配。

说了这么多，到底该怎么实现一个HashMap？上干货
这里就不一步步解释了，大家如果有问题可以在下面留言
第一步，定义接口：

package com.david;

public interface Map<K,V> {
    //向HashMap中插入值
    public V put(K k,V c);

    //根据Key获取HashMap中的值
    public V get(K k);

    //获取集合中的元素个数
    public int size();

    //获取几何中，键值对的对象

    interface  Entry<K,V>{
        K getKey();
        V getValue();
        V setValue(V v);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第二步实现接口：

package com.david;

public class HashMap<K, V> implements Map<K, V> {
    //数据存储结构=》 数组加链表 
    Node<K, V>[] array = null;

    //数组/hash桶的初始长度
    private static int defaultLength = 16;

    //加载因子/扩容因子
    private static double factor = 0.75D;

    //集合中的元素个数
    private int size;


    //调试打印函数
    public void print() {
        System.out.println("***************");
        if (array != null) {
            Node<K, V> node = null;
            for (int i = 0; i < array.length; i++) {
                node = array[i];
                System.out.print("下标【" + i + "】");
                while (node != null) {
                    System.out.print("[" + node.getKey() + ":" + node.getValue() + "]");
                    if (node != null)
                        node = node.next;
                    else
                        node = null;
                }
                System.out.println();
            }
        }

    }

    //put元素方法
    @Override
    public V put(K k, V v) {
        //1、懒加载机制，使用的时候进行分配
        if (array == null) {
            array = new Node[defaultLength];
        }

        //2、通过hash算法，计算出具体插入的位置
        int index = position(k, defaultLength);

        //判断是否需要扩容
        if (size > defaultLength * factor) {
            resize();
        }

        //3、加入要放入的元素
        Node<K, V> node = array[index];
        if (node == null) {
            array[index] = new Node<K, V>(k, v, null);
            size++;
        } else {
            if (k.equals(node.getKey()) || k == node.getKey()) {
                return node.setValue(v);
            } else {
                array[index] = new Node<K, V>(k, v, node);
                size++;
            }
        }
        return null;
    }

    //扩容，并重新排列元素
    private void resize() {
        //翻倍扩容
        //1、创建新temp array
        Node<K, V>[] temp = new Node[defaultLength << 1];

        //2、重新计算散列值，插入到新的array中。code=key%（defaultLength-1） ---》code=key%（defaultLength*2-1）
        Node<K, V> node = null;
        for (int i = 0; i < array.length; i++) {
            node = array[i];
            while (node != null) {
                //重新散列
                int index = position(node.getKey(), temp.length);
                Node<K, V> next = node.next;
                node.next = temp[index];
                temp[index] = node;
                node = next;
            }
        }

        //替换掉老的array
        array = temp;
        defaultLength = temp.length;
        temp = null;
    }

    private int position(K k, int Length) {
        int code = k.hashCode();
        //取模算法
        return code % (Length - 1);
        //求与算法
        //return code & (defaultLength-1);
    }

    @Override
    public V get(K k) {
        if (array != null) {
            int index = position(k, defaultLength);
            //获取对应哈希桶节点
            Node<K, V> node = array[index];
            //遍历链表
            while (node != null) {
                //返回对应key的value
                if (node.getKey() == k)
                    return node.getValue();
                else
                    node = node.next;
            }
        }
        return null;
    }

    @Override
    public int size() {
        return 0;
    }

    static class Node<K, V> implements Map.Entry<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;
        }

        @Override
        public K getKey() {
            return this.key;
        }

        @Override
        public V getValue() {
            return this.value;
        }

        @Override
        public V setValue(V v) {
            V oldValue = this.value;
            this.value = v;
            return oldValue;
        }
    }
}
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

第三步：测试

import com.david.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<String, String>();
        for (int i = 1; i < 50; i++) {
            map.put("0" + i + "号", "0" + i);
        }
        map.print();
        System.out.println("--->" + map.get("01号"));

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14