我应该如何以高效的内存方式将string键映射到Java中的值？
我正在寻找一种方法来存储一个string – >诠释映射。 当然，HashMap是一个最明显的解决scheme，但由于内存受限，需要存储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
我是否应该去一个自定义树（每个节点单个字符，每个叶子的结果），还是有一个现有的集合，适合这个很好？ string实际上是连续的（英国邮政编码，它们差别不大），所以我期望在这里节省内存。
编辑 ：我刚才看到你提到的string是英国的邮政编码，所以我相当有信心，你不能通过使用Trove TLongIntHashMap得到非常错误（btw Trove是一个小型的图书馆，它很容易使用）。
编辑2 ：很多人似乎觉得这个答案有趣，所以我添加了一些信息。
这里的目标是以一种高效的内存方式使用一个包含键/值的映射，所以我们将首先寻找内存高效的集合。
下面的SO问题是相关的（但与此不完全相同）。
什么是最有效的Java Collections库？
Jon Skeet提到Trove “仅仅是一个原始types的集合库” [原文如此]，实际上，它并没有增加太多的function。 我们还可以看到一些关于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可以节省多less内存：
java collections oscillates between 6644536 and 7168840 bytes trove 1853296 bytes pcj 1866112 bytes
所以，即使基准testing总是需要一定的时间，很明显Trove不仅可以节省内存，而且总是会更快。
所以我们现在的目标是使用Trove（通过将数百万条目放在常规的HashMap中 ，您的应用开始感觉不到响应）。
你提到了200万对，7个字符长的键和一个String / int映射。
200万真的不是那么多，但是你仍然会感觉到“对象”的开销，并且在常规的HashMap {String，Integer}中对Integer的原始元素进行常量（非）的装箱，这就是为什么Trove在这里有很大意义的原因。
然而，我会指出，如果你能控制“7个字符”，你可以走得更远：如果你只使用ASCII或ISO-8859-1字符，那么你的7个字符将适合长*）。 在这种情况下，你可以完全躲避对象的创造，并代表你长长的7个字符。 然后你会使用Trove TLongIntHashMap并绕过“Java对象”开销。
您特别指出，您的密钥长度为7个字符，然后评论他们是英国邮政编码：我会映射每个邮政编码很长，并通过使用Trove将数百万个键/值对配合到内存中，节省了大量的内存。
Trove的优点基本上就是它不会对对象/图元进行不断的装箱/拆箱操作。在很多情况下，Trove只能直接使用图元和图元。
（*）表示您最多只能使用256个码点/字符，然后适合7 * 8 = 56位，这个长度足够小。
将String键编码为long的示例方法（假设为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; }
使用Trove库。
Trove库为基元优化了HashMap和HashSet类。 在这种情况下， TObjectIntHashMap<String>将把参数化对象（ String ）映射到基本int 。
首先，你是否测量过LinkedList确实比HashMap更有记忆效率，或者你是如何得出这个结论的？ 其次， LinkedList的元素访问时间是O(n) ，所以你不能对它进行高效的二进制search。 如果你想这样做，你应该使用一个ArrayList ，它应该给你的性能和空间之间的野兽折衷。 然而，我怀疑HashMap ， HashTable或特别是TreeMap会消耗更多的内存，但是前两个将提供常量访问和树对数映射，并提供一个更好的接口，即普通列表。 我会尝试做一些测量，内存消耗的差异真的是多less。
更新 ：正如Adamski指出的那样，由于String本身，而不是存储在数据结构中的数据结构将占用最多的内存，所以查看特定于string的数据结构（如尝试 （特别是帕特里夏尝试 ），这可能会减lessstring所需的存储空间。
你正在寻找的是一个简洁的线索 – 一种在理论上可以将其数据存储在几乎最小的空间中的线索 。
不幸的是，目前没有用于Java的简洁类库。 我的下一个项目之一（几个星期内）是为Java （和其他语言）编写一个项目。
同时，如果您不介意JNI ，那么您可以参考几个 很好的本地简洁库。
你看了看尝试 。 我没有使用它们，但它们可能适合你在做什么。
自定义树将具有相同的复杂度O(log n) ，不要打扰。 你的解决scheme是健全的，但我会用一个ArrayList而不是LinkedList因为链表为每个存储的值分配一个额外的对象，这将相当于你的情况下的很多对象。
由于Erick使用Trove库写入是一个开始的好地方，因为在存储int原语而不是Integer节省了空间。
但是，您仍然需要存储200万个string实例。 鉴于这些是地图中的关键，实习他们不会提供任何好处，所以接下来我要考虑的是是否有一些可以利用的string的特征。 例如：
- 如果
Strings表示常用单词的句子，那么您可以将string转换为Sentence类，并在单词中实习。 - 如果string只包含Unicode字符的一个子集（例如只有字母AZ或字母+数字），那么可以使用比Java的Unicode更紧凑的编码scheme。
- 您可以考虑将每个string转换为UTF-8编码的字节数组，并将其封装在类
MyString。 显然，这里的权衡是花在查找上的额外时间。 - 您可以将地图写入文件，然后将内存映射到文件的一部分或全部。
- 你可以考虑像Berkeley DB这样的库，它允许你定义持久化映射并在内存中caching一部分映射。 这提供了一个可扩展的方法。
也许你可以用一个RadixTree ？
使用java.util.TreeMap而不是java.util.HashMap 。 它使用了一个红色的黑色二叉search树，并没有使用比保存包含地图中元素的注释所需的更多的内存。 没有额外的桶，不像HashMap或Hashtable。
我认为解决的办法是在Java之外进行一点。 如果你有这么多的值，你应该使用一个数据库。 如果你不想安装Oracle，SQLite是快速和容易的。 这样你不需要立即需要的数据就被存储在磁盘上，所有的caching/存储都是为你完成的。 build立一个表格和两列的数据库根本不需要很多时间。
我会考虑使用一些caching，因为它们通常具有溢出到磁盘的能力。
您可以创build一个与您的需求相匹配的关键类。 也许是这样的：
public class MyKey implements Comparable<MyKey> { char[7] keyValue; public MyKey(String keyValue) { ... load this.keyValue from the String keyValue. } public int compareTo(MyKey rhs) { ... blah } public boolean equals(Object rhs) { ... blah } public int hashCode() { ... blah } }
试试这个
OptimizedHashMap<String, int[]> myMap = new OptimizedHashMap<String, int[]>(); for(int i = 0; i < 2000000; i++) { myMap.put("iiiiii" + i, new int[]{i}); } System.out.println(myMap.containsValue(new int[]{3})); System.out.println(myMap.get("iiiiii" + 1));
public class OptimizedHashMap<K,V> extends HashMap<K,V> { public boolean containsValue(Object value) { if(value != null) { Class<? extends Object> aClass = value.getClass(); if(aClass.isArray()) { Collection values = this.values(); for(Object val : values) { int[] newval = (int[]) val; int[] newvalue = (int[]) value; if(newval[0] == newvalue[0]) { return true; } } } } return false; }
实际上，HashMap和List对于通过邮政编码查找int这样的特定任务来说过于普遍。 你应该利用哪些数据被使用的知识。 其中一个选项是使用带叶子的前缀树来存储int值。 另外，如果（我的猜测）有很多具有相同前缀的代码映射到相同的整数，它可能会被修剪。
通过邮政编码查找int将在这样的树中是线性的，并且如果代码数量增加，则不会增长，与在二进制search情况下的O（log（N））相比。
既然你打算使用哈希，你可以尝试基于ASCII值的string的数值转换。 最简单的想法是
int sum=0; for(int i=0;i<arr.length;i++){ sum+=(int)arr[i]; }
哈希“总和”使用一个明确的散列函数。 您将使用基于预期input模式的散列函数。 例如，如果你使用除法
public int hasher(int sum){ return sum%(a prime number); }
select一个不接近2的精确幂的素数可以提高性能并给出更好的均匀散列的密钥分布。
另一种方法是根据各自的位置来权衡字符。
例如：如果使用上述方法，则“abc”和“cab”将被哈希到同一个位置。 但是如果你需要将它们存储在两个不同的位置，就像我们使用数字系统一样给位置加权。
int sum=0; int weight=1; for(int i=0;i<arr.length;i++){ sum+= (int)arr[i]*weight; weight=weight*2; // using powers of 2 gives better results. (you know why :)) }
由于您的样本相当大，因此您应避免使用链接机制进行碰撞，而不要使用探针序列。 毕竟，你会select什么方法完全取决于你的应用程序的性质。
问题是对象的内存开销，但使用一些技巧，你可以尝试实现自己的哈希集。 像这样的东西。 像其他人说，string有相当大的开销，所以你需要“压缩”它以某种方式。 另外，尽量不要在哈希表中使用太多的数组（列表）（如果你使用链式哈希表），因为它们也是对象，也有开销。 更好的做开放寻址哈希表。
