复合键：如何处理它们的指南

复合键是指需要数据组合来定义地图或缓存查找的“键”。例如，您可能需要根据客户名称和用户角色来缓存值。在这种情况下，您的缓存需要能够根据这两个（或更多）条件中的每一个来存储唯一值。

在代码中可以通过几种不同的方式处理复合键。

将条件组合成字符串

最容易想到的第一个答案是将标准组合成一个字符串以用作键。这很简单，不需要花费太多精力：

 private String getMapKey(Long userId, String userLocale) { return userId + "." userLocale; }

这是处理该问题的一个非常基本的方法。使用字符串密钥可以使调试和调查变得更容易，因为缓存密钥采用人类可读的格式。但这种方法有几个问题需要注意：

1. 它需要在每次与地图交互时创建一个新字符串。尽管此字符串分配通常很小，但如果频繁访问映射，则可能会导致大量分配，这会花费时间并需要进行垃圾收集。字符串分配的大小也可以更大，具体取决于密钥的组件有多大或有多少。

   
   

2. 您需要确保您创建的复合键不会被欺骗为另一个键值：

 public String getMapKey(Integer groupId, Integer accessType) { return groupId.toString() + accessType.toString(); }

在上面，如果您有 groupId = 1 和 accessType = 23，那么这将是与 groupId = 12 和 accessType = 3 相同的缓存键。通过在字符串之间添加分隔符，您可以防止这种重叠。但要小心密钥的可选部分：

 public String getMapKey(String userProvidedString, String extensionName) { return userProvidedString + (extensionName == null ? "" : ("." + extensionName)); }

在上面的示例中，extensionName 是密钥的可选部分。如果扩展名是可选的，则 userProvidedString 可以包含分隔符和有效的扩展名，并访问它不应该访问的缓存数据。

使用字符串时，您需要考虑如何组合数据以避免键中的任何冲突。特别是围绕任何用户生成的密钥输入。

使用嵌套映射/缓存

另一种选择是根本不组合键，而是嵌套数据结构（地图的地图的地图）：

 Map<Integer, Map<String, String>> groupAndLocaleMap = new HashMap<>(); groupAndLocaleMap.computeIfAbsent(userId, k -> new HashMap()).put(userLocale, mapValue);

这样做的优点是，在与映射交互时不需要分配任何新内存，因为键的传入值已经分配。虽然您需要进行多次查找才能获得最终值，但地图会更小。

但这种方法的缺点是，嵌套越深入，它就会变得越复杂。即使只有两个级别，地图初始化也可能看起来令人困惑。当您开始处理 3 个或更多数据时，这可能会导致您的代码变得非常冗长。最重要的是，每个级别都需要空检查以避免空指针。

某些“关键部分”也可能无法很好地用作地图键。数组或集合没有比较其内容的默认 equals 方法。因此，您要么需要实现它们，要么使用其他替代方案。

使用嵌套映射也可能会降低空间效率，具体取决于每个级别的键的独特程度。

创建复合键对象

最后一个选项不是将键值组合成字符串，而是为键创建一个自定义对象：

 private class MapKey { private final int userId; private final String userLocale; public MapKey(int userId, String userLocale) { this.userId = userId; this.userLocale = userLocale; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MapKey mapKey = (MapKey) o; return userId == mapKey.userId && Objects.equals(userLocale, mapKey.userLocale); } @Override public int hashCode() { return Objects.hash(userId, userLocale); } }

虽然每次交互仍然需要为新对象分配新的内存。对象键分配明显小于复合字符串所需的分配。原因是组成密钥的部分不需要作为字符串重新分配。相反，只有包装对象键需要新的内存。

复合键对象还可以允许自定义键相等和哈希码实现。例如忽略字符串中的大写，或者使用数组或集合作为键的一部分。

但这里的缺点是，它比复合字符串需要更多的代码。它需要确保您的映射的关键类中具有有效的 equals 和 hashcode 契约。

那么我应该选择哪一个呢？

一般来说，我建议使用复合字符串键。它简单易懂，需要的代码最少，并且最容易后期调试。虽然它可能是执行速度最慢的，但编写简单、可读的代码通常比使用其他两个选项之一获得的好处更重要。记住：

“过早优化是万恶之源”Donald Knuth

如果您没有证据或理由相信您的地图/缓存查找将成为性能瓶颈，请选择可读性。

