The fastest way to check if a value in an array is many times

Question

I have an array of several values ​​between -15and 31, and I have to check if any xis in this array for ~300 000 000times. Since there are negative values, I cannot create a boolean array. Now I create HashSetfrom the source array and use the method .contains(), but it is too slow. Is there a faster way or trick?

Update I create this array from another (so that I can use any structure I want)

Answer 1

You can easily create an array booleanand just shift the index:

// 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) {
    ...
}