Приветствую.
Сравниваются много строк (миллионы и миллиарды). Строки не сортированы, размер прыгает всегда. Прежде чем сравнить строку со строкой сравнивается размер. Далее есть свободный байт (8 бит), который хочется использовать как некую контрольную сумму или наподобие хеш-функции, что-бы ускорить процесс сравнения. Посоветуйте пожалуйста что-нибудь?
Пробовал CRC8 — очень много неверных попаданий, когда строки разные а CRC одинаков. Пока что остановился на простой сумме всех байт в строке, но может что-то есть лучше?
8 бит это всего лишь 256 различных значений. Конечно же, когда вы отображаете миллионы в 256, случается много коллизий, это очевидно. Неважно, насколько хорошую функцию вы возьмете, различных хешей все равно будет только 256.
Интересно, если у какой-либо функции «случайность» лучше, чем у криптографической, чем это объясняется?
Имхо, если у криптографической функции найдена «неслучайность» где-либо, это уже уязвимость.
Она используется в криптографии. Например в браузере можно посмотреть md5 fingerprint какого-нибудь SSL сертификата. Это криптографическая хэш-функция и она не на столько слаба и не на столько уязвима, чтобы вызвать проблемы для применения ТС.
Если для нужд ТС она слишком медлена, может использовать её для сравнения с другими функциями и их случайности.
вам в любом случае нужно использовать этот байт как дополнительную проверку. то есть если длина совпала, CRC8 совпали, только тогда проверять побитно. это даст выигрышь, если у вас совпадений мало по сравнению с общим объёмом и строки часто совпадают в начале. Как вариант, попробуйти сравнивать побитно «задом-на-перед», если первый символ совпал.
Если говорить о английском тексте (как в прочем и о любой текстовой информации) — то CRC не эффективен (особенно для коротких строк). Как пример: простая хэш функция sum( str[i] + str[i+1] << 4) для 0 и четных i, имеет на порядок более равномерное распределение на коротких строках.
Но вообще посмотрите http://www.cse.yorku.ca/~oz/hash.html. Здесь есть несколько толковых функций — оцените по своим данным, какая из них лучше.
1. CRC8
2. Полиномиальный хеш (таких неплохо попробовать несколько вариантов — с разными нечетными множителями).
3. Хеш, основанный на операции циклического сдвига (тут вариантов немного — сдвигать следует на 3 или 5, можно использовать сложение или xor).
Все эти варианты можно проверить последовательно и выбрать наилучший.
CRC8 дает достаточно хорошее распределение при хорошей скорости работы.
Если количество коллизий неприемлемо — то увеличивайте разрядность хеша. Другими алгоритмами заметно уменьшить количество коллизий не выйдет.
Нет. CRC всегда в принципе дают плохое распределение при небольших размерах данных к примеру коротких строк. Вы не найдете ни одну серьёзную библиотеку с использованием CRC8 для хэширования ключей. Хотя часто используются hash функции с количеством значений <256.
CRC8 — специально пропустил словарь английского языка через него. В результате количество слов с CRC8 = 111 в 7 раз больше чем с CRC8 = 11.
Средний
