java - HashMap vs Switch 语句性能

Question

HashMap 本质上具有 O(1) 性能，而开关状态可以具有 O(1) 或 O(log(n))，具体取决于编译器是使用表开关还是查找开关。

可以理解，如果 switch 语句是这样写的，

switch (int) {
    case 1:
    case 2:
    case 3:
    case 4:
    default:
}

那么它将使用 tableswitch 并且显然比标准 HashMap 具有性能优势。但是如果 switch 语句是稀疏的呢？这将是我要比较的两个示例:

HashMap<Integer, String> example = new HashMap<Integer, String>() {{
        put(1, "a");
        put(10, "b");
        put(100, "c");
        put(1000, "d");
}};

.

switch (int) {
    case 1:
        return "a";
    case 10:
        return "b";
    case 100:
        return "c";
    case 1000:
        return "d";
    default:
        return null;
}

什么会提供更高的吞吐量，lookupswitch 或 HashMap？ HashMap 的开销是否在早期为查找开关提供了优势，但最终随着案例/条目数量的增加而逐渐减弱？

编辑:我使用 JMH 尝试了一些基准测试，这是我使用的结果和代码。 https://gist.github.com/mooman219/bebbdc047889c7cfe612 正如你们提到的，lookupswitch 语句优于 HashTable。我仍然想知道为什么。

Answer 1

这里接受的答案是错误的。

http://java-performance.info/string-switch-implementation/

开关总是和 HashMap 一样快。 Switch 语句被转换为直接查找表。对于整数值(整数、枚举、短裤、长整数)，它是对语句的直接查找/jmp。不需要发生额外的散列。对于字符串，它预先计算案例语句的字符串散列，并使用输入字符串的散列码来确定跳转的位置。在发生冲突的情况下，它会执行 if/else 链。现在你可能会想“这和 HashMap 是一样的，对吧？”但事实并非如此。查找的哈希码是在编译时计算的，它不会根据元素的数量而减少(碰撞的可能性更低)。

开关有 O(1) 的查找，而不是 O(n)。 (好吧，事实上，对于少数项目，开关被转换为 if/else 语句。这提供了更好的代码局部性并避免了额外的内存查找。但是，对于许多项目，开关被更改为我上面提到的查找表)。

您可以在此处阅读有关它的更多信息 How does Java's switch work under the hood?