HashMap 与 Switch 语句性能

Question

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

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

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

那么它将使用表开关，并且显然比标准 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 的开销是否会在早期为 lookupswitch 提供优势，但最终会随着案例/条目数量的增加而逐渐减少？

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

原文由 Joe C 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这取决于：

1. 如果有几件物品 |固定项目。尽可能使用 switch（最坏情况 O(n)）

2. 如果有很多项目或者你想在不修改太多代码的情况下添加未来的项目—>使用哈希映射（访问时间被认为是常数时间）

3. 你不应该尝试提高这种情况的性能，因为执行时间的差异是纳秒级的。只关注代码的可读性/可维护性。优化一个简单的案例以提高几纳秒是否值得？

原文由 LHA 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

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

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

开关总是和散列映射一样快，就好像不快一样。 Switch 语句被转换为直接查找表。在整数值（整数、枚举、短裤、长裤）的情况下，它是对语句的直接查找/跳转。不需要进行额外的散列。如果是 String，它会预先计算 case 语句的字符串散列，并使用输入 String 的散列码来确定跳转到哪里。在发生碰撞的情况下，它会执行 if/else 链。现在你可能会想“这和 HashMap 一样，对吧？”但事实并非如此。查找的哈希码是在编译时计算的，它不会根据元素的数量减少（较低的冲突机会）。

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

您可以在此处阅读更多相关信息 Java 的开关如何在后台工作？

原文由 Cogman 发布，翻译遵循 CC BY-SA 4.0 许可协议