Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.17.162.247] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Дана хеш-таблица, состоящая из 10 элементов. Она должна хранить натуральные неповторяющиеся числа. Стартовая инициализация такая (пусть С++ - индекс от нуля): 0 0 0 0 0 0 0 0 0 0 - хранимое число --------------------- 0 1 2 3 4 5 6 7 8 9 - индекс элемента Абсолютно не важно, какой является хеш-функция, но известно, что она не является совершенной, т е возможны коллизии! Ключом выступает само значение числа. Допустим, на вход подаются числа: 12, 16, 8, 27, 13 Я пытаюсь использовать линейное пробирование, у которого интервал шага = 1. Для числа 12 хеш-функция вернула хеш-значение равное 4 (т е 4 - индекс в хеш-таблице, куда попадет число 12). Для 16 индекс 9. Для 8 индекс 2. Для 27 индекс 5. Вот что представляет из себя хеш-таблица после добавления 4-рех чисел: 0 0 8 0 12 27 0 0 0 16 - хранимое число --------------------- 0 1 2 3 4 5 6 7 8 9 - индекс элемента Для 13 индекс получился = 4! Коллизия! Карман этот занят. Поэтому я тупо начинаю искать свободное место, добавляя +1 к индексу. Перехожу на индекс 5. Он тоже занят. Иду дальше и попадаю в позицию 6 - свободно! Значит, туда поставлю число 13 и получу: 0 0 8 0 12 27 13 0 0 16 - хранимое число --------------------- 0 1 2 3 4 5 6 7 8 9 - индекс элемента Как работает вставка вроде все понятно. Также есть булевый флаг, показывающий свободна/занята ячейка, если свободно - вставляю, если просмотрел каждый карман и все заняты - вставка невозможна, т к ХТ заполнена (либо расширять таблицу). Мне до конца непонятно, как будет работать удаление из этой ХТ! Допустим, хочу удалить число 12. Хеш-функция вернула индекс 4. Обращаюсь к этой ячейке, она занята и там стоит именно 4. Ставлю флаг - свободно (типа удалил число). 0 0 8 0 12 27 13 0 0 16 - хранимое число --------------------- 0 1 2 3 4 5 6 7 8 9 - индекс элемента И потом хочу удалить число 13. Хеш функция вернула индекс = 4. Смотрю этот карман, а там СВОБОДНО (предыдущей операцией оттуда было удалено число 12). Что делать в этом случае? Шагать дальше в поиске числа 13? А, если этого числа изначально не было бы в хеш-таблице, тогда придется впустую просмотреть всю таблицу? |
Сообщ.
#2
,
|
|
|
Удалённые помечаются флагом удалённых, а не флагом пустых.
При поиске элемента если мы наткнулись на флаг "удалённый" то продолжаем поиск. Если наткнулись на флаг "пустой", то останавливаем поиск и сообщаем о отсутствие искомого элемента. При поиске свободного места ищем тот флаг который попадётся первым "удалённый" или "пустой". Как и 7 лет назад рекомендую: http://www.cs.cmu.edu/afs/cs.cmu.edu/user/...ear-hashing.PDF |
Сообщ.
#3
,
|
|
|
Так, если я правильно понял, то каждый элемент имеет ТРИ состояния, да:
- пустой - занятый - удаленный ---------------------------- Во всех статейках, которые посматривал, говорилось про булевый флаг (а это лишь 2 значения), а не тернарную переменную. Лишь это меня смущает, что не до конца уловил что-то! Добавлено А, я понял кажется, нужно иметь две флаговые переменные: struct TElem { int value; bool isDeleted; bool isEmpty }; ---------------- И, если isDeleted == false и isEmpty == false -----> занятый спс за помощь! |
Сообщ.
#4
,
|
|
|
Цитата FasterHarder @ Скорее всего там говорилось о хэш-таблицах без удаления. Или писавший сам никогда с таблицами дела не имел.Во всех статейках, которые посматривал, говорилось про булевый флаг Вместо двух булевых переменных всё-же лучше иметь одну, на три состояния. Будет занимать меньше места, меньше проверок, меньше присваиваний. |
Сообщ.
#5
,
|
|
|
FasterHarder
0 - не относится к натуральным числам. Поэтому он заменяет флаг isEmpty. Отсюда и минус 1 флаг. Но я бы оставил 2 флага для наглядности. Да и натуральный ряд удобно расширить до 0 и иметь в value весь набор чисел желательно. |
Сообщ.
#6
,
|
|
|
В общем полностью разобрался с открытой адресацией и закодировал уже на С++ с применением статического одномерного массива на натуральных числах - все достаточно легко оказалось!
|
Сообщ.
#7
,
|
|
|
Цитата Pavia @ Это называется неотрицательные целые.натуральный ряд удобно расширить до 0 Для наглядности можно было ввести несколько inline-функций, проверяющих значение небинарного флага. |