Должен ли метод get получить сбой при линейном зондировании, если между ними есть нуль Если нет, то как мне реализовать метод get? - PullRequest
Новая
       18

Должен ли метод get получить сбой при линейном зондировании, если между ними есть нуль Если нет, то как мне реализовать метод get?

0 голосов
/ 30 апреля 2020

Итак, я создаю хеш-таблицу с нуля, используя линейное зондирование в Java следующими методами: put (int key, String value), get (int key), remove (int key) и size (). Поэтому я успешно реализовал эти методы, но у меня есть теоретический вопрос. Скажем, например, я делаю следующее: 

    var map = new HashMap(5);
    map.put(1, "a");
    map.put(3, "b");
    map.put(4, "c");
    map.put(8, "d");
    map.put(13, "e");
    map.remove(8);
    System.out.println(map);
    System.out.println(map.get(13));

Мой метод пут работает правильно и размещает пары ключ-значение в соответствии с линейным зондированием al go. Теперь мой вывод:

[null, 1 = a, 13 = e, 3 = b, 4 = c] null

Итак, мой вопрос, должен ли мой метод get получить теоретически сбой (из-за линейного зондирования), чтобы получить пару ключ-значение 13 = e, потому что метод удаления помещает ноль в индекс 0. Кроме того, если я не использую удаление, я успешно получаю пару 13 = e.

1 Ответ

0 голосов
/ 30 апреля 2020

Ваш вопрос очень разумный и является одной из известных проблем с линейным зондированием.

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

Вы также можете задать его по-другому, как правильно искать значение, если вы знаете, что некоторые значения в пути могут быть нулевыми (удаленные элементы).

Одним из решений будет поиск до тех пор, пока вы не пройдете всю карту, и, если он не найден, верните ноль. Но это действительно плохое решение, потому что каждый раз, когда вы используете свой метод get (или содержит) для значения, которого нет на карте, вам придется go пройти по всей карте (сложность O (n)) что неприемлемо, потому что HashMaps должны реализовывать эти методы как минимум в среднем постоянной сложности (* O (1)).

Так что существует множество решений, и вы можете исследовать и читать о них. Я дам вам одно решение, которое я знаю:

В вашем HashMap сохраните другой массив, который будет содержать при каждом индексе максимальное количество шагов (или скачков), которые требовались для того, чтобы поместить значение в карту где этот индекс был первым, к которому вы пришли. Каждый раз, когда вы помещаете новое значение в карту (используя метод put), ваш метод запоминает первый индекс, к которому вы перешли, и затем, если общее количество прыжков, через которое вы должны были пройти go, было больше, чем максимальное число шагов в этом индексе в ваш вспомогательный массив, вы обновляете его.

Теперь, в ваших методах get () и contains (), когда вы делаете первый шаг, вы читаете максимальные шаги, которые разрешены из вспомогательного массива, а затем вы нужно только перепрыгнуть это количество шагов, пока вы не будете уверены, что ваше значение не существует. Это вместо остановки, когда вы получаете нулевой ключ.

...