Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > хранение и поиск по ключу SHA1

Автор: null56 29.2.2012, 17:25

Задача  следующая:  http://tools.ietf.org/html/draft-ietf-manet-smf-13#section-6.2.2 Необходимо организовать таблицу, ключом к которой является 20 байтное значение SHA-1 Подскажите пожалуйста каким образом наиболее эффективно можно организовать данную таблицу? У меня были варианты c radix, rb tree, но у них есть свои недостатки из - за довольно большого и главное произвольного значения самого SHA-1. Я не против rb tree, но проверка 20 байтов при довольно частом обращении и большом количестве записей, мне кажется накладно. Частота поступления запросов очень большая... Может быть кто - нибудь огранизовывал хеш таблицу по такому ключу? Заранее благодарен за помощь

Автор: volatile 1.3.2012, 00:19

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

Автор: null56 1.3.2012, 13:34

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

Автор: boostcoder 1.3.2012, 14:16

null56, так а в чем проблема? нет готовой реализации rb tree на Си? или нет возможности назначит свой предикат, который будет работать как предложил volatile ? Цитата(null56 @  29.2.2012,  17:25 ) radix это что?

Автор: null56 1.3.2012, 14:50

Цитата(boostcoder @  1.3.2012,  14:16 ) это что?  дерево корней или как там его еще называются http://en.wikipedia.org/wiki/Radix_tree Цитата(boostcoder @  1.3.2012,  14:16 ) нет готовой реализации rb tree на Си? или нет возможности назначит свой предикат, который будет работать как предложил volatile ? мне интересно хеширование больше, потому что 20 байтов ключ + поиск по довольно большой таблице, ибо данное значение вычисляется и ищется и со временем удаляется в дереве для КАЖДОГО приходящего мультикаст пакета.... я правильно понял, что первые 4 байта 20 байтного хеша будут хорошо разбросаны?

Автор: boostcoder 1.3.2012, 14:54

Цитата(null56 @  1.3.2012,  14:50 ) потому что 20 байтов ключ т.е. смущает сам размер ключа? или то что сравнение такого ключа будет затратно? Цитата(null56 @  1.3.2012,  14:50 ) первые 4 байта 20 байтного хеша будут хорошо разбросаны? тут нужно хорошо знать SHA1. но допустим, не очень хорошо... в таком случае, если в предикате совпадают первые 4 байта, ты можешь сравнить следующие 4 байта. и так до тех пор, пока не найдешь неравенство, или пока не достигнешь полного ключа. это будет означать что ключи равны. такой способ сравнения довольно незатратен.

Автор: null56 1.3.2012, 14:57

Цитата(volatile @  1.3.2012,  00:19 ) Само условие явно не эффективно, но это уже другой вопрос.  ну это не я придумал, так в документе описано, не знаю чем они руководствовались при написании Добавлено через 11 минут и 59 секунд Цитата(boostcoder @  1.3.2012,  14:54 ) т.е. смущает сам размер ключа? или то что сравнение такого ключа будет затратно? сравнение наверное более критично Цитата(boostcoder @  1.3.2012,  14:54 ) тут нужно хорошо знать SHA1. но допустим, не очень хорошо... в таком случае, если в предикате совпадают первые 4 байта, ты можешь сравнить следующие 4 байта. и так до тех пор, пока не найдешь неравенство, или пока не достигнешь полного ключа. это будет означать что ключи равны. вопрос что хранить в качестве ключа? 4 байта хорошо... использовать в качестве индекса хештаблицы, вообще отлично... при колизиях, которые, если верить, что первые 4 байта будут хорошо перемешаны, сравнивать до конца, для окончательного поиска... + при колизиях SHA-1 у нас еще имеются дополнительные параметры сравнения saddr, daddr, но это уже другой вопрос для обсуждения

Автор: boostcoder 1.3.2012, 15:12

Цитата(null56 @  1.3.2012,  14:57 ) вопрос что хранить в качестве ключа? так саму SHA1 и хранить. или я чего-то не понял?...

Автор: null56 1.3.2012, 15:18

кстати, нашел реализацию smf на с++ надо глянуть, как они там поступают http://cs.itd.nrl.navy.mil/work/smf/index.php Добавлено через 5 минут и 45 секунд Цитата(boostcoder @  1.3.2012,  15:12 ) так саму SHA1 и хранить. или я чего-то не понял?...  ну вообще разницы тогда я не очень понимаю, по 4 байта мы сравниваем или memcmp 20 байтов я так понял, volatile предолжил использовать первые 4 байта, как хеш ключ, чтобы находить узел (или колизию) за время 0(1), тогда сравнение потребуется только для редких колизий radix не подходит из - за сильного разброса всех 20 байтов

Автор: boostcoder 1.3.2012, 15:32

Цитата(null56 @  1.3.2012,  15:18 ) вообще разницы тогда я не очень понимаю, по 4 байта мы сравниваем или memcmp 20 байтов так разница в затратах. зачем сравнивать 20 байт, когда, к примеру, первые два уже не равны? ;) Цитата(null56 @  1.3.2012,  15:18 ) volatile предолжил использовать первые 4 байта, как хеш ключ ох и стрёмно это)

Автор: null56 1.3.2012, 15:36

Цитата(boostcoder @  1.3.2012,  15:32 ) зачем сравнивать 20 байт, когда, к примеру, первые два уже не равны? ;) я имел в виду, что функция memcmp выйдет после несовпадения первого же байта(хотя может это зависит от реализации), а при вытаскивании по 4 байта и сравнение их, мне кажется инструкций потребуется больше

Автор: boostcoder 1.3.2012, 15:46

Цитата(null56 @  1.3.2012,  15:36 ) функция memcmp выйдет после несовпадения первого же байта точно! вот я затупил...

Автор: volatile 1.3.2012, 23:39

Цитата(null56 @  1.3.2012,  15:18 ) я так понял, volatile предолжил использовать первые 4 байта, как хеш ключ, чтобы находить узел (или колизию) за время 0(1), тогда сравнение потребуется только для редких колизий Да, именно так. Цитата(null56 @  1.3.2012,  14:50 ) я правильно понял, что первые 4 байта 20 байтного хеша будут хорошо разбросаны?  Не только первые, а вообще любые байты у профессиональных хешей md5,md4, sha1, и т.д. разбросаны очень хорошо. sha1 вообще разрабатывался как криптоустойчивый хеш, поэтому разброс там очень и очень хорош!

Автор: Nica 2.3.2012, 00:31

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

Автор: null56 2.3.2012, 11:08

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

Автор: volatile 2.3.2012, 23:20

null56, хеш таблицы ? вы имеете ввиду что-то вроде хеш мап, хеш сет, т.е быстрый доступ по хеш. Не,  руками не приходилось делать. В С++ оно почти встроено, поэтому велосипед в этом плане не изобретал. Но можно посмотреть как это делают в том-же бусте, например. Кстати, недавно ребята исследовали boost::unordered_map, так он показывал сногсшибательную скорость. boostcoder, не даст соврать   В студии stdext::hash_map тоже очень не плох. Но в вашем случае алгортим boost::unordered_map будет, пожалуй, получше. Он на коротких строках особенно быстр. Исходники открыты, можно поразбираться...

Автор: null56 5.3.2012, 11:53

начну мучать boostcoder

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)