树形图与哈希图以及根据内存使用情况进行排序

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");
}

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

不同的部分是

    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 和排序阶段的 peek 或 TreeMap 方法

Answer 1

如果它是批处理作业，则TreeMap不会像HashMap. HashMap我认为默认的负载系数是 0.75（即地图在大小增长之前可以达到 75%）。

TreeMap如果 O(log n) (IIRC) 不会成为瓶颈，A也会更直接。如果是这样，您可以将 aList与您自己的Tuple对象和自定义一起使用Comparator，但您不会得到 O(1) get()。