Как сделать мою хэш-функцию линейного зонда более эффективной?

Question

Я изо всех сил пытаюсь выяснить, верна ли моя линейная техника зондирования и эффективна ли она вообще.Могу ли я сделать его более эффективным?

static void enterValues(int values[], int hashTable[])
{
    for(int i = 0; i < values.length; i++){
        int k = hashFunction(values[i]);
        if(hashTable[k]== 0)
        hashTable[k] = values[i];
        else{
            boolean b = false;
            int counter = k%hashTable.length+1;
            if(counter >= hashTable.length)
                counter = 0;
                while (!b) {
                    if (hashTable[counter] == 0) {
                        hashTable[counter] = values[i];
                        b = true;
                    } else {
                        counter = counter % hashTable.length+1;
                    }
                }
            }
        }
    }

static int hashFunction(int value)
{
    return value % 10;
}

int values[] = {4371,1323,6173,4199,4344,9679,1989};

Выход для хэш-набора размером 10:

9679,
4371,
1989,
1323,
6173,
4344,
0,
0,
0,
4199

Спасибо, что посмотрели

Answer 1

Это неверно.Подумайте, что произойдет, если value[i] равно нулю:

   if (hashTable[k] == 0) {
        hashTable[k] = values[i];
   } else { .... }

Поскольку вы используете ноль в хеш-таблице, чтобы означать, что запись не используется, и вы также присваиваете значения непосредственно в таблицу, ваш код не можетотличить нулевое значение от пустой записи.

Answer 2

Почему ваша хеш-функция просто возвращает value % 10?Лучше вернуть value % hashTable.length.Я бы предложил вам использовать Integer.hashCode , а затем выполнить модуль с hashTable.length

int counter = k%hashTable.length+1;
if(counter >= hashTable.length)
    counter = 0;

. Эти два оператора можно заменить на: int counter = k % hashTable.length

Чтобы сделать его более эффективным, у вас может быть дополнительный бухгалтерский учет, где вы храните незаполненные индексы в хеш-таблице, и при заполнении вы запрашиваете этот незаполненный массив (или лучшую структуру данных), которая может быть отсортирована по дереву для поиска, вставкии удаление быстрее), когда у вас есть столкновения.