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 提供优势，但最终会随着 cases/entries 的数量增加而逐渐减少？

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

Answer 1

这取决于：

如果有几件|固定项目。尽可能使用开关（最坏情况 O(n))
如果有很多项目或者你想在不修改太多代码的情况下添加未来的项目--->使用哈希映射（访问时间被认为是常数时间）
针对您的情况。你不应该担心性能，因为执行时间的差异是纳秒级的。只关注 readability/maintainability 代码。是否值得优化一个简单的案例来提高几纳秒？

Answer 2

在您的情况下，由于您为 HashMap 使用 Integer 键，为 switch 语句使用普通的“int”，因此性能最佳的实现将是 switch 语句，除非通过这段代码的次数非常高（几万或几十万）。

Answer 3

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

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

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

交换机的查找时间复杂度为 O(1)，而不是 O(n)。（好吧，实际上对于少数项目，开关变成了 if/else 语句。这提供了更好的代码局部性并避免了额外的内存查找。但是，对于许多项目，开关变成了查找 table 我在上面提到过）。

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

Answer 4

如果我有那种例子，我会使用 Guava ImmutableMaps（当然你也可以使用 java 9 builder）。

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

关于性能只挑可读性。您稍后会感谢我（1 年后）：D。

Answer 5

TL/DR

基于代码的可读性和可维护性。两者的成本都是 O(1) 并且几乎没有区别（尽管开关通常会稍微快一些）。

在这种特殊情况下，地图会更快，因为开关 return 是一个地址，然后必须转到该地址以识别 return 值。（一个罕见的案例）。如果您的 switch 只是调用函数，那么 Map 也会更快。

为了加快速度，我会确保使用数字大小写并避免通过常量或枚举器（打字稿）使用字符串。

（已编辑）我按预期确认：How does Java's switch work under the hood? 带开关。

更详细的回答

杂草丛中：

switch 语句通常性能更高。它创建一个查找 table 并转到引用并从该点开始。但也有例外。

当您使用一个简单的开关时，例如 return map.get(x) 与开关（1=>'a'、2=>'b' 等） .这是因为映射可以直接 return 开关将停止映射地址并继续映射所需的值，直到中断或结束。

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

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

使用地图解耦数据，这可以获得动态创建“切换”案例的好处。下面更详细。

如果您需要处理多个复杂的 functions/processes，如果您改用地图，read/write 可能会更容易。特别是如果 switch 语句开始超过 20 或 30 个选项。

个人使用的地图案例:

一段时间以来，我一直在 React 应用程序中使用以下模式来处理通量 (Redux/useReducer)。

我创建了一个中心映射，我将触发器映射为键，值是一个功能引用。然后我可以在合适的时间和地点加载案例。

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

这样做让我可以将默认状态、初始化函数、事件等创建到一个逻辑文件结构中，还可以让我在需要时保持较低的占用空间。

记住一个注意事项

使用地图不允许掉落，尽管大多数人认为这种代码有味道。同时它还可以防止意外掉落。

HashMap 与 Switch 语句性能

HashMap vs Switch statement performance

java

hashmap

switch-statement

TL/DR

更详细的回答

杂草丛中：

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