Хеш-таблица. Непонятно с решением коллизии методом перемешивания внутренними цепочками

[Познающий]

Всем привет!
Ребят проблема такая странная... не могу понять как работает вот этот метод. Сколько мучался и в фундаментальные алгоритмы на с++ лазил.. ничегодля себя не нашел...

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

[notHaker]

вот http://ru.wikipedia.org/wiki/Коллизия. А так ты праильно догнал. Поюзай получше...

[Познающий]

да бывал я там и подавно...

Там нашел разрешение коллизий в хеше, так там всего два слова и ДВЕ классификации( надклассы как я понимаю)
То есть метода есть два:
Цепочками и открытая адресация.
Из них вытекают по два и один подметода

Цепочки - Перемешивание с внутренними цепочками - Перемешивание с цепочками переполнения.

О.А. - открытое перемешивание...

Блин в википедии связного ничего нет из того что мне нужно, чтоб для "особо одаренных" объяснили на рисуночках как оно происходит.

и что от меня вообще нужно (

[notHaker]

Сообщение от Познающий

да бывал я там и подавно...

Там нашел разрешение коллизий в хеше, так там всего два слова и ДВЕ классификации( надклассы как я понимаю)
То есть метода есть два:
Цепочками и открытая адресация.
Из них вытекают по два и один подметода

Цепочки - Перемешивание с внутренними цепочками - Перемешивание с цепочками переполнения.

О.А. - открытое перемешивание...

Блин в википедии связного ничего нет из того что мне нужно, чтоб для "особо одаренных" объяснили на рисуночках как оно происходит.

и что от меня вообще нужно (

А зачем тебе хеширование?

[Познающий]

Сформировть табличку.

Это все связано с сортировкой и базами данных =)
Надо отсортировать табличку хешированием и потом сбацать поиск который, по идее, круче бинарного

[notHaker]

http://pmg.org.ru/ai/hash.htm

вот ещё нашёл, но там С. А так всё поясняется.

[Познающий]

да там немного о хешировании и как это все круто

чьорт ну мне надо само устройство алгоритма перемешивания внутренними цепочками блин...

[Познающий]

тэкс нарыл что раз уж цепочками, то коллизия решается просто - если на место претендуют два элемента, то они становятся цепочкой %|

Только не пойму чем отличается внутреннее от внешнего?
Кое-где пишется что это типа мы в старую таблицу в свободных ячейках будем хранить цепочки %X ужс

[Познающий]

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


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


Мне просто один парень помог и может быть эта запись тоже кому-то поможет... так как на форуме было где-то три темы и я чето не увидел в них разжеванного ответа

[notHaker]

Сообщение от Познающий

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


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


Мне просто один парень помог и может быть эта запись тоже кому-то поможет... так как на форуме было где-то три темы и я чето не увидел в них разжеванного ответа

короч хз... но! переборы массива не пойдут, тк на кой тебе тада хеш таблица?

незнаю, подойдёт ли тебе эта штука, но получай... её я использовал, када создавал некое подобие дескрипторов. просьба не пинать, если не то.

(ТОЛЬКО для скорости) допустим массив дескрипторов. если я несколько раз добавляю, а потом удаляю и у меня образуется окно. прежде чем завршить процесс удаления я добавляю индекс удалённого элемента в другой массив того же размера с индексом равным количеству удалённых. и в следующий раз када буду добавлять в массив дескрипторов, сначала я обращусь в массив с этими окнами, если количество удалённых больше 0. вот.