Под определение подходит CityHash от Google, для начала см. http://habrahabr.ru/post/117360/. По многим сценариям использования и для многих актуальных архитектур/семейств процессоров это чемпион по скорости, но не на коротких данных.
Если хочется/требуется заморочиться больше, то можно выбрать более быстрые/оптимальные варианты:
для коротких данных.
менее устойчивые к некоторым видам «атак», т.е. выдающие сильную (относительно) корреляцию между hash-значениями при определенных (хитрожопых) различиях в исходных данных.
для больших данных с использованием MMX/SSE/AVX и прочих SIMD.
Ну и раз такая гулянка, то не могу не показать свой «велосипед» https://gist.github.com/leo-yuriev/7bf20f02f3ad76c35f0d. На коротких данных он выгоднее CityHash, а на длинных медленнее, но чуть лучше с коллизиями и корреляциями.
для коротких и средних строк: h = h * 101 + *s++; для int8/16/32/64 - простое умножение на золотое сечение интервала (дает практически идеальное распределение для подряд идущих значений)
пофиг на коллизии, мне нужно оооочень неравномерно распределенные строки (пусть, например, 2^20 их) раскидать по 64 (например) корзинам так, чтобы в каждой корзине было бы их примерно поровну. Это частая операция. Изначально корзин может быть около 30, в 10 из них - по 100 строк, в 10 - по 10000, а все остальные - в оставшихся 10, например. Длина строк произвольная, поэтому сам адлер мне не подходит, потому что он там хромает.
пофиг на коллизии, мне нужно оооочень неравномерно распределенные строки (пусть, например, 2^20 их) раскидать по 64 (например) корзинам так, чтобы в каждой корзине было бы их примерно поровну. Это частая операция. Изначально корзин может быть около 30, в 10 из них - по 100 строк, в 10 - по 10000, а все остальные - в оставшихся 10, например. Длина строк произвольная, поэтому сам адлер мне не подходит, потому что он там хромает.
Хорошие показатели по коллизиям и корреляциям - более строгое требование чем равномерное распределение. Из первого автоматически вытекает второе, но не наоборот.
Очень многое зависит от того насколько оптимально хочется/требуется сделать, как по тактам CPU, так и по распределению.
Для равномерного распределения есть простой способ, который всегда сработает (ну или почти-почти всегда):
Берете простое число для количества корзин, это важно.
Используйте любую хоть-немного-вменяемую hash-функцию. Например, rot13 подойдет даже если складывать по 16/24/32 бита за итерацию.
Сдвиньте результат влево на максимальное кол-во разрядов (чтобы не выйти из unsigned long), например на 32 для x86_64.
Получайте номер корзины как остаток от деления на их кол-во (простое число).
Результат всегда будет близок к идеальному, если hash-функция не сильно пакостит коллизиями и сдвиг соответствует умножению на несколько порядков превышающему кол-во корзин.
Если деление дорого или требуется кол-во корзин по степени двойки, то проще так:
Вместо сдвига выполняете murmur-подобную операцию с большим простым числом:
a = any_hash(str);
a = (a * prime) ^ (a >> (sizeof(a) * 6 - 1));
result = (a * prime) ^ (a >> (sizeof(a) * 6 - 1));
Соответственно, так как кол-во корзин степень двойки, то вместо деления битовый and.
Не обязательно степень двойки. Грубо говоря, мне просто нужно, чтобы все строки легли поровну в какое-то количество корзин. Например, пусть 61. Чтобы понять модель - допустим, было (26 + 10) папок, в которые складывали файлы по первой букве имени файла, но оказалось, что из миллиона файлов 600_000 начинаются на «а». Я хочу те же 36 корзин (пусть только их будет до 257, чтобы покрыть больше возможных «первых букв» и перекосов. Но поскольку у меня там не папки на самом деле, а слегка иные вещи, мне дорого хранить полный хэш (ну, его в одном месте не похранишь, это типа метка), поэтому я и хочу что-то короткое, желательно до 8 бит (включительно). Но мне почему-то кажется, что если я буду брать CRC32 & 0xFF, где-то перекосит.
Перекосит? Я сейчас почти полностью раскрыл юзкейс, может, будет более другая, более лучшая идея?
у вас тут конечно прикольная беседа про корзинки
только один вопрос - ТС, ты хеш считаешь всего файла?
если да, тогда вообще без разницы, мурмур или crc
ведь ты эти файлы на диске хранишь, значит упираешься в IO
Но что если распределять тупо по алфавиту а размер корзин балансировать динамически? Скажем берем 5 первых букв. Первая корзина aaaaa-ddesd, вторая - ddese-ggtue и тд. Раз в какое то время проверяем размеры и сдвигаем границы если надо.
Пять первых букв могут совпадать скажем у всех значений, потому что это какой-нибудь заголовок. Для этого и нужен хэш. Впрочем мне кажется это велосипед - взять любую хэш функцию и брать остаток от деления значения этой функции на количество корзин. Этого хватит для любого практического применения.
Нет, от имени. Я не храню файлы вообще, я же сказал, что это модель для понимания, потому что настоящая проблема имеет ту же суть, но дольше объяснять.
Тебе ведь нужно не просто хранить эти строки, а еще и делать выборки? Нужен ли тебе range select? Или просто даешь на вход ключ поиска и получаешь номер корзины где она может быть?
Ну так я ложу просто в корзину (когда несбалансированно), а так - считаю хэш и ложу в корзину. Возросшая скорость доставания, конечно, нивелирует время, затраченное на 1-разовый подсчет хэша, но я хочу и это минимизировать.