Разрешение коллизий — различия между версиями
(Создание страницы) |
(Описание) |
||
| Строка 1: | Строка 1: | ||
'''Поиск свободного места при закрытом хешировании''' - задача, возникающая при создании хеш-таблицы, использующей так называемое зарытое хеширование. | '''Поиск свободного места при закрытом хешировании''' - задача, возникающая при создании хеш-таблицы, использующей так называемое зарытое хеширование. | ||
| + | |||
| + | При использовании открытого хеширования такой проблемы не возникает, так как там в каждой ячейке хранится список всех элементов. При добавлении необходимо просто дописать элемент в конец списка. | ||
| + | |||
| + | Закрытое хеширование работает иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята - необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции. | ||
Версия 23:16, 15 мая 2011
Поиск свободного места при закрытом хешировании - задача, возникающая при создании хеш-таблицы, использующей так называемое зарытое хеширование.
При использовании открытого хеширования такой проблемы не возникает, так как там в каждой ячейке хранится список всех элементов. При добавлении необходимо просто дописать элемент в конец списка.
Закрытое хеширование работает иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята - необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции.
