针对少量条目实现Java Map的最快方法

Question

针对少量条目实现Java Map的最快方法

javaperformancecollectionsdictionary

18

对于非常少量的条目（小于15个），最快的 java.util.Map 实现是什么？同时支持线程安全和非线程安全。

- patstuart

3

请使用 ConcurrentHashMap 实现线程安全。 - Braj

你正在将什么映射到什么？例如，它是一个 Map<Integer, String>，还是一个 Map<Double, Long> 等等？ - arshajii

3个回答

3

如果你想要一个紧凑的Map，可以使用：

Map map = Collections.synchronizedMap(new HashMap<>());

如果你不需要线程安全，可以省略Collections.synchronizedMap。如果你希望集合使用最少的内存，可以像这样做：

Map map = new HashMap<>(4, 1.0f);

这将存储4个键/值（或更多），并且使用尽量少的内存。它将比空标准HashMap小约一半。

使用ConcurrentHashMap的问题在于，对于小型集合来说它过于复杂，即它使用许多对象和大约1 KB的内存（如果为空）。

为了获得准确的内存使用情况，您需要在命令行上使用-XX-UseTLAB。

public static void main(String sdf[]) throws Exception {
    testCreateSize("ConcurrentHashMap", ConcurrentHashMap::new);
    testCreateSize("HashMap", HashMap::new);
    testCreateSize("synchronized HashMap", () -> {
        return Collections.synchronizedMap(new HashMap<>());
    });
    testCreateSize("small synchronized HashMap", () -> {
        return Collections.synchronizedMap(new HashMap<>(4, 2.f));
    });

}

public static void testCreateSize(String description, Supplier<Map<Integer, Integer>> supplier) {
    // warmup.
    supplier.get();
    long start = memoryUsed();
    Map<Integer, Integer> map = supplier.get();
    for (int i = 0; i < 4; i++) {
        map.put(i, i);
    }
    long used = memoryUsed() - start;
    System.out.printf("Memory used for %s, was %,d bytes%n", description, used);

}

public static long memoryUsed() {
    return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
}

打印

Memory used for ConcurrentHashMap, was 272 bytes
Memory used for HashMap, was 256 bytes
Memory used for synchronized HashMap, was 288 bytes
Memory used for small synchronized HashMap, was 240 bytes

如果在使用地图的类中使用同步方法，可以节省32个字节。

- Peter Lawrey

但是ConcurrentHashMap比Collections.synchronizedMap(...)更加高效。 - Kao

@Kao 对于大型集合，是的，但对于许多小集合，CHM相当糟糕。 - Peter Lawrey

1

@Kao 不是“相当糟糕”，但效率较低。 - Peter Lawrey

这不是一个公平的实验。你没有使用ConcurrentHashMap的int initialCapacity，float loadFactor或concurrencyLevel。 - joseph

@joseph 确定。你也可以对HashMap做同样的操作。 - Peter Lawrey

@PeterLawrey 给出了非常好的建议！我一定会尝试使用最小的 Map 大小和 1.0f 作为负载因子。 - Gaurav

1

我会说HashMaps。

HashMap<String, Object> map = new HashMap <String, Object> ();

这将为您提供一个非常简单的映射，其键类型为String，值类型为Object。

编辑：这是一个非线程安全的版本。

您可以查看ConcurrentHashMaps以获取线程安全映射。

- rageandqq

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kao · Accepted Answer

如果所有的条目都可以表示为枚举类型，应该使用EnumMap：

“此实现结合了 Map 接口的丰富性和安全性与接近数组速度的速度。如果您想将枚举映射到值，则应始终首选 EnumMap 而不是数组。”

如果不能使用枚举类型，HashMap 是一个好的解决方案。它提供基本操作（如 get() 和 put()）的常数时间：

“假设散列函数将元素适当地分散在桶中，则此实现对于基本操作（get 和 put）提供恒定时间性能。”

请记得在 HashMap 中设置低容量值：

“因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低）。”

当然，上述实现都不是线程安全的。在这种情况下，最好的线程安全实现将是ConcurrentHashMap。它结合了 HashMap 的高性能和线程安全。这里有不同 Map 实现的很好的比较。

编辑：这里有一个有趣的比较不同的 HashMap 实现。至少对于原始类型，似乎存在比内置的 HashMap 更快的替代品。

编辑2：由于 Peter Lawrey 的回答，我决定执行一些测试，比较 ConcurrentHashMap 和 Collections.synchronizedMap()：

public static void main(String[] args) {
      System.out.println("\n===== ConcurrentHashMap =====");
      testMap(new ConcurrentHashMap<>());
      System.out.println("\n===== Collections.synchronizedMap()  =====");
      testMap(Collections.synchronizedMap(new HashMap<>()));
}

    static final int N = 5;
    static final int R = 1000000;

    public static void testMap(Map map) {
        long startTime = System.nanoTime();

        System.out.println("\n-- " + N*R + " puts(key, value) --");
        startTime = System.nanoTime();
        for (int j = 0; j < R; j++) {
            for (int i = 0; i < N; i++) 
                map.put(i, new float[] { 0f, 1f, 2f, 3f, 4f });
            map.clear();
        }
        System.out.println((System.nanoTime() - startTime) / 1000000000.0);

        System.out.println("\n-- " + N*R + " get(key) --");
        startTime = System.nanoTime();
        for (int j = 0; j < R; j++) {
            for (int i = 0; i < N; i++)  
                map.get(i); 
            map.clear();
        }
        System.out.println((System.nanoTime() - startTime) / 1000000000.0);
    }

}

我的测试结果如下：

===== ConcurrentHashMap =====

5000000 次 puts(key, value) - 0.99714195 秒
5000000 次 get(key) - 0.452227427 秒

===== Collections.synchronizedMap() =====

5000000 次 puts(key, value) - 0.586431367 秒
5000000 次 get(key) - 0.376051088 秒

所以，Peter 可能是正确的 - 对于小型的映射表，Collections.synchronizedMap() 更快。