Google выпустила новое семейство хэш-функций CityHash для строк под бесплатной лицензией.
Представленные на данный момент функции CityHash64 и CityHash128 для получения 64- и 128-битных хеш-кодов.
Как отчет разработчиков , в реальных условиях CityHash64 превосходит аналогичные хэш-функции как минимум на 30%.
Из-за своей простоты эти хеш-функции не подходят для криптографических приложений, но теоретически идеально подходят для хеш-таблиц.
Правда, код пока сырой и недостаточно протестированный (см.
предупреждение ) и нуждается в некотором улучшении.
CityHash128 оптимизирован для строк длиной не менее нескольких сотен байт и при достаточной длине строки превосходит CityHash64. На небольших линиях это происходит медленнее.
Внутри Google он используется в тех случаях, когда необходимо минимизировать количество коллизий.
Хотя они пытались оптимизировать функции процессоров, найденных в дата-центрах Google, оказалось, что они очень быстро работают на большинстве ПК и ноутбуков.
Поддерживает 64-битные регистры, параллелизм на уровне инструкций и быстрый доступ к невыровненным данным в памяти.
Традиционно главным преимуществом разработок Google является производительность.
И здесь это тоже было поставлено на первое место.
Хеш-функция CityHash основана на известных разработках, и основным примером является МурмурХэш , созданная Остином Эпплби в 2008 году.
Это простая и быстрая хеш-функция общего назначения, не являющаяся криптографически безопасной.
Все его варианты находятся в свободном доступе.
Основное преимущество подхода Google заключается в том, что большинство шагов содержат как минимум две независимые математические операции.
Как оказалось, современные процессоры лучше справляются с таким кодом.
Обратная сторона медали заключается в том, что код становится сложнее, чем у других популярных хэш-функций.
Но разработчики решили оптимизировать его ради производительности, а не простоты, и даже добавили специальные возможности выполнения функции для коротких строк входных данных.
Странно, что разработчики не показали конкретных тестов, если они заявляют скорость как главное преимущество своей хэш-функции.
Вот исполнение некоторых популярных хэш-функций с сайта Остина Эпплби (он же разработал программу 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Теги: #хеш-функция #хеш-таблица #хеширование #MurmurHash #CityHash #Алгоритмы
-
Автоматизация: Залог Успеха
19 Oct, 24 -
Фотогалерея: 40 Лет Apple
19 Oct, 24 -
Набор Доменных Имен В Другой Раскладке
19 Oct, 24
