在任意键上使用 EnumSet 或 EnumMap
Using EnumSet or EnumMap on arbitrary keys
我们知道 EnumSet 和 EnumMap 比 HashSet/HashMap 更快，这是由于位操作的强大功能。但是，我们真的在真正重要的时候利用了 EnumSet/EnumMap 的真正力量吗？如果我们有一组数百万条记录，我们想知道该组中是否存在某个对象，我们可以利用 EnumSet 的速度吗？
我查了一下，但没有发现任何讨论此问题的内容。到处都是常见的东西，即因为 EnumSet 和 EnumMap 使用一组预定义的键，在小集合上查找非常快。我知道枚举是编译时常量，但我们能否两全其美 - 一个类似于 EnumSet 的数据结构而不需要枚举作为键？
有趣的见解；简短的回答是否定的，但你的问题是探索一些好的数据结构设计概念，我将尝试讨论这些概念。
首先，让我们谈谈 HashMap（HashSet 在内部使用 HashMap，因此它们共享大多数行为）；基于散列的数据结构非常强大，因为它快速且通用。它很快（即大约 O(1)），因为我们可以通过非常少量的计算找到我们正在寻找的密钥。粗略地说，我们有一个键列表数组，将键转换为该数组中的整数索引，然后在关联列表中查找键。随着映射变大，支持数组会反复调整大小以容纳更多列表。假设列表均匀分布，此查找非常快。因为这适用于任何通用对象（具有适当的 .hashcode() 和 .equals()），所以它对几乎任何应用程序都很有用。
枚举有几个有趣的属性，但为了高效查找，我们只关心其中两个 - 它们通常很小，并且具有固定数量的值。正因为如此，我们可以做得比HashMap更好；具体来说，我们可以将每个可能的值映射到一个唯一的整数，这意味着我们不需要计算散列，也不需要担心散列冲突。所以 EnumMap 简单地存储一个与枚举大小相同的数组并直接在其中查找：
// From Java 7's EnumMap
public V get(Object key) {
return (isValidKey(key) ?
unmaskNull(vals[((Enum)key).ordinal()]) : null);
}
去除一些必需的 Map 健全性检查，它只是：
return vals[key.ordinal()];
请注意，这 概念上 与标准 HashMap 没有什么不同，它只是避免了一些计算。 EnumSet 更聪明一点，使用一个或多个 long 中的位来表示数组索引，但在功能上它与 EnumMap 的情况没有什么不同——我们分配了足够的槽来覆盖所有可能的枚举值，并且可以使用它们的整数 .ordinal() 而不是计算哈希值。
那么 EnumMap 比 HashMap 快多少？它显然更快，但实际上并没有 快得多。 HashMap 已经是一个非常高效的数据结构，因此对其进行任何优化只会产生略微更好的结果。特别是，HashMap 和 EnumMap 渐近地具有相同的速度 (O(1))，这意味着当它们变大时，它们表现得同样好。这是为什么没有像 EnumMap 这样更通用的数据结构的主要原因 - 因为相对于 HashMap.
来说不值得付出努力
我们不想要更通用的“FiniteKeysMap”的第二个原因是它会使我们作为用户的生活变得更加复杂，如果它能显着提高速度，那将是值得的，但因为它不是会很麻烦。我们必须为任何可能是此映射中的键的类型定义一个接口（可能还有一个 factory pattern）。该接口需要保证每个唯一实例 returns 范围 [0-n) 中的唯一哈希码，并且还需要为地图提供一种获取 n 和可能所有 [=36] 的方法=] 元素。最后两个操作作为静态方法会更好，但由于我们不能在接口中定义静态方法，因此必须将它们直接传递给我们创建的每个映射，或者具有此信息的单独工厂对象将具有存在并在构造时传递给 map/set。因为枚举是语言的一部分，所以它们可以免费获得所有这些好处，这意味着最终用户程序员无需支付任何费用。
而且这个界面也很容易出错；假设您的类型正好具有 100,000 个唯一值。它应该实现我们的接口吗？它可以。但你实际上可能搬起石头砸自己的脚。这会占用大量不必要的内存，因为我们的 FiniteKeysMap 会分配一个新的 100,000 长度数组来表示一个空映射。一般来说，这种浪费 space 不值得这种数据结构提供的边际改进。
简而言之，虽然你的想法是可行的，但并不实用。 HashMap 效率如此之高，以至于尝试为非常有限的案例创建单独的数据结构所增加的复杂性远远超过价值。
对于更快 .contains() 检查的特定情况，您可能喜欢 Bloom Filters. It's a set-like data structure that very efficiently stores very large sets, with the condition that it may sometimes incorrectly say an element is in the set when it is not (but not the other way around - if it says an element isn't in the set, it's definitely not). Guava provides a nice BloomFilter 实施。
我们知道 EnumSet 和 EnumMap 比 HashSet/HashMap 更快，这是由于位操作的强大功能。但是，我们真的在真正重要的时候利用了 EnumSet/EnumMap 的真正力量吗？如果我们有一组数百万条记录，我们想知道该组中是否存在某个对象，我们可以利用 EnumSet 的速度吗？
我查了一下，但没有发现任何讨论此问题的内容。到处都是常见的东西，即因为 EnumSet 和 EnumMap 使用一组预定义的键，在小集合上查找非常快。我知道枚举是编译时常量，但我们能否两全其美 - 一个类似于 EnumSet 的数据结构而不需要枚举作为键？
有趣的见解；简短的回答是否定的，但你的问题是探索一些好的数据结构设计概念，我将尝试讨论这些概念。
首先，让我们谈谈 HashMap（HashSet 在内部使用 HashMap，因此它们共享大多数行为）；基于散列的数据结构非常强大，因为它快速且通用。它很快（即大约 O(1)），因为我们可以通过非常少量的计算找到我们正在寻找的密钥。粗略地说，我们有一个键列表数组，将键转换为该数组中的整数索引，然后在关联列表中查找键。随着映射变大，支持数组会反复调整大小以容纳更多列表。假设列表均匀分布，此查找非常快。因为这适用于任何通用对象（具有适当的 .hashcode() 和 .equals()），所以它对几乎任何应用程序都很有用。
枚举有几个有趣的属性，但为了高效查找，我们只关心其中两个 - 它们通常很小，并且具有固定数量的值。正因为如此，我们可以做得比HashMap更好；具体来说，我们可以将每个可能的值映射到一个唯一的整数，这意味着我们不需要计算散列，也不需要担心散列冲突。所以 EnumMap 简单地存储一个与枚举大小相同的数组并直接在其中查找：
// From Java 7's EnumMap
public V get(Object key) {
return (isValidKey(key) ?
unmaskNull(vals[((Enum)key).ordinal()]) : null);
}
去除一些必需的 Map 健全性检查，它只是：
return vals[key.ordinal()];
请注意，这 概念上 与标准 HashMap 没有什么不同，它只是避免了一些计算。 EnumSet 更聪明一点，使用一个或多个 long 中的位来表示数组索引，但在功能上它与 EnumMap 的情况没有什么不同——我们分配了足够的槽来覆盖所有可能的枚举值，并且可以使用它们的整数 .ordinal() 而不是计算哈希值。
那么 EnumMap 比 HashMap 快多少？它显然更快，但实际上并没有 快得多。 HashMap 已经是一个非常高效的数据结构，因此对其进行任何优化只会产生略微更好的结果。特别是，HashMap 和 EnumMap 渐近地具有相同的速度 (O(1))，这意味着当它们变大时，它们表现得同样好。这是为什么没有像 EnumMap 这样更通用的数据结构的主要原因 - 因为相对于 HashMap.
我们不想要更通用的“FiniteKeysMap”的第二个原因是它会使我们作为用户的生活变得更加复杂，如果它能显着提高速度，那将是值得的，但因为它不是会很麻烦。我们必须为任何可能是此映射中的键的类型定义一个接口（可能还有一个 factory pattern）。该接口需要保证每个唯一实例 returns 范围 [0-n) 中的唯一哈希码，并且还需要为地图提供一种获取 n 和可能所有 [=36] 的方法=] 元素。最后两个操作作为静态方法会更好，但由于我们不能在接口中定义静态方法，因此必须将它们直接传递给我们创建的每个映射，或者具有此信息的单独工厂对象将具有存在并在构造时传递给 map/set。因为枚举是语言的一部分，所以它们可以免费获得所有这些好处，这意味着最终用户程序员无需支付任何费用。
而且这个界面也很容易出错；假设您的类型正好具有 100,000 个唯一值。它应该实现我们的接口吗？它可以。但你实际上可能搬起石头砸自己的脚。这会占用大量不必要的内存，因为我们的 FiniteKeysMap 会分配一个新的 100,000 长度数组来表示一个空映射。一般来说，这种浪费 space 不值得这种数据结构提供的边际改进。
简而言之，虽然你的想法是可行的，但并不实用。 HashMap 效率如此之高，以至于尝试为非常有限的案例创建单独的数据结构所增加的复杂性远远超过价值。
对于更快 .contains() 检查的特定情况，您可能喜欢 Bloom Filters. It's a set-like data structure that very efficiently stores very large sets, with the condition that it may sometimes incorrectly say an element is in the set when it is not (but not the other way around - if it says an element isn't in the set, it's definitely not). Guava provides a nice BloomFilter 实施。