Э... Не понял, в чём понт. В лучшем случае число бит хэша вдвое меньше, чем в ключе, про худшие молчу. Разве такого результата трудно добиться? Видится очень узкое применение - только для коротеньких ключей в статических словарях. С ходу и не вспомню, когда мне такое последний раз требовалось.
Тут число бит хеша это ceil(log2(количество_элементов_в_таблице)). Оно генерирует минимальные идеальные хеш-функции по известному набору элементов. Нужно это для случаев, если нужно сделать развесистый свитч по непоследовательным значениям кейсов (WM_* в оконной процедуре, например), и он будет вызываться из какого-нибудь нагруженного цикла. Тогда можно вычислить такую хеш-функцию, что все эти WM_* будут маппится на интервал 0..N-1, где N это количество кейсов, и использовать это число как индекс джамп-массива. В результате будет требоваться не 20-30 условных переходов с соответствующей вероятностью сброса конвеера, а вычисление хеша, одно обращение к массиву и один переход.
А, ну WM_* - как раз, да (из 16 бит в 8-9, табличка разумного размера). Если в компилятор встроят - хорошо. Хотя откуда тут сейчас 20-30 условных переходов - не понял. Вроде ж компиляторам хватает ума строить дерево, нет?
Мне-то обычно хэши нужны от строки, а то и от чего похуже. Или, как минимум, мапа из поинтера в поинтер (по 64 бита) - но тут редко есть статическая таблица.
... Почитал ещё, погуглил немного... В общем, тема проработана давно и достаточно глубоко, вплоть до наличия стандартной тулзы gperf (у меня на маке есть, хотя специально не ставил, возможно, встала с xcode), а статья - очень ограниченный частный случай (со ссылкой на работу 15-летней давности с более полными алгоритмами)
_Иногда_ компиляторам хватает ума строить дерево, но у меня всё равно юзкейс похитрее. Мне gperf на шаблончиках нужен, увы. А статью я и поновее читал, только мне не нужны строки, и строить рандомные графы я не могу, по причине отсутствия rand<>::value.
Comments 10
Видится очень узкое применение - только для коротеньких ключей в статических словарях. С ходу и не вспомню, когда мне такое последний раз требовалось.
Reply
Reply
Хотя откуда тут сейчас 20-30 условных переходов - не понял. Вроде ж компиляторам хватает ума строить дерево, нет?
Мне-то обычно хэши нужны от строки, а то и от чего похуже. Или, как минимум, мапа из поинтера в поинтер (по 64 бита) - но тут редко есть статическая таблица.
... Почитал ещё, погуглил немного... В общем, тема проработана давно и достаточно глубоко, вплоть до наличия стандартной тулзы gperf (у меня на маке есть, хотя специально не ставил, возможно, встала с xcode), а статья - очень ограниченный частный случай (со ссылкой на работу 15-летней давности с более полными алгоритмами)
Reply
Reply
Reply
Reply
Leave a comment