java - 如何快速将 KVP 列表映射到 Map> ..

Question

我很快写了这段代码来完成这项工作

private void map() {
    for (KVPair kvPair : content) {
        String k = kvPair.getKey();
        String v = kvPair.getValue();

        if (mappedContent.containsKey(k)) {
            List<String> values = mappedContent.get(k);
            values.add(v);
        } else {
            List<String> values = new ArrayList<>();
            values.add(v);
            mappedContent.put(k, values);
        }
    }
}

它有效，当使用 1k、2k、4k 和 8k 随机数据运行时，我得到以下性能(100,000 次运行的平均值)

Running with 1,000 pairs
  [perfRun] 100000 iterations took 3 seconds
  [perfRun] Run time: 3758786000 ns. 1 iteration takes 37 us
Running with 2,000 pairs
  [perfRun] 100000 iterations took 6 seconds
  [perfRun] Run time: 6675544000 ns. 1 iteration takes 66 us
Running with 4,000 pairs
  [perfRun] 100000 iterations took 13 seconds
  [perfRun] Run time: 13337145000 ns. 1 iteration takes 133 us
Running with 8,000 pairs
  [perfRun] 100000 iterations took 27 seconds
  [perfRun] Run time: 27109480000 ns. 1 iteration takes 271 us

粗略地说，当大小加倍时，时间加倍。我会采取线性增长，但仍然想知道，我们能做得更好吗？是否可以使用常数时间来映射事物？

Answer 1

我能看到的，mappedContent.containsKey(k)它是不必要的，大约需要 BigO(n) ，可以通过null转义检查，

for (KVPair kvPair : content) {
        String k = kvPair.getKey();
        String v = kvPair.getValue();
        List<String> values = mappedContent.get(k);
        if (values!=null) {
            values.add(v);
        } else {
            values = new ArrayList<>();
            values.add(v);
            mappedContent.put(k, values);
        }
}