java - 如何快速将 KVP 列表映射到 Map<Key, List<Value>> ..

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