java - treemap vs hashmap 并根据内存使用情况进行排序

Question

我有一个格式很大的文件:

x a
y c
x d
z a
z s
y k

我希望输出排序并以

的形式

x a,d
y c,k
z a,s,k

对于这种类型的任务，哈希是最好的:

直接的 TreeMap 解决方案是这样的:

Map<String, StringBuilder> agg = Maps.newTreeMap();

while ((line = r.readLine()) != null) {

    String[] arr = line.split("\t");
            String key = arr[0];
            String value = arr[1];

    if(agg.containsKey(key)) {
            agg.get(key).append(",").append(value);
        }
        else {
            agg.put(key, new StringBuilder(value));
        }
    }

}
r.close();


System.out.println("Printing results");
FileWriter f = new FileWriter("out.txt");

for (String key : agg.keySet()) {
    f.write(key+"\t"+agg.get(key)+"\n");
}

另一种选择是使用 HashMap ，获取键集，对其进行排序并对其进行迭代。

不同的部分是

    System.out.println("Sorting array");
    List<String> keys = Lists.newArrayList(agg.keySet());
            Collections.sort(keys);
        System.out.println("Printing results");
        FileWriter f = new FileWriter("out.txt");

        for (String key : keys) {
            f.write(key+"\t"+agg.get(key)+"\n");
        }

对我来说，大 O 不太重要，因为它是批处理作业。

对我来说，内存使用更为重要。

哪种策略在内存方面更有效？

HashMap 和排序阶段或 TreeMap 方法中的一瞥

Answer 1

HashMap 在内存利用率方面不是最优的，而是针对特定的操作。它由一个数组支持，该数组在初始化时分配并在其大小达到特定限制时调整大小。因此，内存被急切分配。它的大小总是2的幂，这实际上是为了更快的桶索引计算而进行的计算优化。因此，(未使用的)分配的内存可能会大大超过您的程序实际使用的内存。

TreeMap 提供最佳内存利用率，但与 HashMap 相比，在获取、添加、删除操作方面的性能较差。这通过它的构造函数变得更加明显，它没有任何可以影响其计算复杂性的参数。它的所有条目都是延迟分配的，并与现有条目相关联以形成一棵树。