HashMap底层原理_hashmap的底层实现 c++

HashMap底层原理剖析

前置知识
数据结构：数组、链表、红黑树
算法：hash算法
1
2
3

看图说话：

面试官：你能说一下hashmap的底层实现原理吗？

回答：hashmap底层实现是数组+链表，回答完毕，猝！！！

这TM和没说有什么区别呢，今天我们好好的剖析一下

JDK1.7实现

基本实现思想

JDK1.7中，hashmap底层是由数组加链表实现，初始的数组长度为16，调用map.put(key,value)方法会首先根据key算出hashcode，再和数组长度取模运算得到数组下标index，然后把key和value封装成一个Entry对象存入数组对应的位置

链表的使用时机

因为是和数组长度进行取模，所以一定会出现哈希冲突的情况，当哈希冲突之后算出的数组下标一定是一致的，我们知道数组在同一位置插值，前值会被覆盖，这时候就用链表来解决这个问题，在Entry对象中还有一个关键属性：next对象，这个对象保存了原本在这个位置的Entry对象，这样就形成了一个链

JDK1.8的优化

思考：我们都知道，数组的优势在于查找速度快，而链表的查询速度并没有数组这么迅速，每次查找的时候都需要从头链向尾链遍历，那么如果链表过长，假设有1W个数据在这条链上，而我们查找的数据在靠后的位置，那整个查询效率将会很低，怎么解决这个问题呢？

红黑树的加入

jdk1.8为了优化这个查询过程，加入了红黑树的数据结构，我们知道红黑树是一种二叉树，那在查找的效率上基本是比链表快了一倍，但是在生成树的时候会有一次左旋的计算，这是有一定开销的，所以jdk1.8为了平衡链表和红黑树，加了一个阀值8，当链表长度>7的时候，会将链表转成红黑树

下面贴一张更为细腻的图，相信看到这里再结合下图，你会很容易理解hashmap的工作原理了

手撕鬼子环节：手写一个HashMap

创建Map接口，规定三个方法：插值（put）、取值（get）、集合大小（size）

public interface Map<K, V> {
    void put(K k, V v);
    V get(K k);
    int size();
}
1
2
3
4
5

创建map的数组中存储的Entry对象，定义属性，提供getter、setter、构造方法

public class Entry<K, V> {

    K key; // 键
    V value; // 值
    int index; // 下标
    Entry<K, V> next; // 下段链节点数据

    public Entry(K key, V value, int index, Entry next) {
        this.key = key;
        this.value = value;
        this.index = index;
        this.next = next;
    }

  // 忽略getter、setter
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

创建hashmap类，实现map接口

public class HashMap<K, V> implements Map<K, V> {

    private Entry<K, V>[] table = null;
    int size = 0;

    public HashMap() {
        table = new Entry[16];
        int size = 0;
    }

  	/**
     * 插值
     * 
     * 1、根据key得到数组下标
     * 2、检查数组相对位置是否存在数据
     *  2.1、不存在：封装entry对象，插入数组相对位置
     *  2.2、存在：将已有entry对象装入新entry对象的next属性，将新entry对象插入数组相对位置
     * @param k 键
     * @param v 值
     */
    @Override
    public void put(K k, V v) {
        int index = hash(k);
        Entry<K, V> entry = table[index];
        if (entry == null) { // 没有哈希冲突
            table[index] = new Entry<>(k, v, index, null);
        } else { // 哈希冲突
            table[index] = new Entry<>(k, v, index, table[index]);
        }
        size++;
    }

    /**
     * 哈希计算
     *
     * @param k 建
     * @return 数组下标
     */
    private int hash(K k) {
        int hashCode = k.hashCode();
        // 因为hashCode会出现负数导致错误，所以我们取一个绝对值
        return Math.abs(hashCode % table.length);
    }

     /**
     * 取值
     *
     * 1、根据key得到数组下标
     * 2、根据下标拿到entry对象
     * 3、判断key是否和当前entry中相同
     *  3.1、相同：返回对应value
     *  3.2、不同：拿到链表下一节点数据执行第3步
     * @param k
     * @return
     */
    @Override
    public V get(K k) {
        int index = hash(k);
        Entry<K, V> entry = table[index];
        return (entry != null) ? findValue(entry, k).getValue() : null;
    }

    private Entry<K, V> findValue(Entry<K, V> entry, K k) {
        if (entry != null) {
            if (k.equals(entry.getKey()) || k == entry.getKey()) {
                return entry;
            } else {
                if (entry.getNext() != null) {
                    return findValue(entry.getNext(), k);
                }
            }
        }
        return null;
    }

    @Override
    public int size() {
        return size;
    }
  
}
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

一套组合拳打完收工，看测试

  public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("刘一", "java工程师");
        map.put("陈二", "python工程师");
        map.put("张三", "js工程师");
        map.put("李四", "php工程师");
        map.put("王五", "c++工程师");

        System.out.println("刘一 --- hashCode：" + "刘一".hashCode() + " --- index:" + hash("刘一") + " --- " + map.get("刘一"));
        System.out.println("陈二 --- hashCode：" + "陈二".hashCode() + " --- index:" + hash("陈二")  + " --- " + map.get("陈二"));
        System.out.println("张三 --- hashCode：" + "张三".hashCode() + " --- index:" + hash("张三")  + " --- " + map.get("张三"));
        System.out.println("李四 --- hashCode：" + "李四".hashCode() + " --- index:" + hash("李四")  + " --- " + map.get("李四"));
        System.out.println("王五 --- hashCode：" + "王五".hashCode() + " --- index:" + hash("王五")  + " --- " + map.get("王五"));

        System.out.println("size:" + map.size());
    }

    private static int hash(String k) {
        int hashCode = k.hashCode();
        return Math.abs(hashCode % 16);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

多线程下出现的问题

很多人都知道hashmap是线程不安全的，但是为什么不安全呢？jdk也提供了解决方案，哪种更好呢？

为什么HashMap是线程不安全的？

看过上面的图，你会发现在调用put方法的时候有一个关键步骤，就是得到数组下标后，检查数组相对位置是否为空，我们假设有两个线程在同一时间都进行put，两个线程都检测到相对位置是空，那会出现什么结果？基于hashmap的工作原理，检查出数组相对位置为空，会直接进行数据插入，而数组的特性决定了后填入的数据会覆盖先前数据，这个操作会导致其中一个线程的数据丢失，这个数据被覆盖掉了，所以说他是线程不安全的

HashTable是线程安全的，但是为什么不用呢？

我们上面说到了hashmap是线程不安全的，为了解决线程安全问题，同胞兄弟hashtable则是被设计成线程安全的，但是hashtable比hashmap的效率低，为什么低呢？我们来看源码

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        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

这我们看到这段源码解决线程问题的关键在于加锁，但是synchronized给到了方法，那么这个粒度是map对象本身，对于插值来说这个粒度是大的，因为在插值的时候，如果不出现哈希冲突，同时插值在数组的不同下标下，这样是不存在线程安全问题的，锁给了map本身那就意味着每次插入都需要等待锁的释放，这就变成了一个串行操作，效率当然低了，所以基本这个同胞兄弟是不会被使用的，想要优化这个问题，就要引出一个概念：对位锁，这将引出另外一个map对象：ConcurrentHashMap

线程安全的ConcurrentHashMap