检查值是否在数组中的最快方法

Question

我-15和31/ 之间有一些值的数组,我必须检查,如果有一些x在这个数组中的~300 000 000次数.因为有负值,我无法创建布尔数组.现在我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) {
    ...
}