HashMap与Switch语句性能比较

Question

HashMap基本上具有O(1)的性能，而switch语句可以具有O(1)或O(log(n))的性能，这取决于编译器是否使用tableswitch或lookup switch。

可以理解的是，如果一个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 的开销是否会使得 lookupswitch 在开始时具有优势，但随着 case/entry 数量的增加而逐渐减少？

编辑：我使用了 JMH 进行了一些基准测试，以下是我的结果和使用的代码。https://gist.github.com/mooman219/bebbdc047889c7cfe612 正如你们所说，lookupswitch 语句的性能优于 HashTable。我仍然想知道为什么。

- Joe C

---

与几乎所有性能问题一样：您必须进行测量。 https://dev59.com/hHRB5IYBdhLWcg3wz6UK 我期待您的结果 :) - Matt Ball

一个好的默认答案是告诉你去测量差异... 我期望 switch 语句会更快，因为它应该相当于更少的指令。对于 C 和 GCC，在不同的上下文中（例如 switch 中有多少个 case，索引等），switch 语句将被实现为 if/elseif 链、跳转表等。 - Morten Jensen

除了复杂度远低于哈希表，lookupswitch 机制还具有重要的引用局部性优势。哈希表必须执行以下步骤：1. 解引用您的整数键；2. 解引用桶数组；3. 解引用从 1 派生的索引处的数组中的 Node 实例；4. 解引用节点的 Integer 键以确保它等于请求的键；5. 最后解引用节点的返回值。 - Marko Topolnik

尝试使用字符串键而不是整数键运行相同的代码可能会很有趣。 - MonoThreaded

如果您对地图键的访问进行随机化，那么基准测试将会更有趣。如果连续多次访问相同的键，我想JIT可能会重写switch语句... - Lukas Eder

Answer 1

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

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

Switch语句将始终像哈希表一样快，甚至更快。 Switch语句被转换为直接查找表。 对于整数值（int，枚举，short，long），它是到该语句的直接查找/ jmp。 不需要进行额外的哈希处理。 对于字符串，它预先计算了情况语句的字符串哈希，并使用输入字符串的哈希码确定要跳转的位置。 在发生冲突的情况下，它执行if / else链。 现在你可能会想，“这与HashMap相同，对吧？”，但这不是真的。 查找的哈希代码是在编译时计算的，并且不会根据元素数量减少（冲突的机会较低）。

Switch语句具有O（1）的查找效率，而不是O（n）。 （好吧，实际上对于少量项目，Switch语句被转换为if / else语句。 这提供更好的代码局部性并避免了额外的内存查找。 但是，对于许多项目，Switch语句会转换为我上面提到的查找表）。

您可以在此处阅读更多信息 Java Switch语句的工作原理？

- Cogman

---

我说哪个更快了吗？我没有这样说。我的答案是在哪种情况下哪一个更方便，为什么我们不需要担心该情况的性能，因为我们有大量其他用例需要优化性能，而不是这个简单的情况。 - LHA

你说Switches的时间复杂度是O(1)，这并不适用于所有语言/编译器。它取决于编译器，最坏情况下它是O(n)。 - LHA

Answer 2

这要看情况：

1. 如果只有几个固定的项目，使用switch语句（最坏情况O（n））。

2. 如果有很多项目，或者您想添加未来的项目而不修改太多代码--->使用哈希映射（访问时间被认为是常数时间）。

3. 不应该为了这种情况而尝试提高性能，因为执行时间的差异仅为纳秒级别。重点关注代码的可读性/可维护性。值得优化一个简单的情况以改善几个纳秒吗？

- LHA

---

为什么很多项对于 switch 语句来说是不好的？我听说编译器会为我们优化和在 switch 语句中使用二叉树。 - KRoy

这是不正确的。如果你能转换，就切换。它总是像哈希表一样快，甚至更快。对于整数值和枚举值，它会转换成内存查找表，这没有哈希的开销。对于字符串，它创建HashMap并使用它来切换。唯一可能比if / else块慢的是代码局部性低。 - Cogman

