Структуры данных. Ассоциативный массив на основе хеш-таблиц

На этой лекции мы рассмотрим одну из реализация ассоциативного массива на основе хеш-таблиц. Узнаем как описываются и реализуются составляющие его компоненты. Рассмотрим алгоритмы разрешения коллизий, и реализуем его на нескольких языках программирования.

0:00 Вступление
0:30 Определение ассоциативного массива
01:43 Хеш-таблица
02:52 Способы разрешения коллизий в хеш-таблицах
04:33 Разрешение коллизий методом списков
16:58 Реализация на Python
24:35 Разрешение коллизий методом открытой адресации
26:50 Линейное пробирование
38:14 Реализация на Java
47:17 Двойное хеширование
49:31 «Ленивое» удаление
51:32 Реализация на Fortran
01:02:00 Список литературы

[radmitr]

Александр, подскажите! Может я что-то неправильно делаю? Для второго примера (линейное пробирование) на Java: при удалении наблюдаю потерю доступа к элементу; это связано со сдвигом элементов. Для эксперимента изменил функции:

Выбрал seed = 0:

private void calculatePolyCoeff() {
// Random rn = new Random();
Random rn = new Random(0); // seed = 0
for (int i = 0; i < polyCoeff.length; i++) {
polyCoeff[i] = rn.nextInt(capacity);
}
}

Для теста поле сделал публичным:

public int[] polyCoeff = new int[5]; // для теста

Сделал трассировку:

public void addPair(String key, Object value) {
int index =
while (true) {
if (pairArray[index] == null) {
pairArray[index] = new Pair(key, value);
System.out.println(key + ":" + value + ", (index=" + index + ")"); // трассировка
size++;
break;
} else if {
pairArray[index].value = value;
System.out.println(key + ":" + value + ", (index=" + index + ")"); // трассировка
break;
} else {
System.out.println(key + ":" + value + ", (index=" + index + ")"); // трассировка
index = (index + 1) % capacity;
}
}
if (size > capacity / 2) {
upResize();
}
}

Для наглядности отображаю ячейки с null:

public String toString() {
String result = "{";
for (Pair pair : pairArray) {
if (pair != null) {
result += pair.key + ":" + pair.value + ", ";
} else {
result += "null, ";
}
}
return result.substring(0, result.length() - 2) + "}";
}

В main() удаляю "one", потом хочу получить "two", а доступ к нему потерян:

public static void main(String[] args) {
HashTable hashTable = new HashTable();



hashTable.addPair("one", 1);
hashTable.addPair("five", 5);
hashTable.addPair("four", 4);
hashTable.addPair("two", 2);
hashTable.addPair("three", 3);
hashTable.addPair("nine", 9);


hashTable.remove("one");



}

Вывод такой:

[11, 13, 3, 9, 10]
one:1, (index=4)
two:2, (index=6)
three:3, (index=4)
three:3, (index=5)
four:4, (index=4)
four:4, (index=5)
four:4, (index=6)
four:4, (index=7)
five:5, (index=0)
nine:9, (index=0)
nine:9, (index=1)
{five:5, nine:9, null, null, one:1, three:3, two:2, four:4, null, null, null, null, null, null, null, null}
{five:5, nine:9, null, null, three:3, two:2, four:4, null, null, null, null, null, null, null, null, null}
null


У "two" был индекс = 6, но после удаления "one" (индекс=4), "four" сдвинулся на индекс = 4, а "two" сдвинулся на индекс = 5. При получении элемента "two", искать начинаем с индекса = 6, а там "three", потом на индексе = 7 имеем null.ind

[Денис-дуд]

Вычисление полиномиального хэша в теории различается с тем, что представлено на языке Java. Или я ошибаюсь?