Обработка коллизий хешей при использовании линейного зондирования

Question

Я читал о хэш-таблицах и открытых адресах. Если вы хотите вставить ключи: 18,32,44 в хеш-таблицу с размером 13:

18 gets index 5 (18 modulus 13 = 5)
32 gets index 6 (32 modulus 13 = 6)
44 gets index 5 (44 modulus 13 = 5)

Вы получите столкновение, потому что в индексе 5 уже есть что-то.

Если вы используете линейное зондирование, вы будете делать hashfunction = (key+i) modulus N, где i = 0,1,2.., пока не найдете пустое место в хеш-таблице. Тогда 44 будет вставлено в индекс 7.

Что, если вы удалите 32, а затем захотите удалить 44. Сначала вы посмотрите на hashfunction(44)=5 - это было не 44, а затем hashfunction(44 + 1) = 6 - пусто. Тогда вы можете подумать, что 44 прошло. Как пометить место в хеш-таблице, что это место на самом деле не пустое, но не содержит ключа, и что вы должны продолжать искать 44 при следующем индексе?

Если вам необходимо вставить другой ключ с индексом 6, тогда ключ просто перезаписывает «метку» в хеш-таблице.

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

Answer 1

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

Когда значение удаляется, слот помечается какDELETED, а не EMPTY.Когда вы попытаетесь получить значение, вы будете проверять, пока не найдете слот с отметкой EMPTY;Например: вы считаете DELETED слоты такими же, как OCCUPIED.Обратите внимание, что вставка может игнорировать это различие - вы можете вставить в DELETED или EMPTY слот.

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

Как вы можете видеть, резкое падение производительности около 0,7отметка.Размер большинства хеш-таблиц изменяется после того, как их коэффициент загрузки превышает определенный постоянный коэффициент.Например, Java удваивает размер HashMap, когда коэффициент загрузки превышает 0,75.

Answer 2

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

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

В википедии есть некоторый псевдокод, достаточно хорошо описывающий это:

http://en.wikipedia.org/wiki/Open_addressing

Answer 3

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

Answer 4

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

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