java - 多次检查值是否在数组中的最快方法

Question

我有一个介于 -15 和 31 之间的一些值的数组，我必须检查这个数组中是否有一些 x ~300 000 000 次。因为有负值，所以我无法创建 boolean 数组。现在我正在从原始数组创建 HashSet 并使用 .contains() 方法，但这太慢了。有没有更快的方法或技巧？

更新 我从另一个数组创建这个数组(所以我可以使用我想要的任何结构)

Answer 1

您可以轻松地创建一个boolean 数组并仅偏移索引:

// Do this once...
int minValueInclusive = -15;
int maxValueExclusive = 31;
boolean[] presence = new boolean[maxValueExclusive - minValueInclusive + 1];
for (int value : array) {
    presence[value - minValueInclusive] = true;
}

然后检查是否存在:

if (presence[index - minValueInclusive]) {
    ...
}

或者，当您使用少于 64 位时，您可以将整个内容存储在单个 long 中，并使用位移位。

// Do this once...
int minValueInclusive = -15;
long presence = 0;
for (int value : array) {
    presence |= 1L << (value - minValueInclusive);
}

然后检查是否存在:

if ((presence & (1L << (index - minValueInclusive))) != 0) {
    ...
}