Java On-Memory高效键值存储

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java On-Memory高效键值存储，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3310字，纯文字阅读大概需要5分钟。

内容图文

我存储了1.11亿个键值对(一个键可以有多个值 – 最大值为2/3),其键为50位整数,值为32位(最大值)整数.现在,我的要求是：

1. Fast Insertion of (Key, Value) pair [allowing duplicates]
2. Fast retrieving of value/values based on key.

一个很好的解决方案是基于MultiMap给出here.但是,我想在主内存中存储更多的键值对,没有/小的性能损失.我从网络文章中研究过B Tree,R Tree,B Tree,Compact Multimap等可以很好地解决这个问题.有谁能够帮助我：

是否有任何Java库可以满足我的所有需求
    (上面提到/其他ds也可以接受.没有问题)？
    实际上,我想要一个高效的java库数据结构来存储/检索
    键值/值对,占用更少的内存,必须
    内置于内存中.

注意：我曾尝试使用路易斯·沃瑟曼,京都/东京内阁等提到的HashMultiMap(Guava与trove进行一些修改)等.我的经验对于磁盘烘焙解决方案并不好.所以请避免:).另一点是,为了选择库/ ds,一个重点是：密钥是50位(所以如果我们分配64位),14位将丢失,值为32位Int(最大) – 大多数是10-12-14位.所以,我们也可以节省空间.

解决方法:

我认为JDK中没有任何东西可以做到这一点.

然而,实现这样的事情只是一个简单的编程问题.这是一个带有线性探测的开放式散列表,其中键和值存储在并行数组中：

public class LongIntParallelHashMultimap {

    private static final long NULL = 0L;

    private final long[] keys;
    private final int[] values;
    private int size;

    public LongIntParallelHashMultimap(int capacity) {
        keys = new long[capacity];
        values = new int[capacity];
    }

    public void put(long key, int value) {
        if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL);
        if (size == keys.length) throw new IllegalStateException("map is full");

        int index = indexFor(key);
        while (keys[index] != NULL) {
            index = successor(index);
        }
        keys[index] = key;
        values[index] = value;
        ++size;
    }

    public int[] get(long key) {
        if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL);

        int index = indexFor(key);
        int count = countHits(key, index);

        int[] hits = new int[count];
        int hitIndex = 0;

        while (keys[index] != NULL) {
            if (keys[index] == key) {
                hits[hitIndex] = values[index];
                ++hitIndex;
            }
            index = successor(index);
        }

        return hits;
    }

    private int countHits(long key, int index) {
        int numHits = 0;
        while (keys[index] != NULL) {
            if (keys[index] == key) ++numHits;
            index = successor(index);
        }
        return numHits;
    }

    private int indexFor(long key) {
        // the hashing constant is (the golden ratio * Long.MAX_VALUE) + 1
        // see The Art of Computer Programming, section 6.4
        // the constant has two important properties:
        // (1) it is coprime with 2^64, so multiplication by it is a bijective function, and does not generate collisions in the hash
        // (2) it has a 1 in the bottom bit, so it does not add zeroes in the bottom bits of the hash, and does not generate (gratuitous) collisions in the index
        long hash = key * 5700357409661598721L;
        return Math.abs((int) (hash % keys.length));
    }

    private int successor(int index) {
        return (index + 1) % keys.length;
    }

    public int size() {
        return size;
    }

}

请注意,这是一个固定大小的结构.您需要创建足够大的数据来保存所有数据–1.1亿条记录占用1.32 GB.您创建的数据越大,超出存储数据所需的数量,插入和查找的速度就越快.我发现,对于1.1亿个条目,加载因子为0.5(2.64 GB,是所需空间的两倍),查找密钥平均需要403纳秒,但负载系数为0.75(1.76 GB,a比需要的空间多三个,花了575纳秒.将负载系数降低到0.5以下通常没有太大区别,实际上,当负载系数为0.33(4.00 GB,比所需空间多三倍)时,平均时间为394纳秒.因此,即使您有5 GB可用,也不要全部使用它.

另请注意,不允许将零作为键.如果这是一个问题,请将null值更改为其他值,并在创建时使用该值预填充keys数组.

内容总结

以上是互联网集市为您收集整理的Java On-Memory高效键值存储全部内容，希望文章能够帮你解决Java On-Memory高效键值存储所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端