HashMap通过简单而复杂的键获得性能

Question

我想要一张其get操作尽可能快的地图。键是字符串集（数据库中有2个相关的表名），值是整数（数字是数据库中具有表之间实际关系的行的ID），

例如：

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

我无意阅读地图中的按键。我只想要给定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);
}

在我的机器上，块2​​完成块执行所需的时间比块1多大约9倍。

性能是否取决于用作键的对象的复杂性。无论哪种情况，我都知道哈希码是由HasMap.get（）方法的实现计算出来的。

实际上，对于块1中的代码，哈希代码是由我的代码以及HashMap的实现来计算的，但性能仍然好于块2，后者中Set的哈希码仅由HashMap的实现来计算。

请注意，两个块中都在创建Set

Answer 1

的性能get()取决于两件事：

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

看看的文档HashMap.get()。映射包含键值对。为了找到正确的键值，使用了键的equals()方法。在中HashMap，要比较的键数通过使用哈希值来减少。因此hashCode()，在您作为参数传递的键对象上仅执行一次。

然后，的实现HashMap有几个可能要比较的关键对象（理想情况下只有一个）。这意味着它必须执行equals()1到n次。

如果您具有Setas键类型，则两者都会更复杂，因为它们会迭代Set自身中包含的所有对象。看看执行的equals()和hashCode()的HashSet和比较它的那些String。

以您的示例为例：由于hashCode()恰好执行一次，因此其影响比少equals()。在第一个块中，您需要对其进行一次计算HashSet，然后get()再次对其进行计算Integer（这实际上并不那么复杂）。这在hashCode()零件上没有多大区别。第一个块要快得多，因为equals()执行的是Integer代替HashSet，它要快得多。