针对少量条目且无删除操作的优化Java Map/Dictionary

11 浏览
0 Comments

针对少量条目且无删除操作的优化Java Map/Dictionary

我有一种对于HashMap的特定用法，它只存储少量的条目（通常少于5-10个），这些条目是以String键为基础的。我只需添加条目、通过键获取它们，有时迭代条目集。在映射的生命周期中，条目永远不会被删除。我有一些操作需要5-6个这样的较小的映射，并且在单个用户使用（即请求）期间每次都要分配。

我目前使用HashMap。然而，我想知道是否有更好、更优化的Map类似结构的实现可以用于这个场景？比如，一个能够分配更少空间并且在元素较少时可能更快的实现。或者HashMap已经足够好了吗？

请注意，我并不坚持要遵循Map接口。

我的想法是朝着由数组支持的映射的方向发展，就像JetBrains的这个实现引起了我的注意：SmartFMap（一个针对存储少量条目并且更新相对较少的不可变映射，正如他们所说）。

有人知道类似的替代实现可以作为HashMap的替代品吗？

补充

我最初的想法是@Evgeniy Dorofeev在他的答案中提到的，使用排序后的条目数组并使用二分搜索，但有以下修改。由于我需要向集合中添加元素并且防止数组的重新创建，我考虑使用带有一些空间的数组。第一个元素添加在数组中间，第二个元素添加在剩余一半的中间（上方或下方，取决于排序顺序）。如果这样的数组的初始大小足够好，我们可以（大多数情况下）避免重新创建该数组，同时仍然能够进行二进制/基数搜索。

0

3 答案

0 Comments

优化Java中用于少量条目的Map/Dictionary，不需要删除操作

问题的出现原因:

原因是需要一个能够存储少量条目的Map/Dictionary，但不需要进行删除操作。传统的HashMap或者TreeMap可能会有一些不必要的开销，因为它们为处理大量数据而设计，而不是针对小规模数据。

解决方法:

1. 可以基于数组创建一个自定义的Map。首先创建一个二维数组，用于存储键值对。然后将键值对依次存储在数组中。

      Object[][] map = new Object[3][];
      map[0] = new Object[] {k1, v1};
      map[1] = new Object[] {k2, v2};
      map[2] = new Object[] {k3, v3};
      Arrays.sort(map);

2. 使用二分查找算法进行搜索。通过对数组进行排序，可以使用二分查找算法快速定位到指定的键，并获取对应的值。

      int i = Arrays.binarySearch(map, key);
      Object value = map[i];

3. 可以添加一个自定义的功能，用于向数组中插入新的键值对。这样就可以实现类似于HashMap中的put操作，动态地向数组中添加新的键值对。同时，可以通过一些技巧避免数组的重新分配，提高性能。

这种优化方案可能不会比传统的HashMap或者TreeMap更快，但它可以节省内存空间。此外，通过使用数组而不是哈希表或者树结构，可以减少一些不必要的开销，适用于处理少量数据的场景。

相关问题:

这个问题与Stack Overflow上的这个问题有关。换句话说，使用这种方式进行查找是否比哈希查找更快。

作者认为这种解决方案可能不会更快，唯一的优势在于它会占用更少的内存空间。

0
0 Comments

问题出现的原因是需要一个适用于少量条目且不需要删除操作的优化的Java Map/Dictionary。解决方法是使用Guava的ImmutableMap或者JDK的EnumMap。

Guava的ImmutableMap可以通过以下方式创建：

Map map = ImmutableMap.of("key1", "value1", "key2", "value2");

JDK的EnumMap可以在需要修改map的条目时使用，它比HashMap稍微快一点。

然而，ImmutableMap并不适用于需要插入元素的情况，而EnumMap也不适用于非枚举类型的键。经过检查，发现Guava的ImmutableMap在查找时会使用普通的线性查找方法。因此，如果可以创建一个不可变的map，那么Guava的ImmutableMap可能足够好用。

0
0 Comments

优化java Map/Dictionary用于小数量条目且不需要移除条目的问题出现的原因是，使用HashMap计算哈希值需要使用所有字符，而对于某些字符串，只需比较前几个字符即可获取相关值。为了解决这个问题，可以考虑使用Trie数据结构，它可以提供与HashMap几乎相同的复杂度来获取条目，但在某些情况下会更快。

Trie数据结构是一种用于存储字符串的树状结构，每个节点表示字符串的一个字符，通过不断遍历节点来获取字符串的值。对于给定的字符串集合，如"hello, world, house, foo, bar, balloon"，使用Trie结构可以只比较前几个字符来获取相关值。例如，对于字符串"hello"，只需要比较前两个字符；对于字符串"world"，只需要比较一个字符；对于字符串"bar"和"balloon"，需要比较前三个字符。相比之下，使用HashMap需要计算所有字符的哈希值。

然而，根据参考链接中的内容显示，Trie数据结构不能超越Java集合的性能。

虽然Trie数据结构在某些情况下可以提供更快的访问速度，但在Java中，它无法超越使用HashMap的性能。因此，在解决这个问题时，需要权衡使用Trie数据结构和使用HashMap的优劣。

0