Компания Google открыла код hash-функций CityHash

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

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.