首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >简易却高效的hashmap实现

简易却高效的hashmap实现

作者头像
呼延十
发布2019-09-10 19:36:58
7780
发布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());

    }
}

总结

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 目录
  • 原理
  • 代码实现
  • 性能测试
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档