原始值的地图替代

Question

我对我的应用程序进行了一些分析,其中一个结果发现堆上大约18%的内存被类型的对象使用Double.事实证明这些对象是Maps 中的值,我不能使用原始类型.

我的理由是原始类型double消耗的内存少于它的对象Double.有没有办法有一个像数据结构的地图,可以接受任何类型的键和基元double作为值？

主要业务是:

• 插入(可能只有一次)
• 查找(按键包含)
• 检索(按键)
• 迭代

我拥有的典型地图是:

• HashMap<T, HashMap<NodeData<T>, Double>> graph
• HashMap<Point2D, Boolean> onSea (虽然不是双倍价值)
• ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>

全部用于Java 8.

附录

我主要对那些有这些类型的地图解决方案的框架不感兴趣,但对解决这些问题时需要考虑的内容感兴趣.如果您愿意,任何此类框架背后的概念/想法/方法是什么.或者解决方案也可能在另一个层面,其中地图被替换为像@Ilmari Karonen在他的答案中指出的特定模式的对象.

Answer 1

Eclipse Collections具有对象和原始映射,并且两者都具有Mutable和Immutable版本.

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);

通过调用,MutableMap可以将A 用作ImmutableMapEclipse集合中的工厂,toImmutable就像我在上面的示例中所做的那样.两个可变和不可变的映射共享共同父接口,其中在的情况下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);

几年前发布了大型地图的性能比较.

大型HashMap概述:JDK,FastUtil,Goldman Sachs,HPPC,Koloboke,Trove - 2015年1月版

此后,GS Collections已迁移到Eclipse Foundation,现在是Eclipse Collections.

注意:我是Eclipse Collections的提交者.

Answer 2

您正在寻找的是Object2DoubleOpenHashMap来自fastutil(具有较小内存占用和快速访问和插入的集合框架),它提供了类型double getDouble(Object k)和方法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");

该类Object2DoubleOpenHashMap是一个Map非线程安全的实际实现,但是Object2DoubleMaps.synchronize(Object2DoubleMap<K> m)由于装饰器,您仍然可以使用实用程序方法使其成为线程安全的.

创建代码将是:

// Create a thread safe Object2DoubleMap
Object2DoubleMap<String> map =  Object2DoubleMaps.synchronize(
    new Object2DoubleOpenHashMap<>()
);

Answer 3

其他人已经提出了几个原始值映射的第三方实现.为了完整起见,我想提一些完全摆脱你可能想要考虑的地图的方法.这些解决方案并不总是可行的,但是当它们存在时,它们通常比任何地图都更快,更节省内存.

备选方案1:使用普通旧阵列.

一个简单的double[]阵列可能不像花哨的地图那么性感,但很少能在紧凑性和访问速度上击败它.

当然,数组有一些限制:它们的大小是固定的(尽管你总是可以创建一个新的数组并将旧的数据复制到其中),它们的键只能是小正整数,为了提高效率,应该合理密集(即使用的密钥总数应该是最高密钥值的一个相当大的部分).但是,如果您的密钥恰好是这种情况,或者如果您可以安排它,那么原始值数组可以非常高效.

特别是,如果可以为每个键对象分配唯一的小整数ID,则可以将该ID用作数组的索引.类似地,如果您已经将对象存储在数组中(例如,作为一些更复杂的数据结构的一部分)并通过索引查找它们,那么您可以简单地使用相同的索引来查找另一个数组中的任何其他元数据值.

如果你实现了某种冲突处理机制,你甚至可以免除ID唯一性要求,但是那时你正在实现自己的哈希表.在某些情况下,实际上可能有意义,但通常在这一点上,使用现有的第三方实现可能更容易.

备选方案2:自定义对象.

不是将关键对象的映射维护为原始值,为什么不将这些值设置为对象本身的属性？毕竟,这是面向对象编程的全部内容 - 将相关数据分组为有意义的对象.

例如,HashMap<Point2D, Boolean> onSea为什么不给你的点一个布尔onSea属性,而不是维持一个？当然,您需要为此定义自己的自定义点类,但是Point2D如果您愿意,没有理由不能扩展标准类,这样您就可以将自定义点传递给任何期望的方法.Point2D.

同样,这种方法可能并不总是直接起作用,例如,如果您需要使用无法修改的类(但请参阅下文),或者您要存储的值与多个对象(如您的ConcurrentHashMap<Point2D, HashMap<Point2D, Double>>)相关联.

但是,对于后一种情况,您仍可以通过适当地重新设计数据表示来解决问题.例如,Map<Node, Map<Node, Double>>您可以定义一个Edge类,而不是将加权图表示为a :

class Edge {
    Node a, b;
    double weight;
}

然后向每个包含连接到该节点的边的节点添加Edge[](或Vector<Edge>)属性.

备选方案3:将多个地图合并为一个.

如果您有多个具有相同键的映射,并且不能像上面建议的那样将值转换为键对象的新属性,请考虑将它们分组到单个元数据类中,并从键创建单个映射到该类的对象.例如,考虑定义单个元数据类而不是a Map<Item, Double> accessFrequency和a Map<Item, Long> creationTime:

class ItemMetadata {
    double accessFrequency;
    long creationTime;
}

并且只有一个Map<Item, ItemMetadata>存储所有元数据值.这比具有多个映射更具内存效率,并且还可以通过避免冗余映射查找来节省时间.

在某些情况下,为方便起见,您可能还希望在每个元数据对象中包含对其对应主对象的引用,以便您可以通过对元数据对象的单个引用来访问它们.这自然会变成...

备选方案4:使用装饰器.

作为前两个备选方案的组合,如果您无法直接向关键对象添加额外的元数据属性,请考虑使用可以保存额外值的装饰器来包装它们.因此,例如,您可以简单地执行以下操作,而不是直接创建具有额外属性的自己的点类.

class PointWrapper {
    Point2D point;
    boolean onSea;
    // ...
}

如果你愿意,你甚至可以通过实现方法转发将这个包装器变成一个完整的装饰器,但即使只是一个简单的"哑"包装器也可能用于许多目的.

如果您可以安排存储和使用包装器,那么这种方法最有用,这样您就不需要查找与未包装对象相对应的包装器.当然,如果你确实需要偶尔这样做(例如因为你只是从其他代码接收未解包的对象),那么你可以用一个单独做Map<Point2D, PointWrapper>,但是你有效地回到了之前的选择.