简易却高效的hashmap实现

呼延十

发布于 2019-09-10 19:36:58

8690

发布于 2019-09-10 19:36:58

文章被收录于专栏：呼延

原理

我们每天都在使用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然后寻找.

代码实现

下面具体的代码实现:

/**
 * 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

测试代码如下:

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());

    }
}