генерация уникального целого / длинного хеш-ключа по строкам для более быстрого сравнения

Общие криптографические хеш-функции, такие как SHA-1, выводят 20 байтов (160 бит). Какова длина ваших биржевых символов? Если мы говорим о тикерных символах , таких как «WMT» (Walmart), «KO» (Coca-Cola) и т. Д., То кажется, что они имеют длину всего пару байтов - так что это должно быть быстрее сравнивать их напрямую вместо того, чтобы иметь дело с 20-байтовым хешем. Вы упоминаете о коллизиях хеширования - я бы не стал о них беспокоиться, особенно если входные данные намного меньше, чем хеш-выход.

Вы можете преобразовать байты в int или ] long в зависимости от языка программирования и платформы, а затем выполните сравнение этих «чисел» в одной инструкции ЦП. (Я не

Если вы используете String.intern () или свой собственный пул строк, вы можете использовать == вместо .equals () - я сделал это в аналогичном критически важном для производительности коде, и это сильно изменило ситуацию. Строка по умолчанию уже имеет hashCode (), которая работает довольно эффективно.

Я только что понял, что это не вопрос Java, но применимо то же самое. Да, хеширование и последующая проверка личности могут сэкономить время.

Вам следует подумать об использовании Идеальной хеш-функции , я думаю, она соответствует вашим требованиям

Если вы получаете 4-буквенные символы тикера, каждая буква должна быть представлена ​​как один байт. Упакуйте все 4 вместе в 32-битное int, и вуаля, у вас есть "хэш". Теперь вы можете сравнить это с эталоном, используя одну машинную инструкцию.

Если бы вы не использовали Java, то есть.

Я бы действительно не советовал использовать Java для чего-либо критичного к скорости, особенно для тысяч строк сравнений в миллисекунду.

edit: Если вы хотите использовать 64-битный код, вы можете упаковать до 8 букв в длинное целое число, а затем сравнить в 1 инструкции.

Вы можете сгенерировать хеш, рассматривая строку как число Base-27 ( предполагая, что символы содержат только буквы). Это создаст уникальность, которую вы ищете. Например:

(без буквы) = 0, A = 1, B = 2, ... 27 ¹ ) + (1 x 27 ⁰ ) = 757

BBB = (2 x 27 ² ) + (2 x 27 ¹ ) + (2 x 27 ⁰ ) = 1514

GOOG = (7 x 27 ³ ) + (15 x 27 ² ) + (15 x 27 ¹ ) + (7 x 27 ⁰ ) = 149128

Это будет нормально работать до 6 символов в 32-битном int .

Вам нужна быстрая хеш-функция с хорошей дискриминационной способностью. Для каждой строки вычислите связанную хеш-функцию и сохраните ее вместе со строкой. Затем для сравнения код: если (Хэш (s1) == Хеш (s2) && s1 == s2) затем { ... } Фактическое сравнение строк не произойдет, если хеши не совпадут, что на практике только тогда, когда строки совпадают.

Некоторые люди посоветуют вам реализовать идеальный хеш. Ты можешь только делать что когда набор строк, которые вы хотите хэшировать, имеет ограниченный размер, обычно всего 10-1000. Вы не можете сделать это для произвольно большого словаря строк. Поскольку вы не можете этого сделать, вам фактически нужно сравнить строки, чтобы определить равенство.

Криптографические хэши обладают большой способностью распознавания, но не предназначены быть быстрым. Что обычно очень быстрое и имеет хорошую дискриминацию power - это функции CRC, и на большинстве языков легко найти библиотеки которые вычисляют их быстро (используя технику поиска в таблице по байтам). Мы используем CRC-32, и он очень эффективен для этого (в основном 1 шанс из 2 ^ 32, что произойдет конфликт хэша, когда строки не совпадают). Вы можете использовать CRC-64, но дополнительная сила дискриминации он не добавляет реальной функциональности.

Edit: Better comments than my own were thrown on (and earlier), making mine redundant at best.

Я поддерживаю приведенное выше предложение о структуре Trie как лучший подход для этого случая. Вычислительно эквивалентен идеальному хешу, но концептуально намного красивее. Предполагается, что ваши символы имеют ограниченную длину.

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

Но не надо ' • Напишите свою собственную хеш-функцию, используйте ту, что есть.

Да, и генерацию хеша нужно делать только один раз, я думаю. Потому что у вас есть таблица поиска того, что вы отслеживаете, а хеш-таблица должна изменяться только тогда, когда вы добавляете новую «интересную» вещь для сканирования.

FWIW, в последнем проекте с большим объемом данных, над которым я работал, мы обнаружили, что фильтрация, агрегирование и предварительная классификация данных с использованием некоторого сильно настроенного кода C были ключевыми. Все наши каналы поступали в этот препроцессор, и он позаботился о простой очистке данных перед передачей основной части данных в нашу систему на основе Java для обработки. В основном препроцессор делал именно то, о чем вы просите: выявлял интересующие записи, проверял их полноту и удалял дубли и пустые записи. В периоды пиковой нагрузки препроцессор может удалить до 20% из 8 миллионов записей, которые мы получаем в час (вероятно, не совсем тот объем, который, как я полагаю, вы получаете из каналов фондовой биржи). Нашей оригинальной версии Java посчастливилось получить вдвое меньше (но, по крайней мере, она была «элегантной»!)