我正在编写一个应用程序，其中内存和速度在较小程度上是至关重要的。我从分析中发现，我在 Map 和 Set 操作上花费了大量时间。虽然我正在研究减少调用这些方法的方法，但我想知道是否有人编写或遇到过显着改善访问时间或内存开销的实现？或者至少，考虑到一些假设，这可以改善这些事情？
通过查看 JDK 源代码，我无法相信它不能变得更快或更精简。
我知道 Commons Collections，但我不相信它有任何目标是更快或更精简的实现。谷歌收藏也是如此。
更新：应该注意到我不需要线程安全。
问问题
12641 次
17 回答
11
通常这些方法很快。您应该检查几件事：您的哈希码是否已实现？它们是否足够均匀？否则你会得到垃圾性能。
http://trove4j.sourceforge.net/ <-- 这有点快并且节省了一些内存。我在 50,000 次更新上节省了几毫秒
您确定您正确使用了地图/设置吗？即不尝试迭代所有值或类似的东西。另外，例如不要先包含然后再删除。只需检查删除。
还要检查您是否使用 Double vs double。我注意到数万次检查的几毫秒性能改进。
您是否还正确/适当地设置了初始容量？
于 2009-05-14T20:22:09.850 回答
6
以下是我知道的，除了 Google 和 Commons Collections：
当然，您始终可以实现自己的数据结构，这些数据结构针对您的用例进行了优化。为了能够提供更好的帮助，我们需要了解您的访问模式以及您在集合中存储的数据类型。
于 2009-05-14T20:52:21.073 回答
4
尝试提高 equals 和 hashCode 方法的性能，这有助于加快标准容器对对象的使用。
于 2009-05-14T20:10:10.520 回答
2
您可以扩展 AbstractMap 和/或 AbstractSet 作为起点。不久前我这样做是为了实现一个基于二叉树的映射（键是一个整数，树上的每个“级别”都是一个位位置。左孩子是 0，右孩子是 1）。这对我们来说效果很好，因为密钥是 EUI-64 标识符，而且对我们来说，大多数时候前 5 个字节是相同的。
要实现一个 AbstractMap，至少需要实现 entrySet() 方法，返回一组 Map.Entry，每个都是一个键/值对。
为了实现一个集合，你扩展 AbstractSet 并提供 size() 和 iterator() 的实现。
然而，至少是这样。您还需要实现 get 和 put，因为默认映射是不可修改的，并且 get 的默认实现会遍历 entrySet 以寻找匹配项。
于 2009-05-14T20:09:39.397 回答
2
您可以通过以下方式节省一点内存：
(a) 使用更强大、更广泛的哈希码，从而避免存储密钥；
(b) 通过从数组中分配自己，避免为每个哈希表条目创建单独的对象。
如果它有用，这里有一个简单的 Java 实现的Numerical Recipies哈希表，我有时发现它很有用。您可以直接键入 CharSequence（包括字符串），否则您必须自己为您的对象提供一个强大的 64 位散列函数。
请记住，此实现不存储 keys，因此如果两个项目具有相同的哈希码（如果您有一个良好的哈希函数，您会期望在 2^32 或几十亿个项目之后进行哈希处理），然后一项将覆盖另一项：
public class CompactMap<E> implements Serializable {
static final long serialVersionUID = 1L;
private static final int MAX_HASH_TABLE_SIZE = 1 << 24;
private static final int MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR = 1 << 20;
private static final long[] byteTable;
private static final long HSTART = 0xBB40E64DA205B064L;
private static final long HMULT = 7664345821815920749L;
static {
byteTable = new long[256];
long h = 0x544B2FBACAAF1684L;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 31; j++) {
h = (h >>> 7) ^ h;
h = (h << 11) ^ h;
h = (h >>> 10) ^ h;
}
byteTable[i] = h;
}
}
private int maxValues;
private int[] table;
private int[] nextPtrs;
private long[] hashValues;
private E[] elements;
private int nextHashValuePos;
private int hashMask;
private int size;
@SuppressWarnings("unchecked")
public CompactMap(int maxElements) {
int sz = 128;
int desiredTableSize = maxElements;
if (desiredTableSize < MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR) {
desiredTableSize = desiredTableSize * 4 / 3;
}
desiredTableSize = Math.min(desiredTableSize, MAX_HASH_TABLE_SIZE);
while (sz < desiredTableSize) {
sz <<= 1;
}
this.maxValues = maxElements;
this.table = new int[sz];
this.nextPtrs = new int[maxValues];
this.hashValues = new long[maxValues];
this.elements = (E[]) new Object[sz];
Arrays.fill(table, -1);
this.hashMask = sz-1;
}
public int size() {
return size;
}
public E put(CharSequence key, E val) {
return put(hash(key), val);
}
public E put(long hash, E val) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
int lastk;
do {
if (hashValues[k] == hash) {
E old = elements[k];
elements[k] = val;
return old;
}
lastk = k;
k = nextPtrs[k];
} while (k != -1);
k = nextHashValuePos++;
nextPtrs[lastk] = k;
} else {
k = nextHashValuePos++;
table[hc] = k;
}
if (k >= maxValues) {
throw new IllegalStateException("Hash table full (size " + size + ", k " + k);
}
hashValues[k] = hash;
nextPtrs[k] = -1;
elements[k] = val;
size++;
return null;
}
public E get(long hash) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
do {
if (hashValues[k] == hash) {
return elements[k];
}
k = nextPtrs[k];
} while (k != -1);
}
return null;
}
public E get(CharSequence hash) {
return get(hash(hash));
}
public static long hash(CharSequence cs) {
if (cs == null) return 1L;
long h = HSTART;
final long hmult = HMULT;
final long[] ht = byteTable;
for (int i = cs.length()-1; i >= 0; i--) {
char ch = cs.charAt(i);
h = (h * hmult) ^ ht[ch & 0xff];
h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
}
return h;
}
}
于 2009-05-15T02:36:42.617 回答
1
查看 GNU Trove：
于 2009-05-14T20:10:58.770 回答
1
在 commons-collections 中至少有一个专门为速度而构建的实现：Flat3Map它非常具体，只要元素不超过 3 个，它就会非常快。
我怀疑通过遵循@thaggie 的建议添加查看equals/hashcode 方法时间，您可能会获得更多里程。
于 2009-05-14T20:19:08.937 回答
1
你说你分析了一些课程，但你有没有做任何时间来检查他们的速度？我不确定您将如何检查他们的内存使用情况。当您比较不同的实现时，手头有一些具体的数字似乎会很好。
于 2009-05-14T20:40:05.690 回答
1
这里有一些注释和几个替代数据结构库的链接：http: //www.leepoint.net/notes-java/data/collections/ds-alternatives.html
我也会对 fastutil 投出强烈的一票。（在另一个响应中和该页面上提到）它具有比您无法动摇的更多不同的数据结构，并且针对原始类型作为键或值进行了优化的版本。（一个缺点是 jar 文件很大，但您大概可以将其修剪为您需要的内容）
于 2009-05-14T21:47:09.287 回答
1
几年前我经历过类似的事情——非常大的地图和集合以及其中的很多。默认的 Java 实现占用了太多空间。最后我推出了自己的，但只有在我检查了我的代码所需的实际使用模式之后。例如，我有一组已知的大型对象，这些对象是在早期创建的，有些地图是稀疏的，而另一些是密集的。其他结构单调增长（没有删除），而在其他地方，使用“集合”并执行偶尔但无害的处理重复项目的额外工作比花费时间和空间避免重复更快。我使用的许多实现都是数组支持的，并利用了我的哈希码是按顺序分配的这一事实，因此对于密集映射，查找只是一个数组访问。
带走消息：
- 看看你的算法，
- 考虑多种实现，以及
- 请记住，那里的大多数库都适合通用用途（例如插入和删除、一系列大小、既不稀疏也不密集等），因此它们将产生您可能避免的开销。
哦，写单元测试...
于 2009-05-25T15:12:35.743 回答
1
有时，当我看到 Map 和 Set 操作使用高比例的 CPU 时，这表明我过度使用了 Map 和 Set，并且重组我的数据几乎消除了前 10% 的 CPU 消耗者的集合。
看看你是否可以避免集合的副本、迭代集合和任何其他导致访问集合的大部分元素和创建对象的操作。
于 2009-05-25T15:26:01.083 回答
0
这可能不是导致问题的原因，而是它们背后的对象Map。Set根据您的问题，您可能需要更多数据库类型的方案，其中“对象”存储为一堆字节而不是 Java 对象。您可以嵌入一个数据库（例如 Apache Derby）或做您自己的专业工作。这非常取决于您实际在做什么。HashMap不是故意大而慢...
于 2009-05-14T20:08:44.627 回答
0
Commons Collections 有FastArrayList、FastHashMap和FastTreeMap但我不知道它们的价值...
于 2009-05-14T20:17:22.123 回答
0
- Commons Collections 有一个 id 映射，它通过 == 进行比较，应该更快。-
[Joda Primities][1]与原始收藏一样，Trove 也是如此。我用 Trove 做了实验，发现它的内存使用更好。 - 我正在用一些整数映射许多小对象的集合。将这些更改为整数节省了近一半的内存（尽管需要一些更混乱的应用程序代码来补偿）。
- 在我看来，排序树应该比哈希图消耗更少的内存，因为它们不需要负载因子（尽管如果有人可以确认或有理由说明这实际上是愚蠢的，请在评论中发布）。
于 2009-05-14T20:28:48.727 回答
0
您使用的是哪个版本的 JVM？
如果您不在 6 上（尽管我怀疑您是），那么切换到 6 可能会有所帮助。
如果这是一个服务器应用程序并且在 Windows 上运行，请尝试使用 -server 来使用正确的热点实现。
于 2009-05-15T13:06:22.637 回答
0
我使用下面的包（koloboke）来做一个 int-int hashmap，因为它支持 promitive 类型并将两个 int 存储在一个 long 变量中，这对我来说很酷。科洛博克
于 2016-08-08T12:07:08.693 回答