Равномерный, быстрый, короткий (до 64 бит), криптографически несекьюрный хэш

via http://burtleburtle.net/bob/hash/doobs.html, на хабре глянуть, ну и посковики вроде не отменили

murmurhash

Рискну назваться экспертом и дать ссылки по делу.

Под определение подходит CityHash от Google, для начала см. http://habrahabr.ru/post/117360/. По многим сценариям использования и для многих актуальных архитектур/семейств процессоров это чемпион по скорости, но не на коротких данных.

Если хочется/требуется заморочиться больше, то можно выбрать более быстрые/оптимальные варианты:

• для коротких данных.
• менее устойчивые к некоторым видам «атак», т.е. выдающие сильную (относительно) корреляцию между hash-значениями при определенных (хитрожопых) различиях в исходных данных.
• для больших данных с использованием MMX/SSE/AVX и прочих SIMD.

Ну и раз такая гулянка, то не могу не показать свой «велосипед» https://gist.github.com/leo-yuriev/7bf20f02f3ad76c35f0d. На коротких данных он выгоднее CityHash, а на длинных медленнее, но чуть лучше с коллизиями и корреляциями.

Из совсем простого, но эффективного см. rot13, ly и rs на http://vak.ru/doku.php/proj/hash/efficiency

А для тестирования, пожалуй https://code.google.com/p/smhasher/

для коротких и средних строк: h = h * 101 + *s++;
для int8/16/32/64 - простое умножение на золотое сечение интервала (дает практически идеальное распределение для подряд идущих значений)

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

А ещё есть xxhash.

rot13 что, равномерный?

пофиг на коллизии, мне нужно оооочень неравномерно распределенные строки (пусть, например, 2^20 их) раскидать по 64 (например) корзинам так, чтобы в каждой корзине было бы их примерно поровну. Это частая операция. Изначально корзин может быть около 30, в 10 из них - по 100 строк, в 10 - по 10000, а все остальные - в оставшихся 10, например. Длина строк произвольная, поэтому сам адлер мне не подходит, потому что он там хромает.

Остальные посмотрю поближе.

у этого есть называние? хочу знать характеристики

Я пока СРС32 юзаю, вроде норм, но мне по сути-то и 8 бит хватило бы с головой. На самом деле, даже 6 хватит.

Почему никто ещё корректику от лучших умов страны не предложил? CoReCTica/CRCT/Корректика

пофиг на коллизии, мне нужно оооочень неравномерно распределенные строки (пусть, например, 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, где-то перекосит.

Перекосит? Я сейчас почти полностью раскрыл юзкейс, может, будет более другая, более лучшая идея?

h = h * 101 + *s++; это Paul Larson' hash
умножение за золотую середину - чисто математика

мне дорого хранить полный хэш (ну, его в одном месте не похранишь, это типа метка

Ну так храните индекс корзины, а не полный хеш. Или не храните ничего, а вычисляйте хеш каждый раз.

Не перекосит, и CRC подойдет (хотя это не будет оптимальным вариантом).

у вас тут конечно прикольная беседа про корзинки
только один вопрос - ТС, ты хеш считаешь всего файла?
если да, тогда вообще без разницы, мурмур или crc
ведь ты эти файлы на диске хранишь, значит упираешься в IO

1, 2, 3, ... N

Я сейчас возможно хрень скажу. Даже наверняка.

Но что если распределять тупо по алфавиту а размер корзин балансировать динамически? Скажем берем 5 первых букв. Первая корзина aaaaa-ddesd, вторая - ddese-ggtue и тд. Раз в какое то время проверяем размеры и сдвигаем границы если надо.

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

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

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

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

Тогда берем 5 букв с середины. От length/2-2 до length/2+2

Я сейчас почти полностью раскрыл юзкейс

Нет, не полностью.

Тебе ведь нужно не просто хранить эти строки, а еще и делать выборки? Нужен ли тебе range select? Или просто даешь на вход ключ поиска и получаешь номер корзины где она может быть?

Влияние на что? Какое именно влияние хочешь исключить? Ну удовлетворяет равномерность распределения? Скорость?

Для чего разлаживаешь по корзинам? Поиск?

DJB2? Или недостаточно однородный?

а от opt, mnt, usr и т.д. ты как будешь 5 букв брать?

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

хз, почитал - вроде норм.

О, ты вернулся. Ты предупреждай, когда исчезать собираешься. ♥

кто здесь?!