Логика работы метода push в хеш таблице

316

30 января 2017, 17:11

Здравствуйте, я нашел вариант реализации хэш-таблицы, но мне непонятна логика работы метода push:

public boolean push(T1 x, T2 y) {
    int h = returnHash(x); // это мы посчитали hashCode для ключа
    int i=0;
    try{
        if (table[h].isDeleted() ) { // проверили было ли там какое-то значение когда-нибудь
            table[h] = new Pair<T1, T2>(x, y);// если да то записали новое
            return true;
        }
        for (i = h + 1; i != h; i = (i + 1) % table.length) {//вот это место вообще не понятно
            if (table[i].isDeleted() || table[i].getKey() == x) {
                table[i] = new Pair<T1, T2>(x, y);
                return true;
            }
        }
        return false;
    } catch(NullPointerException e) {
        table[h] = new Pair<T1, T2>(x, y);
        return true;
    }
}

Откуда взялся этот цикл? Зачем он нужен? Почему просто не проверить что ячейка null и записать туда, либо нет?

Answer 1

Приведенный Вами фрагмент реализации HashMap использует метод открытой адресации для разрешения коллизий.

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

Откуда взялся этот цикл? Зачем он нужен?

Этот цикл используется для поиска пустой корзины для размещения в ней добавляемой пары при возникновении коллизии.

Почему просто не проверить что ячейка null и записать туда, либо нет?

Если Вы внимательно посмотрите код, то здесь (в частности) это реализовано: сначала, исходя из хэш-кода ключа вычисляется номер корзины (h), затем происходит обращение к table[h]:

table[h].isDeleted()

при котором, если table[h] == null, то будет сгенерировано исключение NullPointerException, которое тут же и обрабатывается:

table[h] = new Pair<T1, T2>(x, y);

Следовательно, если в корзине с номером h ничего нет и не было, то пара будет размещена там, если раньше в корзине что-то было, но сейчас уже нет (случай, когда table[h].isDeleted() == true), то опять же пара будет размещена в этой корзине, а если корзина занята, то будет произведет поиск другой корзины, в которой и будет размещена добавляемая пара.

Хочу обратить внимание, что реализация HashMap из JDK использует другой метод для разрешения коллизий, а именно, метод цепочек.

Кстати, это какая-то весьма странная реализация добавления пары в HashMap:

Если все корзины заняты, то очередная добавляемая пара просто не будет добавлена в HashMap (в данной реализации массив не расширяется и пары не перераспределяются по корзинам);
В HashMap метод для вставки пары традиционно именуется как put, а push относится к стеку.