Задача  следующая: 
http://tools.ietf.org/html/draft-ietf-mane...3#section-6.2.2
Необходимо организовать таблицу, ключом к которой является 20 байтное значение SHA-1

Подскажите пожалуйста каким образом наиболее эффективно можно организовать данную таблицу?
У меня были варианты c radix, rb tree, но у них есть свои недостатки из - за довольно большого и главное произвольного значения самого SHA-1.

Я не против rb tree, но проверка 20 байтов при довольно частом обращении и большом количестве записей, мне кажется накладно. Частота поступления запросов очень большая...

Может быть кто - нибудь огранизовывал хеш таблицу по такому ключу?

Заранее благодарен за помощь

хеш мап. на С++.
Причем хешем для 20 байтов sha1 написать простейшую функцию, выбирающую просто первое слово (4 байта из 20)
В силу того что sha1 очень не плохо перемешан, это будет хороший и быстрый хеш.
Все возможные коллизии, (а их будет совсем не много), разрешит хеш.мап.
Быстрее, имхо, врядли что-то можно придумать в данном случае.
(только если изменить само условие)

Само условие явно не эффективно, но это уже другой вопрос.

а можно по подробнее по организации... особенно по формированию хеш таблицы... ++ у меня не будет возможности использовать, всё будет в ядре
подробнее по выбору ключа и расширению таблицы, тут мне подсказать можете?

null56, так а в чем проблема?
нет готовой реализации rb tree на Си? или нет возможности назначит свой предикат, который будет работать как предложил volatile ?


это что?

дерево корней или как там его еще называются
http://en.wikipedia.org/wiki/Radix_tree

мне интересно хеширование больше, потому что 20 байтов ключ + поиск по довольно большой таблице, ибо данное значение вычисляется и ищется и со временем удаляется в дереве для КАЖДОГО приходящего мультикаст пакета....

я правильно понял, что первые 4 байта 20 байтного хеша будут хорошо разбросаны?

т.е. смущает сам размер ключа? или то что сравнение такого ключа будет затратно?


тут нужно хорошо знать SHA1.
но допустим, не очень хорошо... в таком случае, если в предикате совпадают первые 4 байта, ты можешь сравнить следующие 4 байта. и так до тех пор, пока не найдешь неравенство, или пока не достигнешь полного ключа. это будет означать что ключи равны.

такой способ сравнения довольно незатратен.

ну это не я придумал, так в документе описано, не знаю чем они руководствовались при написании

Добавлено через 11 минут и 59 секунд

сравнение наверное более критично


вопрос что хранить в качестве ключа?
4 байта хорошо... использовать в качестве индекса хештаблицы, вообще отлично...
при колизиях, которые, если верить, что первые 4 байта будут хорошо перемешаны, сравнивать до конца, для окончательного поиска...

+ при колизиях SHA-1 у нас еще имеются дополнительные параметры сравнения saddr, daddr, но это уже другой вопрос для обсуждения

так саму SHA1 и хранить. или я чего-то не понял?...

кстати, нашел реализацию smf на с++ надо глянуть, как они там поступают
http://cs.itd.nrl.navy.mil/work/smf/index.php

Добавлено через 5 минут и 45 секунд

ну вообще разницы тогда я не очень понимаю, по 4 байта мы сравниваем или memcmp 20 байтов


я так понял, volatile предолжил использовать первые 4 байта, как хеш ключ, чтобы находить узел (или колизию) за время 0(1), тогда сравнение потребуется только для редких колизий

radix не подходит из - за сильного разброса всех 20 байтов

так разница в затратах.
зачем сравнивать 20 байт, когда, к примеру, первые два уже не равны? ;)


ох и стрёмно это)

я имел в виду, что функция memcmp выйдет после несовпадения первого же байта(хотя может это зависит от реализации), а при вытаскивании по 4 байта и сравнение их, мне кажется инструкций потребуется больше

точно! вот я затупил...  

Да, именно так.


Не только первые, а вообще любые байты у профессиональных хешей md5,md4, sha1, и т.д. разбросаны очень хорошо.
sha1 вообще разрабатывался как криптоустойчивый хеш, поэтому разброс там очень и очень хорош!

1) две таблицы использовать? и этот ключ связывать по id?
2) этот ключ преобразовать с помощью mime64 ли аналога какого-то? (так же есть возможность в mime64 с фиксированной длинной)

Это сообщение отредактировал(а) Nica - 2.3.2012, 00:32

Nica, это кому вопрос, мне?

Добавлено через 3 минуты и 17 секунд
volatile, идея выглядит очень хорошо, спасибо. теперь надо понять, как разработать хеш таблицу, при том надо подобрать функцию для обработки этих 4 байтов и учесть тот факт, что таблица может увеличиваться... 

volatile, вам не приходилось создавать руками хеш таблицы? не чем поделиться в этом плане?