3

我想存储键值对，其中键是整数，值ArrayLists是Strings.

我不能使用数据库，因为我必须使用代码在线解决特定比赛的问题。

对于少量数据，我可以毫无问题地使用哈希表。但是当我的数据变大时，我的堆大小就用完了。我无法更改堆大小，因为我只需要上传代码并且无法提供工作环境。这就是挑战。

4

6 回答 6

3

  1. 如果字符串经常重复，具有自然语言频率，请不要为同一字符串使用新的对象实例。

    private Map<String, String> sharedStrings = new HashMap<>().

public void shareString(String s) {
    String t = sharedStrings.get(s);
    if (t == null) {
        t = s;
        sharedStrings.put(t, t);
    }
    return t;
}

  2. 字符串的编号可能太慢了。

  3. 将字符串列表打包成一个（分隔一些控制字符），并可能对字符串进行 Gzip 压缩（GZipOutputStream、GZipInputStream）。

  4. 使用足够的初始容量调整哈希图。（对不起，如果我说的很明显。）

  5. 使用巨大的 large 对所有 ArrayList 进行自己的分配String[]：

    int count;
String[] allStrings = new String[999999];

Map<Integer, Long> map = new HashMap<>(9999);

void put(int key, List<String> strings) {
    int start = count;
    for (String s : strings) {
        allStrings[count] = s;
        ++count;
    }
    // high: start index, low: size
    long listDescriptor = (((long)start) << 32) | (count - start);
    map.put(key, listDescriptor);
}

  6. 有使用 int 和 long 等原语的地图实现；例如trove库（我自己没有使用它）。

于 2013-08-12T12:12:33.670 回答
1

使用简单的数组代替ArrayList可能会节省一些额外的内存（但不多）。

如果搜索性能不是优先考虑的，您可以使用 aPair<Integer, List<>>并手动进行搜索。

如果整数的范围有限，只需实例化一个数组List[integer_range]并使用数组索引作为键。

由于您正在使用Strings，您可以尝试使用intern()它们并确保没有重复值。

让我们知道有关您拥有的数据的哪些统计信息 - 键是什么，值是否重复，等等。

于 2013-08-12T11:25:57.110 回答
0

一种可能的优化可能是 ArrayList.trimToSize，它将 ArrayList 使用的存储减少到最低限度。

于 2013-08-12T11:54:42.570 回答
0

一些想法

  1. 如果您可以写入文件，则将数据存储在那里。您可以将键保存在内存中的一组中，以便更快地查找，只需将值写出 - 可以写入单个文件，甚至可以写入每个条目的文件。

  2. 创建您自己的映射实现，将值列表序列化为 String 或 byte[]，然后压缩序列化数据。您必须在读取时反序列化。不过，每次执行 get/put 时，都会受到很大的运行时影响。有关示例，请参见http://theplateisbad.blogspot.co.uk/2011/04/java-in-memory-compression.html 。

  3. 每次查找地图数据时，只需计算列表值，而不是存储它们 - 如果可以的话。

于 2013-08-12T11:22:06.990 回答
0

您可以将 ArrayList 存储在序列化（甚至可能压缩）的ByteBuffers中。当您需要访问列表时，您需要对其进行反序列化、更改/读取，然后将其存储回来。

操作会明显变慢，但您可以进行一些缓存以将 X Arraylists 保留在堆中并将其余部分存储在外部。

于 2013-08-12T12:04:35.987 回答
-1

如果您不能增加堆大小，那么您需要限制哈希表（或您使用的任何其他数据结构）的大小。我建议尝试Apache LRUMap：

LRU地图

Map 的一种实现，它具有最大大小，并在达到最大大小并添加新项目时使用最近最少使用算法从 Map 中删除项目。

如果您真的需要同步版本，那么也可以使用：

可以通过以下方式获得同步版本： Collections.synchronizedMap( theMapToSynchronize ) 如果它将被多个线程访问，则必须同步访问此 Map。甚至并发的 get(Object) 操作也会产生不确定的行为。

如果你不想使用 LRU 来丢失数据，那么你需要编写一个算法来将一些数据保存在你的数据结构中，并保留在持久性存储中，例如文件等。

于 2013-08-12T11:08:08.933 回答