java - HashMap 以简单和复杂的键获得性能

Question

我想要一个 get 操作尽可能快的 map 。键是一组字符串(数据库中的2个表名，它们是相关的)，值是一个整数(数字是数据库中表之间有实际关系的行的id)，

例子:

table 1 - employee
table 2 - company
relationship - employee.comp_id = company.id

我无意阅读 map 中的键。我只想要给定的 2 个表名的关系 ID。所以我写了一个小程序来测试HashMap中的get操作。

public static void main(String args[]) throws NoSuchMethodException, SecurityException {
    int limit = 1000;
    HashMap<Integer, Integer> m1 = new HashMap<>(1000 * 1000);
    HashMap<Set<String>, Integer> m2 = new HashMap<>(1000 * 1000);
    String k1, k2;
    Set<String> k3;
    Integer k4;
    for (int x = 0; x < limit; x++) {
        for (int y = 0; y < limit; y++) {
            k1 = String.valueOf(x);
            k2 = String.valueOf(y);
            k3 = new HashSet<>(Arrays.asList(k1, k2));
            k4 = k3.hashCode();
            m2.put(k3, k4);
            m1.put(k4, k4);
        }
    }

    long t1, t2;
    System.out.println("init");

    t1 = System.nanoTime();
    // block 1 /////////////////////////////////////////////
    for (int x = 0; x < limit; x++) {
        for (int y = 0; y < limit; y++) {
            m1.get(new HashSet<>(Arrays.asList(String.valueOf(x),
                String.valueOf(y))).hashCode());
        }
    }
    // /////////////////////////////////////////////////////
    t2 = System.nanoTime();
    System.out.println(t2 - t1);
    t1 = t2;
    // block 2 /////////////////////////////////////////////
    for (int x = 0; x < limit; x++) {
        for (int y = 0; y < limit; y++) {
            m2.get(new HashSet<>(Arrays.asList(String.valueOf(x),
                String.valueOf(y))));
        }
    }
    // /////////////////////////////////////////////////////
    t2 = System.nanoTime();
    System.out.println(t2 - t1);
}

在我的机器上， block 2 完成执行所用的时间大约是 block 1 的 9 倍。

性能是否取决于用作键的对象的复杂性。在任何一种情况下，我都知道哈希码是通过实现 HasMap.get() 方法计算的。

实际上，对于 block 1 中的代码，哈希码是通过我的代码以及 HashMap 的实现计算的，但性能仍然优于 block 2，其中 Set 的哈希码仅通过 HashMap 的实现计算。

注意在两个 block 中都创建了 Set

Answer 1

get()的表现取决于两件事:

• 参数关键对象的表现hashCode()方法
• 现有关键对象的表现equals()方法

看看 documentation of HashMap.get() .映射包含键值对。要找到键的正确值，equals()使用 key 的方法。在 HashMap ，通过使用它的散列减少了要比较的键的数量。所以hashCode()在您作为参数传递的关键对象上恰好执行一次。

执行HashMap然后有几个可能的关键对象必须比较(最好只有一个)。这意味着它必须执行 equals() 1到n次。

如果你有一个 Set作为键类型，两者都更复杂，因为它们遍历 Set 中包含的所有对象本身。看一下 equals() 的实现和 hashCode()的 HashSet并将其与 String 的比较.

至于你的例子:因为hashCode()一旦影响小于 equals() 就会执行.在您的第一个 block 中，您为 HashSet 计算一次然后 get()为 Integer 再做一次(实际上并没有那么复杂)。这对 hashCode() 没有太大影响。部分。第一个 block 要快得多，因为 equals()为 Integer 执行而不是 HashSet ，这要快得多。