Значение открытого и закрытого хэширования
Открыть Хэширование (Отдельная Цепочка):
в открытом хэшировании ключи хранятся в связанных списках, прикрепленных к ячейкам хэш-таблицы.
Закрытое Хэширование (Открытая Адресация):
в закрытом хэшировании все ключи хранятся в самой хэш-таблице без использования связанных списков.
Я не могу понять, почему они называются открытыми, закрытыми и отдельными. Может кто-нибудь объяснить это?
4 ответов:
использование " закрыто "против" открыто " отражает, заблокированы ли мы для использования определенной позиции или структуры данных (это чрезвычайно расплывчатое описание, но, надеюсь, остальное поможет).
например, "open "в" open addressing " сообщает нам индекс (aka. адреса), по которому объект будет храниться в хэш-таблице не полностью определяется его хэш-код. Вместо этого индекс может варьироваться в зависимости от того, что уже есть в хэш-таблице.
в "закрытый "в" закрытом хэшировании " относится к тому, что мы никогда не покидаем хэш-таблицу; каждый объект хранится непосредственно в индексе во внутреннем массиве хэш-таблицы. Обратите внимание, что это возможно только с помощью какой-то стратегии открытой адресацией. Это объясняет, почему "закрытое хэширование" и "открытая адресация" являются синонимами.
сравните это с открытым хэшированием - в этой стратегии ни один из объектов фактически не хранится в массиве хэш-таблицы; вместо этого, как только объект хэшируется, он сохраняется в списке, который отделен от внутреннего массива хэш-таблицы. "открыть" относится к свободе, которую мы получаем, оставляя хэш-таблицу и используя отдельный список. Кстати, "отдельный список "намекает на то, почему открытое хэширование также известно как"отдельная цепочка".
короче говоря, "закрытый" всегда относится к какой-то строгой гарантии, например, когда мы гарантируем, что объекты всегда хранятся непосредственно в хэш-таблице (закрытое хэширование). Тогда противоположность "закрыто" - "открыто", поэтому, если у вас нет такие гарантии стратегия считает "открытыми".
имя открыть решении относится к тому, что местоположение ("адрес") элемента не определяется его хэш-значением. (Этот метод также называется закрытым хэшированием).
на отдельные цепочки, каждое ведро является независимым и имеет какой-то ADT (список, двоичные деревья поиска и т. д.) записей с одним и тем же индексом. В хорошей хэш-таблице каждое ведро имеет ноль или одну запись, потому что нам нужны операции порядка O (1) для вставки, поиска, так далее.
Это пример на отдельные цепочки использование C++ с простой хэш-функцией с помощью оператора mod (очевидно, плохая хэш-функция)
У вас есть массив, который является "хэш-таблицы".
при открытом хэшировании каждая ячейка массива указывает на список, содержащий коллизии. Хэширование произвело один и тот же индекс для всех элементов в связанном списке.
в закрытом хэшировании вы используете только один массив для всего. Вы храните коллизии в том же массиве. Фокус в том, чтобы использовать какой-то умный способ перейти от столкновения к столкновению unitl вы найдете то, что хотите. И сделать это в воспроизводимом / детерминированном виде путь.
Ну это так просто понять концепцию открытого и закрытого хэширования,
в открытом хэшировании он принимает свойство списка ссылок, которое ссылается, если какой-либо ключ индекса уже имеет элемент данных,чем мы можем вставить другой элемент данных в том же месте, ясно, что он открыт для данных, которые имеют одно и то же место после того, как он уже занят другим.
и в Close, если данные получают расположение в таблице, то никакие данные не могут использовать это адрес..
решена........легко
Comments