我应该如何以内存效率的方式将字符串键映射到Java中的值？

Question

我正在寻找一种存储字符串 - > int映射的方法.当然,HashMap是一个最明显的解决方案,但由于我受内存限制,需要存储200万对,7个字符长的密钥,我需要一些内存有效的东西,检索速度是次要参数.

目前我正沿着以下方向前进:

List<Tuple<String, int>> list = new ArrayList<Tuple<String, int>>();
list.add(...); // load from file
Collections.sort(list);

然后进行检索:

Collections.binarySearch(list, key); // log(n), acceptable

或许我应该去为一个自定义的树(每个节点一个字符,每片叶子与结果),或有一个现有的集合,符合这个好听？这些字符串实际上是顺序的(英国邮政编码,它们没有多大区别),所以我期待在这里节省大量内存.

Answer 1

编辑:我刚刚看到你提到字符串是英国邮政编码,所以我相当自信你使用Trove TLongIntHashMap不会出错:顺便说一句,Trove是一个小型库,它很容易使用.

编辑2:很多人似乎觉得这个答案很有趣,所以我要添加一些信息.

这里的目标是以一种以内存效率的方式使用包含键/值的映射,因此我们将首先查找内存有效的集合.

以下SO问题是相关的(但与此相同).

什么是最有效的Java Collections库？

Jon Skeet提到Trove "只是一个来自原始类型的集合库" [原文如此],实际上,它并没有增加太多功能.我们还可以看到一些关于Trove的内存和速度与默认集合相比的基准(由.duckman提供).这是一个片段:

                      100000 put operations      100000 contains operations 
java collections             1938 ms                        203 ms
trove                         234 ms                        125 ms
pcj                           516 ms                         94 ms

还有一个示例显示使用Trove而不是常规Java HashMap可以节省多少内存:

java collections        oscillates between 6644536 and 7168840 bytes
trove                                      1853296 bytes
pcj                                        1866112 bytes

因此,尽管基准测试总是需要花费一些时间,但很明显,Trove不仅会节省内存,而且会更快.

因此,我们现在的目标是使用Trove(通过在常规HashMap中投入数百万条条目,您的应用开始感到反应迟钝).

你提到了200万对,7个字符的长键和一个String/int映射.

2000000是真的不那么多,但你还是会觉得"对象"开销和原语的常数(UN)拳击整数在一个普通的HashMap {字符串,整数}这就是为什么特罗韦使得很多的意义在这里.

但是,我要指出,如果你可以控制"7个字符",你可以更进一步:如果你只使用ASCII或ISO-8859-1字符,那么你的7个字符就会很长(*).在这种情况下,您可以完全躲避对象创建,并在很长时间内代表您的7个角色.然后,您将使用Trove TLongIntHashMap并完全绕过"Java对象"开销.

你明确指出你的密​​钥是7个字符长然后评论他们是英国邮政编码:我将每个邮政编码映射到一个长的,并通过使用Trove将数百万个键/值对装入内存来节省大量内存.

Trove的优势基本上在于它不会对对象/原语进行持续的装箱/拆箱:在很多情况下,Trove只能直接使用基元和基元.

(*)假设您最多只使用256个代码点/字符,那么它适合7*8 == 56位,这个小到足以适合长整数.

将String密钥编码为longs的示例方法(假设ASCII字符,每个字符一个字节用于简化--7位就足够了):

long encode(final String key) {
    final int length = key.length();
    if (length > 8) {
        throw new IndexOutOfBoundsException(
                "key is longer than 8 characters");
    }
    long result = 0;
    for (int i = 0; i < length; i++) {
        result += ((long) ((byte) key.charAt(i))) << i * 8;
    }
    return result;
}

Answer 2

使用Trove库.

该特罗韦库进行了优化HashMap和HashSet类原语.在这种情况下,TObjectIntHashMap<String>将参数化对象(String)映射到基元int.

Answer 3

首先,你是否测量过这LinkedList确实比a更具记忆效率HashMap,或者你是如何得出这个结论的？其次,LinkedList元素的访问时间是O(n),所以你不能对它进行有效的二进制搜索.如果你想做这样的方法,你应该使用一个ArrayList,它应该给你在性能和空间之间的妥协.然而,再次,我怀疑a HashMap,HashTable或者 - 特别是 - a TreeMap会消耗更多的内存,但前两个将提供常量访问和树映射对数并提供一个更好的接口,正常列表.我会尝试做一些测量,内存消耗的差异究竟是多少.

更新:正如Adamski指出的那样,它String本身而不是它们存储在的数据结构将消耗最多的内存,因此查看特定于字符串的数据结构(例如尝试)可能是个好主意(特别是patricia尝试),这可能会减少字符串所需的存储空间.

Answer 4

你正在寻找的是一个简洁的特里 - 一个trie,它在理论上可以将其数据存储在几乎最小的空间内.

不幸的是,目前没有适用于Java的简洁类库.我的下一个项目之一(在几周内)就是为Java (和其他语言)编写一个.

同时,如果你不介意JNI,你可以参考几个 很好的原生succinct-trie库.

Answer 5

你看过尝试了吗？我没有使用它们,但它们可能适合你正在做的事情.