Открыть хеширование (отдельное цепочка):
В открытом хэшировании ключи хранятся в связанных списках, прикрепленных к ячейкам хэш-таблицы.
Закрытое хеширование (Open Addressing):
В закрытом хэшировании все ключи хранятся в самой хэш-таблице без использования связанных списков.
Я не могу понять, почему они называются открытыми, закрытыми и отдельными. Может кто-нибудь объяснить это?
Использование "закрытого" и "открытого" отражает, действительно ли мы заперты в использовании определенной позиции или структуры данных (это очень неопределенное описание, но, надеюсь, остальное помогает).
Например, "open" в "открытой адресации" указывает нам, что индекс (ака-адрес), в котором объект будет храниться в хэш-таблице, не полностью определяется его хеш-кодом. Вместо этого индекс может меняться в зависимости от того, что уже находится в хеш-таблице.
"Закрыто" в "закрытом хешировании" относится к тому факту, что мы никогда не покидаем хеш-таблицу; каждый объект хранится непосредственно в индексе в внутреннем массиве хэш-таблицы. Обратите внимание, что это возможно только при использовании какой-либо стратегии открытой адресации. Это объясняет, почему "закрытое хеширование" и "открытая адресация" являются синонимами.
Контрастируйте это с открытым хэшированием - в этой стратегии ни один из объектов фактически не хранится в массиве хэш-таблицы; вместо того, чтобы объект хэширован, он сохраняется в списке, который отделен от внутреннего массива хэш-таблицы. "open" означает свободу, которую мы получаем, оставляя хеш-таблицу и используя отдельный список. Кстати, "отдельный список" подсказывает, почему открытое хеширование также известно как "отдельная цепочка".
Короче говоря, "закрыто" всегда ссылается на какую-то строгую гарантию, например, когда мы гарантируем, что объекты всегда хранятся непосредственно в хэш-таблице (закрытое хеширование). Тогда противоположность "закрыта" "открыта", поэтому, если у вас нет таких гарантий, стратегия считается "открытой".
Имя открытая адресация относится к тому факту, что местоположение ( "адрес" ) элемента не определяется его хеш-значением. (Этот метод также называется замкнутым хешированием).
В отдельной цепочке каждый ведро является независимым и имеет своего рода ADT (список, двоичные деревья поиска и т.д.) записей с тем же индексом. В хорошей хеш-таблице каждое ведро имеет ноль или одну запись, потому что нам нужны операции порядка O (1) для вставки, поиска и т.д.
Это пример отдельной цепочки с использованием С++ с простой хэш-функцией с использованием оператора mod (очевидно, плохая хэш-функция)
У вас есть массив, который является "хэш-таблицей".
При открытом хешировании каждая ячейка в массиве указывает на список, содержащий коллизии. Хеширование произвело одинаковый индекс для всех элементов в связанном списке.
В Closed Hashing вы используете только один массив для всего. Вы сохраняете коллизии в одном и том же массиве. Хитрость заключается в том, чтобы использовать какой-то умный способ перейти от столкновения к столкновению, если вы найдете то, что хотите. И сделайте это воспроизводимым/детерминированным способом.
Хорошо, это так просто понять концепцию хэширования Open And Close,
В Open hashing, он принимает свойство списка ссылок, которое ссылается, если любой ключ индекса allready имеет элемент данных, чем мы можем вставить другой элемент данных в том же месте, очевидно, что он открыт для данных, имеющих такое же местоположение после того, как он уже занят другим.
И в Close, если данные получают местоположение в таблице, чем никакие данные не могут использовать этот адрес.
Решенный........ простой na
