Компания Google открыла код hash-функций CityHash12.04.2011 16:21

Разработчики из компании Google представили реализацию 64- и 128-разрядных hash-функций CityHash, позволяющих получить отпечаток фиксированной длины, идентифицирующий больший по размеру набор входящих данных. Код функций написан на языке C++, распространяется в рамках лицензии MIT и разработан в стиле "всё ради высокой производительности".

Код CityHash был написан для реализации высокопроизводительных хэш-таблиц, используемых для организации хранения баз ключ-значение. Функция CityHash128 оптимизирована для строк размером в несколько сотен байт. Оптимизация кода, использование 64-разрядных регистров, обеспечение параллелизма выполнения на уровне инструкций и быстрый доступ к невыровненным областям памяти позволили добиться значительного превосходства в производительности по сравнению с другими реализациями хэшей. Ценой производительности является достаточно сильная запутанность кода.

По сравнению с прошлыми реализациями высокопроизводительных хэшей от компании Google, CityHash демонстрирует в реальных условиях ускорение как минимум на 30%. В некоторых ситуациях наблюдается увеличение производительности до двух раз. Утверждается, что представленные функции не подходят для использования в криптографии, так как алгоритм работы CityHash подразумевает смешивание битов входящего потока, что допускает появление коллизий (вероятность коллизий крайне низка, что подтверждено накопленной статитстикой).