Pull to refresh

Семейство хеш-функций CityHash от Google

Algorithms *
Google выложил под свободной лицензией новое семейство хеш-функций CityHash для строк. Пока представлены функции CityHash64 и CityHash128 для получения 64- и 128-битных хеш-кодов.

Как сообщают разработчики, в реальных условиях CityHash64 превосходит по скорости аналогичные хеш-функции как минимум на 30%.

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

CityHash128 оптимизирован для строк хотя бы в несколько сотен байт и при достаточной длине строк обгоняет по скорости CityHash64. На малых строках он медленнее. Внутри Google его применяют в тех случаях, когда нужно минимизировать количество коллизий.

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

Традиционно главное преимущество разработок Google — производительность. И здесь тоже это поставили первым приоритетом. Хеш-функция CityHash сделана на основе известных разработок, а основным образцом стала MurmurHash, созданная Остином Апплеби в 2008 году. Это простая и быстрая хэш-функция общего назначения, не являющаяся криптографически безопасной. Все её варианты находятся в свободном пользовании.

Главное достоинство подхода Google — большинство шагов содержат как минимум два независимых математических действия. Как выяснилось, современные CPU лучше справляются с кодом такого рода.

Обратная сторона медали — код становится сложнее, чем в других популярных хеш-функциях. Но разработчики решили оптимизировать его для производительности, а не для простоты, и даже добавили специальный варианты исполнения функции для коротких строк входных данных.

Странно, что разработчики не показали конкретных бенчмарков, если заявляют скорость главным преимуществом своей хеш-функции. Вот производительность некоторых популярных хеш-функций с сайта Остина Апплеби (он же разработал программу SMHasher для тестирования скорости хеш-функций):

OneAtATime - 354.163715 mb/sec
FNV - 443.668038 mb/sec
SuperFastHash - 985.335173 mb/sec
lookup3 - 988.080652 mb/sec
MurmurHash 1.0 - 1363.293480 mb/sec
MurmurHash 2.0 - 2056.885653 mb/sec
Tags:
Hubs:
Total votes 45: ↑41 and ↓4 +37
Views 11K
Comments Comments 15