当人们说类似于“你不应该担心性能”的话时，我真的很讨厌。是的，在某些情况下这可能是完全有效的，但总体而言，我们的行业目前正在生产成千上万个软件包，它们的性能非常糟糕，不可接受（考虑到我们当前使用的硬件）。问题并不在于人们过分关注性能，恰恰相反。即使有些人会过分关注性能，那么这绝对比“YAGNI”方法在性能优化方面应用时造成的问题要少得多。:/ - Per Lundberg

再也听不下去这句“不要担心性能”的话了。这就是人们声称Java很慢的原因。在今天的应用程序中，每秒处理数十亿甚至更多的事件并不是不切实际的。特别是对于开发库来说，关注性能非常重要。因此，纳秒级别的性能也很重要。问题并不涉及代码风格，请回答问题...如果您能的话。 - PeMa

@PerLundberg：你看到我说“对于你的情况”了吗？这意味着在这种情况下，问题所有者不应该担心性能。我并没有说在所有情况下都不用担心性能。我们总是需要关注性能。我们也需要为性能优化我们的API，但不是每一行源代码都需要优化。因为可读性/可维护性也很重要。有时我们需要做出某种权衡。 - LHA

Answer 3

TL/DR

在代码的可读性和可维护性方面进行选择。两者成本都是O(1)，几乎没有什么区别（尽管switch通常会稍微快一些）。

在这种特殊情况下，使用map会更快，因为switch返回一个地址，然后必须去该地址以识别返回值。 （一个罕见的例子）。如果您的switch只是调用函数，那么Map也会更快。

为了使事情更快，我会确保使用数字案例并通过常量或枚举器（typescript）避免使用字符串。

（编辑）我通过How does Java's switch work under the hood? with switches确认了我的期望。

更详细的答案

深入讨论：

switch语句通常具有更高的性能。它创建一个查找表和goto引用，并从该点开始。但是有例外情况。

当您使用简单的switch，例如return map.get(x) vs. switch(1=>'a', 2=>'b'等)时。那是因为map可以直接返回所需的值，而switch将停止映射地址并继续执行，直到break或结束为止。

无论如何，它们在执行成本方面应该非常相似。

考虑代码的可维护性和可读性

使用map可以解耦数据，这可以获得动态创建“switch”案例的好处。更详细请参见下文。

如果您需要处理几个复杂的函数/进程，则使用map可能更容易阅读/编写。特别是如果switch语句开始超过20或30个选项。

个人使用地图的案例示例：

我已经在React应用程序中的flux（Redux/useReducer）中使用以下模式一段时间了。

我创建一个中央映射，其中将触发器映射为键，值是功能引用。然后我可以在何时何地加载案例。

最初，我使用它来能够将用例拆分以减少文件大小，并以更有组织的方式将类似功能的案例组合在一起。尽管后来我将其发展为在域中加载并配置事件和数据的域钩子，例如useUser、useFeedback、useProfile等...

这样做不仅允许我将默认状态、初始化函数、事件等放入逻辑文件结构中，还允许我保持占用空间低直到需要。

需要注意的一点

使用map不允许直接跳过，尽管大多数人都认为这是代码味道。同时，它还可以防止意外掉落。

- Steve Cook

Answer 4

在您的情况下，由于您正在使用 HashMap 的 Integer 键和纯' int '用于 switch 语句，因此最佳执行效果的实现将是 switch 语句，除非通过代码的这个部分的次数非常高（几万或几十万）。

- sqlsword

Answer 5

如果我有这样的例子，我会使用Guava ImmutableMaps（当然您也可以使用Java 9构建器）。

private static final Map<String, String> EXAMPLE = ImmutableMaps.<String, String>>builder()
    .put("a", "100")
    .put("b", "200")
    .build(); 

这样它们就是不可变的，并且只被初始化一次。

有时我会这样使用策略模式：

private static final Map<String, Command> EXAMPLE = ImmutableMaps.<String, String>>builder()
    .put("a", new SomethingCool())
    .put("b", new BCool())
    .build(); 

private static final Command DEFAULT= new DefCommand();

使用：

EXAMPLE.getOrDefault("a", DEFAULT).execute(); //java 8

关于性能，选择可读性。你以后会感谢我的（一年后）:D。

- John Tribe