但是，如果您的地图或缓存的吞吐量非常高，那么最好切换到其他两个选项之一。让我们看看这三者在性能以及内存分配大小方面如何进行比较。

为了测试上面的 3 个场景，我编写了代码来复制复合键的所有 3 个场景的相同实现。键本身由一个整数值、一个字符串值和一个长整型值组成。所有三种实现在每次运行时都使用相同的测试数据来构建密钥。

所有运行均使用映射中的 100 万条记录执行（使用了 Java 的哈希映射）。使用不同的密钥大小组合构建密钥进行了 3 次运行：

• 100 个整数、100 个字符串、100 个长整型 — 100 万个唯一键

• 1 个 int、1 个字符串、1,000,000 个 long——100 万个唯一键

• 1,000,000 个整数、1 个字符串、1 个长整型 — 100 万个唯一键

  
  

首先，让我们看看每个映射在堆中占用了多少空间。这很重要，因为它会影响运行应用程序所需的内存量。

这里有一个有趣的明显注释：在最后一个场景（1,000,000 个整数）中，嵌套映射的大小明显大于其他映射。这是因为，在这种情况下，嵌套映射会创建 1 个包含 100 万个条目的第一级映射。然后，对于第二级和第三级，它会创建 100 万张地图，其中只有一个条目。

所有这些嵌套映射都会存储额外的开销，并且大部分都是空的。这显然是一个边缘情况，但我想用它来说明这一点。当使用嵌套映射实现时，唯一性（以及该唯一性的顺序）非常重要。

如果将顺序颠倒为 1、1、100 万，您实际上会得到最低的存储要求。

在其他两种情况下，嵌套映射是最有效的，自定义键对象排在第二位，字符串键排在最后。

接下来，让我们看看从头开始创建每个地图所需的时间：

同样，我们看到嵌套映射在内存分配的 100 万-1-1 场景中表现最差，但即便如此，它在 CPU 时间方面也优于其他映射。在上面，我们还可以看到 String 键在所有情况下表现最差，而使用自定义键对象比嵌套键稍慢并且需要更多的内存分配。

最后我们看一下最高吞吐量场景以及读取效率如何。我们运行了 100 万次读取操作（每个创建的密钥 1 次）；我们没有包含任何不存在的密钥。

这是我们真正看到基于字符串的键查找有多慢的地方。它是迄今为止 3 个选项中最慢且分配最多内存的。自定义键对象的执行“接近”嵌套映射实现，但仍然稍微慢一些。

然而，在查找内存分配时，请注意嵌套映射的表现如何。不，这不是图表中的错误；而是错误。在嵌套映射中查找值不需要额外的内存分配来进行查找。这怎么可能？

那么，当将复合对象组合成字符串键时，每次都需要为新的字符串对象分配内存：

 private String lookup(int key1, String key2, long key3) { return map.get(key1 + "." + key2 + "." + key3); }

当使用复合键时，仍然需要为新的键对象分配内存。但是因为该对象的成员已经创建并引用，所以它分配的空间仍然比新字符串少得多：

 private String lookup(int key1, String key2, long key3) { return map.get(new MapKey(key1, key2, key3)); }

但嵌套映射实现不需要在查找时分配新的内存。您将重用给定的部分作为每个嵌套映射的键：

 private String lookup(int key1, String key2, long key3) { return map.get(key1).get(key2).get(key3); }

那么，基于上述，哪个性能最好？

很容易看出，嵌套地图几乎在所有情况下都名列前茅。如果您在大多数用例中寻求原始性能，那么它可能是最佳选择。不过，您应该执行自己的测试来确认您的用例。

当嵌套映射变得不切实际或无法用于您的实现时，关键对象是一个非常好的通用选项。复合字符串键虽然最容易实现，但几乎总是最慢的。

在寻求实现复合键时要考虑的最后一点是您可以将上述内容组合起来。例如，您可以在第一级或第二级使用嵌套映射，然后使用复合键对象来简化更深的级别。

这仍然可以保持数据分区以便快速查找，同时仍然优化存储和查找性能。并保持代码的可读性。

太长了；

大多数时候，只要保持简单即可。将复合键组合成字符串键，以便存储在映射或缓存中（如果这是最简单的选项并且性能不是主要问题）。

在性能至关重要的情况下，请确保进行自己的测试。但在大多数情况下，使用嵌套映射将是性能最高的。它还可能具有最小的存储要求。当嵌套映射变得不切实际时，复合键仍然是一种高性能的替代方案。

也发布在这里