映射原始值的替代方案
Map alternative for primitive values
我对我的应用程序做了一些分析，结果之一是堆上大约 18% 的内存被 Double 类型的对象使用。原来这些对象是 Maps 中的值，我不能在其中使用原始类型。
我的理由是 double 的原始类型比它的对象 Double 消耗更少的内存。有没有一种方法可以让数据结构像地图一样接受任何类型作为键和原始 double 作为值？
主要操作是：
- 插入（可能只有一次）
- 查找（按键包含）
- 检索（按键）
- 迭代
我拥有的典型地图是：
HashMap<T, HashMap<NodeData<T>, Double>> graphHashMap<Point2D, Boolean> onSea（虽然不是双精度值）ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>
全部用于Java 8.
附录
我主要对能够解决这些类型映射的框架不感兴趣，但对解决这些问题时必须考虑的内容感兴趣。如果需要，任何此类框架背后的 concepts/ideas/approaches 是什么。或者解决方案也可能在另一个层面上，其中地图被替换为遵循某种模式的对象，就像@Ilmari Karonen 在他的回答中指出的那样。
您要找的是Object2DoubleOpenHashMap from fastutil (Collections Framework with a small memory footprint and fast access and insertion) which provides methods of type double getDouble(Object k) and double put(K k, double v)。
例如：
// Create a Object2DoubleOpenHashMap instance
Object2DoubleMap<String> map = new Object2DoubleOpenHashMap<>();
// Put a new entry
map.put("foo", 12.50d);
// Access to the entry
double value = map.getDouble("foo");
class Object2DoubleOpenHashMap 是 Map 的真正实现，它不是 thread-safe，但是您仍然可以使用实用方法 Object2DoubleMaps.synchronize(Object2DoubleMap<K> m) 来多亏了装饰师thread-safe。
创建代码将是：
// Create a thread safe Object2DoubleMap
Object2DoubleMap<String> map = Object2DoubleMaps.synchronize(
new Object2DoubleOpenHashMap<>()
);
有几种实现方式：
以下是与最佳表现相关的问题：
- Most efficient Java primitive collections library
- What is a fast alternative to HashMap for mapping to primitive types?
实际实施也会影响性能
- Difference between HashMap, LinkedHashMap and TreeMap
Eclipse Collections has object and primitive maps 并且两者都有可变和不可变版本。
MutableObjectDoubleMap<String> doubleMap = ObjectDoubleMaps.mutable.empty();
doubleMap.put("1", 1.0d);
doubleMap.put("2", 2.0d);
MutableObjectBooleanMap<String> booleanMap = ObjectBooleanMaps.mutable.empty();
booleanMap.put("ok", true);
ImmutableObjectDoubleMap<String> immutableMap = doubleMap.toImmutable();
Assert.assertEquals(doubleMap, immutableMap);
A MutableMap 可以通过调用 toImmutable 在 Eclipse Collections 中用作 ImmutableMap 的工厂，就像我在上面的示例中所做的那样。可变映射和不可变映射共享一个公共父接口，在上面的 MutableObjectDoubleMap 和 ImmutableObjectDoubleMap 的情况下，它被命名为 ObjectDoubleMap.
Eclipse Collections 还为库中的所有可变容器提供了同步和不可修改的版本。以下代码将为您提供围绕原始地图的同步视图。
MutableObjectDoubleMap<String> doubleMap =
ObjectDoubleMaps.mutable.<String>empty().asSynchronized();
doubleMap.put("1", 1.0d);
doubleMap.put("2", 2.0d);
MutableObjectBooleanMap<String> booleanMap =
ObjectBooleanMaps.mutable.<String>empty().asSynchronized();
booleanMap.put("ok", true);
这种大型地图的性能比较发表于几年前。
Large HashMap overview: JDK, FastUtil, Goldman Sachs, HPPC, Koloboke, Trove – January 2015 version
GS Collections 已经迁移到 Eclipse Foundation，现在是 Eclipse Collections。
注意：我是 Eclipse Collections 的提交者。
其他人已经提出了 third-party 几个 primitive-valued 地图的实现。为了完整起见，我想提一些您可能想要考虑的完全摆脱地图的方法。这些解决方案并不总是可行，但如果可行，它们通常比任何地图都更快、更 memory-efficient。
备选方案 1：使用普通的旧数组。
一个简单的 double[] 数组可能不如精美的地图那么吸引人，但在紧凑性和访问速度方面几乎没有什么能比得上它。
当然，数组有很多限制：它们的大小是固定的（尽管你总是可以创建一个新数组并将旧数组的内容复制到其中）并且它们的键只能是小的正整数，对于效率，应该相当密集（即使用的密钥总数应该是最高密钥值的相当大的一部分）。但是，如果您的键恰好是这种情况，或者如果您可以安排这种情况，原始值数组会非常有效。
特别是，如果您可以为每个键对象分配一个唯一的小整数 ID，则可以将该 ID 用作数组的索引。类似地，如果您已经将对象存储在一个数组中（例如，作为一些更复杂的数据结构的一部分）并通过索引查找它们，那么您可以简单地使用相同的索引来查找另一个数组中的任何其他元数据值。
如果您实现了某种冲突处理机制，您甚至可以免除 ID 唯一性要求，但到那时您就可以很好地实现自己的哈希 table。在某些情况下 可能 实际上有意义，但通常在那个时候使用现有的 third-party 实现可能更容易。
备选方案 2：自定义您的对象。
为什么不维护从关键对象到原始值的映射，为什么不直接将这些值变成对象本身的属性呢？毕竟，这就是 object-oriented 编程的全部内容 — 将相关数据分组到有意义的对象中。
例如，与其维护一个 HashMap<Point2D, Boolean> onSea，为什么不直接给你的积分一个布尔值 onSea 属性？当然，你需要为此定义你自己的自定义点class，但如果你愿意，你没有理由不能让它扩展标准Point2D class，所以您可以将自定义点传递给任何需要 Point2D.
的方法
同样，这种方法可能并不总是直接有效，例如如果您需要使用无法修改的 classes（见下文），或者如果您要存储的值与多个对象相关联（如在您的 ConcurrentHashMap<Point2D, HashMap<Point2D, Double>> 中）。
但是，对于后一种情况，您仍然可以通过适当地重新设计数据表示来解决问题。例如，您可以定义一个 Edge class，而不是将加权图表示为 Map<Node, Map<Node, Double>>：
class Edge {
Node a, b;
double weight;
}
然后向包含连接到该节点的任何边的每个节点添加 Edge[]（或 Vector<Edge>）属性。
方案三：将多张地图合二为一。
如果您有多个具有相同键的地图，并且不能像上面建议的那样将值转换为键对象的新属性，请考虑将它们分组到一个元数据中 class 并从中创建一个地图class 对象的键。例如，考虑定义单个元数据 class，而不是 Map<Item, Double> accessFrequency 和 Map<Item, Long> creationTime，例如：
class ItemMetadata {
double accessFrequency;
long creationTime;
}
并且有一个 Map<Item, ItemMetadata> 来存储所有元数据值。这比拥有多个地图更 memory-efficient，并且还可以通过避免冗余地图查找来节省时间。
在某些情况下，为方便起见，您可能还希望在每个元数据对象中包含对其相应主对象的引用，以便您可以通过对元数据对象的单个引用来访问这两个对象。这自然会进入...
备选方案 4：使用装饰器。
作为前两个备选方案的组合，如果您不能直接将额外的元数据属性添加到键对象中，请考虑使用可以容纳额外值的 decorators 将它们包装起来。因此，例如，与其直接创建具有额外属性的点 class，不如简单地执行以下操作：
class PointWrapper {
Point2D point;
boolean onSea;
// ...
}
如果你愿意，你甚至可以通过实现方法转发将这个包装器变成一个 full-blown 装饰器，但即使只是一个简单的 "dumb" 包装器也可能足以满足许多目的。
如果您随后可以安排仅存储和使用包装器，则此方法最有用，这样您就无需查找与未包装对象对应的包装器。当然，如果你确实需要偶尔这样做（例如，因为你只从其他代码接收解包的对象），那么你可以用一个 Map<Point2D, PointWrapper>以前的选择。
为了更好地估计这些不同的库如何相互叠加，我整理了一个小的基准测试来检查以下库的性能：
- 300'000 次插入的总时间
- 检查地图中包含 1000 个样本的平均时间
- 数据结构的内存大小
我查看了类似
Map 的结构，它以 String 为键，以 double 为值。检查的框架是 Eclipse Collection, HPPC, Trove and FastUtil，以及用于比较的 HashMap 和 ConcurrentHashMap.
简而言之，这些是结果：
Filling in 300000 into the JDK HashMap took 107ms
Filling in 300000 into the JDK ConcurrentHashMap took 152ms
Filling in 300000 into the Eclipse map took 107ms
Filling in 300000 into the Trove map took 855ms
Filling in 300000 into the HPPC map took 93ms
Filling in 300000 into the FastUtil map took 163ms
1000 lookups average in JDK HashMap took: 550ns
1000 lookups average in JDK Concurrent HashMap took: 748ns
1000 lookups average in Eclipse Map took: 894ns
1000 lookups average in Trove Map took: 1033ns
1000 lookups average in HPPC Map took: 523ns
1000 lookups average in FastUtil Map took: 680ns
JDK HashMap: 43'809'895B
JDK Concurrent HashMap: 43'653'740B => save 0.36%
Eclipse Map: 35'755'084B => save 18.39%
Trove Map: 32'147'798B => save 26.62%
HPPC Map: 27'366'533B => save 37.53%
FastUtil Map: 31'560'889B => save 27.96%
有关所有详细信息以及测试应用程序，请查看我的 blog entry。
我对我的应用程序做了一些分析，结果之一是堆上大约 18% 的内存被 Double 类型的对象使用。原来这些对象是 Maps 中的值，我不能在其中使用原始类型。
我的理由是 double 的原始类型比它的对象 Double 消耗更少的内存。有没有一种方法可以让数据结构像地图一样接受任何类型作为键和原始 double 作为值？
主要操作是：
- 插入（可能只有一次）
- 查找（按键包含）
- 检索（按键）
- 迭代
我拥有的典型地图是：
HashMap<T, HashMap<NodeData<T>, Double>> graphHashMap<Point2D, Boolean> onSea（虽然不是双精度值）ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>
全部用于Java 8.
附录
我主要对能够解决这些类型映射的框架不感兴趣，但对解决这些问题时必须考虑的内容感兴趣。如果需要，任何此类框架背后的 concepts/ideas/approaches 是什么。或者解决方案也可能在另一个层面上，其中地图被替换为遵循某种模式的对象，就像@Ilmari Karonen 在他的回答中指出的那样。
您要找的是Object2DoubleOpenHashMap from fastutil (Collections Framework with a small memory footprint and fast access and insertion) which provides methods of type double getDouble(Object k) and double put(K k, double v)。
例如：
// Create a Object2DoubleOpenHashMap instance
Object2DoubleMap<String> map = new Object2DoubleOpenHashMap<>();
// Put a new entry
map.put("foo", 12.50d);
// Access to the entry
double value = map.getDouble("foo");
class Object2DoubleOpenHashMap 是 Map 的真正实现，它不是 thread-safe，但是您仍然可以使用实用方法 Object2DoubleMaps.synchronize(Object2DoubleMap<K> m) 来多亏了装饰师thread-safe。
创建代码将是：
// Create a thread safe Object2DoubleMap
Object2DoubleMap<String> map = Object2DoubleMaps.synchronize(
new Object2DoubleOpenHashMap<>()
);
有几种实现方式：
以下是与最佳表现相关的问题：
- Most efficient Java primitive collections library
- What is a fast alternative to HashMap for mapping to primitive types?
实际实施也会影响性能
- Difference between HashMap, LinkedHashMap and TreeMap
Eclipse Collections has object and primitive maps 并且两者都有可变和不可变版本。
MutableObjectDoubleMap<String> doubleMap = ObjectDoubleMaps.mutable.empty();
doubleMap.put("1", 1.0d);
doubleMap.put("2", 2.0d);
MutableObjectBooleanMap<String> booleanMap = ObjectBooleanMaps.mutable.empty();
booleanMap.put("ok", true);
ImmutableObjectDoubleMap<String> immutableMap = doubleMap.toImmutable();
Assert.assertEquals(doubleMap, immutableMap);
A MutableMap 可以通过调用 toImmutable 在 Eclipse Collections 中用作 ImmutableMap 的工厂，就像我在上面的示例中所做的那样。可变映射和不可变映射共享一个公共父接口，在上面的 MutableObjectDoubleMap 和 ImmutableObjectDoubleMap 的情况下，它被命名为 ObjectDoubleMap.
Eclipse Collections 还为库中的所有可变容器提供了同步和不可修改的版本。以下代码将为您提供围绕原始地图的同步视图。
MutableObjectDoubleMap<String> doubleMap =
ObjectDoubleMaps.mutable.<String>empty().asSynchronized();
doubleMap.put("1", 1.0d);
doubleMap.put("2", 2.0d);
MutableObjectBooleanMap<String> booleanMap =
ObjectBooleanMaps.mutable.<String>empty().asSynchronized();
booleanMap.put("ok", true);
这种大型地图的性能比较发表于几年前。
Large HashMap overview: JDK, FastUtil, Goldman Sachs, HPPC, Koloboke, Trove – January 2015 version
GS Collections 已经迁移到 Eclipse Foundation，现在是 Eclipse Collections。
注意：我是 Eclipse Collections 的提交者。
其他人已经提出了 third-party 几个 primitive-valued 地图的实现。为了完整起见，我想提一些您可能想要考虑的完全摆脱地图的方法。这些解决方案并不总是可行，但如果可行，它们通常比任何地图都更快、更 memory-efficient。
备选方案 1：使用普通的旧数组。
一个简单的 double[] 数组可能不如精美的地图那么吸引人，但在紧凑性和访问速度方面几乎没有什么能比得上它。
当然，数组有很多限制：它们的大小是固定的（尽管你总是可以创建一个新数组并将旧数组的内容复制到其中）并且它们的键只能是小的正整数，对于效率，应该相当密集（即使用的密钥总数应该是最高密钥值的相当大的一部分）。但是，如果您的键恰好是这种情况，或者如果您可以安排这种情况，原始值数组会非常有效。
特别是，如果您可以为每个键对象分配一个唯一的小整数 ID，则可以将该 ID 用作数组的索引。类似地，如果您已经将对象存储在一个数组中（例如，作为一些更复杂的数据结构的一部分）并通过索引查找它们，那么您可以简单地使用相同的索引来查找另一个数组中的任何其他元数据值。
如果您实现了某种冲突处理机制，您甚至可以免除 ID 唯一性要求，但到那时您就可以很好地实现自己的哈希 table。在某些情况下 可能 实际上有意义，但通常在那个时候使用现有的 third-party 实现可能更容易。
备选方案 2：自定义您的对象。
为什么不维护从关键对象到原始值的映射，为什么不直接将这些值变成对象本身的属性呢？毕竟，这就是 object-oriented 编程的全部内容 — 将相关数据分组到有意义的对象中。
例如，与其维护一个 HashMap<Point2D, Boolean> onSea，为什么不直接给你的积分一个布尔值 onSea 属性？当然，你需要为此定义你自己的自定义点class，但如果你愿意，你没有理由不能让它扩展标准Point2D class，所以您可以将自定义点传递给任何需要 Point2D.
同样，这种方法可能并不总是直接有效，例如如果您需要使用无法修改的 classes（见下文），或者如果您要存储的值与多个对象相关联（如在您的 ConcurrentHashMap<Point2D, HashMap<Point2D, Double>> 中）。
但是，对于后一种情况，您仍然可以通过适当地重新设计数据表示来解决问题。例如，您可以定义一个 Edge class，而不是将加权图表示为 Map<Node, Map<Node, Double>>：
class Edge {
Node a, b;
double weight;
}
然后向包含连接到该节点的任何边的每个节点添加 Edge[]（或 Vector<Edge>）属性。
方案三：将多张地图合二为一。
如果您有多个具有相同键的地图，并且不能像上面建议的那样将值转换为键对象的新属性，请考虑将它们分组到一个元数据中 class 并从中创建一个地图class 对象的键。例如，考虑定义单个元数据 class，而不是 Map<Item, Double> accessFrequency 和 Map<Item, Long> creationTime，例如：
class ItemMetadata {
double accessFrequency;
long creationTime;
}
并且有一个 Map<Item, ItemMetadata> 来存储所有元数据值。这比拥有多个地图更 memory-efficient，并且还可以通过避免冗余地图查找来节省时间。
在某些情况下，为方便起见，您可能还希望在每个元数据对象中包含对其相应主对象的引用，以便您可以通过对元数据对象的单个引用来访问这两个对象。这自然会进入...
备选方案 4：使用装饰器。
作为前两个备选方案的组合，如果您不能直接将额外的元数据属性添加到键对象中，请考虑使用可以容纳额外值的 decorators 将它们包装起来。因此，例如，与其直接创建具有额外属性的点 class，不如简单地执行以下操作：
class PointWrapper {
Point2D point;
boolean onSea;
// ...
}
如果你愿意，你甚至可以通过实现方法转发将这个包装器变成一个 full-blown 装饰器，但即使只是一个简单的 "dumb" 包装器也可能足以满足许多目的。
如果您随后可以安排仅存储和使用包装器，则此方法最有用，这样您就无需查找与未包装对象对应的包装器。当然，如果你确实需要偶尔这样做（例如，因为你只从其他代码接收解包的对象），那么你可以用一个 Map<Point2D, PointWrapper>以前的选择。
为了更好地估计这些不同的库如何相互叠加，我整理了一个小的基准测试来检查以下库的性能：
- 300'000 次插入的总时间
- 检查地图中包含 1000 个样本的平均时间
- 数据结构的内存大小
我查看了类似
Map的结构，它以String为键，以double为值。检查的框架是 Eclipse Collection, HPPC, Trove and FastUtil，以及用于比较的HashMap和ConcurrentHashMap.
简而言之，这些是结果：
Filling in 300000 into the JDK HashMap took 107ms
Filling in 300000 into the JDK ConcurrentHashMap took 152ms
Filling in 300000 into the Eclipse map took 107ms
Filling in 300000 into the Trove map took 855ms
Filling in 300000 into the HPPC map took 93ms
Filling in 300000 into the FastUtil map took 163ms
1000 lookups average in JDK HashMap took: 550ns
1000 lookups average in JDK Concurrent HashMap took: 748ns
1000 lookups average in Eclipse Map took: 894ns
1000 lookups average in Trove Map took: 1033ns
1000 lookups average in HPPC Map took: 523ns
1000 lookups average in FastUtil Map took: 680ns
JDK HashMap: 43'809'895B
JDK Concurrent HashMap: 43'653'740B => save 0.36%
Eclipse Map: 35'755'084B => save 18.39%
Trove Map: 32'147'798B => save 26.62%
HPPC Map: 27'366'533B => save 37.53%
FastUtil Map: 31'560'889B => save 27.96%
有关所有详细信息以及测试应用程序，请查看我的 blog entry。