简易却高效的HashMap实现

java , 评论

目录

原理

我们每天都在使用HashMap,有没有想过,在很多情景下,HashMap做的其实没有特别好,他是一个很通用的k-v数据结构,却不一定在各个小方面都适合.因此我们实现了一个特定场景下使用的HashMap.

对于HashMap的原理,本文不做过分的重复,不甚了解的同学可以看一下 这篇文章.

我们可以针对基本类型实现自己的HashMap.比如IntHashMap.

当我们日常想要使用int->int的k-v形式的时候,我们必须使用HashMap<Integer,Integer>,因为HashMap不支持基本类型,只支持对象,那么我们为了存储一个4字节的int类型,使用了多少空间呢?

首先包装类至少12字节(对象头8+对其填充4).然后在Hashmap中存放的是entry对象的数组,一个entry对象至少20几个字节了,然后entry持有的k-v.又有对象头.这样算下来,光对象头就32字节,加上一些填充和对象中的辅助变量,50字节差不多了.

而我们的初衷只是为了存储8个字节极其对应关系.

这个时候就想,当key和value都是int的时候,底层我们直接使用int数组好了.

数据结构确定之后,我们逐一确定下其他要素:

构造方法: 我们强制必须传入一个初始的容量值.然后初始化.容量的计算参考HashMap的.

put方法: 我们对key进行hash取模后,依次放置,如果冲突,不采用拉链法,而是线性探测,向后遍历,找到空位置放下.减小我们的数据结构的复杂度.

get方法: get方法没什么好讲的,hash然后寻找.

代码实现

下面具体的代码实现:

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
/**
 * Created by pfliu on 2019/08/07.
 */
public class IntHashMap {
    private int[] keys;
    private int[] vals;
    private int size = 0;

    public IntHashMap(int capacity) {
        capacity = tableSizeFor(capacity);
        keys = new int[capacity];
        vals = new int[capacity];
    }

    public int size() {
        return size;
    }

    public int get(int key) {
        int h = hash(key);
        int size_1 = keys.length - 1;

        final int LOOP_UNROLLING = 3;

        for (int i = 0; i < LOOP_UNROLLING; i++) {
            int idx = (h + i) & size_1;
            if (keys[idx] == key) return vals[idx];
            if (keys[idx] == 0) return 0;
        }

        for (int i = LOOP_UNROLLING; ; i++) {
            int idx = (h + i) & size_1;
            if (keys[idx] == key) return vals[idx];
            if (keys[idx] == 0) return 0;
        }
    }

    public boolean put(int key, int value) {
        // 扩容以及rehash
        if (this.size + (this.size >> 1) > keys.length) { 
            int[] oldKeys = this.keys;
            int[] oldVals = this.vals;

            this.keys = new int[oldKeys.length * 2];
            this.vals = new int[oldKeys.length * 2];

            this.size = 0;
            for (int i = 0; i < oldKeys.length; i++) {
                if (oldKeys[i] != 0) {
                    put0(oldKeys[i], oldVals[i]);
                }
            }
        }

        return put0(key, value);
    }

    private boolean put0(int key, int value) {
        int h = hash(key);
        int size_1 = keys.length - 1;

        for (int i = 0; ; i++) {
            int idx = (h + i) & size_1;
            if (keys[idx] == 0) {
                keys[idx] = key;
                vals[idx] = value;
                this.size += 1;
                return true;
            } else if (keys[idx] == key) {
                vals[idx] = value;
                return false;
            }
        }
    }

    // 模仿hashmap的容量计算
    public static int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : n + 1;
    }

    // hash
    public static int hash(int x) {
        x = ((x >>> 16) ^ x) * 0x45d9f3b;
        x = ((x >>> 16) ^ x) * 0x45d9f3b;
        x = (x >>> 16) ^ x;
        return x;
    }
}

性能测试

测试方法如下:

对IntHashMap和HashMap分别进行随机数字的X次插入和取出.统计时间以及占用内存大小.统计结果如下:

其中T1=IntHashMap消耗时间,T2=HashMap消耗时间,M1=IntHashMap占用内存,M2=HashMap占用内存.

其中时间单位为ms,内存占用单位为字节.

Table T1 T2 M1 M2
10000 6ms 7ms 524344 666304
100000 17ms 31ms 1048632 4576320
1000000 157ms 299ms 8388664 44626736
10000000 2184ms 7613ms 134217784 471696400

测试代码如下:

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
import jdk.nashorn.internal.ir.debug.ObjectSizeCalculator;
import org.junit.Test;

import java.util.*;

public class IntHashMapTest {

    static final int NUM = 10000000;

    @Test
    public void t() {
        // 7,8 万的亚子
        Ticker ticker = new Ticker();
        IntHashMap intHashMap = new IntHashMap(1 << 16);

        Random r = new Random();

        for (int i = 0; i < NUM; i++) {
            int key = r.nextInt(NUM);
            intHashMap.put(key, key + 2);
        }

        for (int i = 0; i < NUM; i++) {
            int j = intHashMap.get(r.nextInt(NUM));
        }

        ticker.tick("inthashmap");

        Map<Integer, Integer> map = new HashMap<>(1 << 16);
        Random r1 = new Random();

        for (int i = 0; i < NUM; i++) {
            int key = r1.nextInt(NUM);
            map.put(key, key + 2);
        }

        for (int i = 0; i < NUM; i++) {
            Integer a = map.get(r1.nextInt(NUM));
        }
        ticker.tick("hashmap");
        System.out.println(ObjectSizeCalculator.getObjectSize(intHashMap));
        System.out.println(ObjectSizeCalculator.getObjectSize(map));
        System.out.println(ticker.toString());

    }
}

总结

从测试结果我们可以看出来,效果还是不错的,因此在很追求性能的条件下,如有使用基本类型的HashMap的需求,不妨自己试一下.按照图中的代码,可以很轻易的扩展出针对long,float等其他基本类型的定制版HashMap.


完。







ChangeLog

2019-08-12 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。