Получение int-представления строки

Какова длина ваших струн? Если вы не выберете представление типа int, которое длиннее строки, коллизии будут возможны всегда, независимо от того, какое преобразование вы используете. Поэтому, если вы используете 32-битное целое число, вы можете однозначно представлять только строки длиной до 4 байтов.

Разве вы не можете просто начать с хеш-кода, и, если хеш-коды совпадают, провести сравнение символов по символам?

Насколько велики ваши струны? Строки произвольной длины не могут быть сжаты в формат 32/64 бит.

Если вам не нужны коллизии, попробуйте что-нибудь безумное, например SHA-512. Я не могу гарантировать, что столкновений не будет, но я не думаю, что они их еще обнаружили.

Предполагая, что «буквенно-цифровой» означает буквы и цифры, вы можете рассматривать каждую букву / цифру как цифру с основанием 36. К сожалению, большие строки приведут к быстрому росту числа, и вам придется прибегать к большим целым числам, что вряд ли эффективно.

Если при сравнении (т. Е. Поиске определенной строки) ваши строки обычно различаются, хеш может быть вашим лучшим вариантом. Как только вы получите потенциальный результат, вы можете провести сравнение строк, чтобы быть уверенным. Хорошо спроектированный хеш сделает коллизии чрезвычайно редкими.

Казалось бы, хеш MD5 подойдет. Риск хеш-коллизии крайне маловероятен. В зависимости от длины вашей строки хэш, который генерирует int / long, очень быстро столкнется с проблемами максимального значения.

Почему бы вам не сделать что-то вроде 1stChar + (10 x 2ndChar) + 100 x (3rdChar) ...., где вы используете простое целочисленное значение каждого символа, т.е. a = 1, b = 2 и т. д., Или просто целочисленное значение, если это не буква. Это даст уникальное значение для каждой строки, даже для двух строк, которые представляют собой одни и те же буквы в другом порядке.

Конечно, если становится сложнее, если вам нужно беспокоиться о Unicode, а не только о ASCII, и числа могут стать большими, если вам нужно использовать длинную строку.

Стандартные функции сравнения строк Java определенно недостаточно эффективны?

Какова длина струн? Если они очень короткие, то уникальный идентификатор можно сгенерировать, рассматривая символы как цифры в базе 36 (26 + 10), которые образуют число п-digits, где п - длина строки. С другой стороны, если строки достаточно короткие, чтобы позволить это, прямое сравнение в любом случае не будет проблемой.

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

Могут быть другие способы найти такую ​​функцию. Кнут назвал это «довольно забавной… головоломкой» в TAoCP, но он также не дает алгоритма.

В общем, вы даете слишком мало информации, чтобы найти алгоритм, который не требует каким-либо образом исследовать все проблемное пространство. Это всегда означает, что проблема имеет экспоненциальное время выполнения, но может быть решена с помощью эвристики машинного обучения. Я не уверен, целесообразно ли это в вашем случае.

Возможно:

String y = "oiu291981u39u192u3198u389u28u389u";
BigInteger bi = new BigInteger(y, 36);
System.out.println(bi);

Несколько вопросов для начала:

1. Вы проверяли, что простое сравнение строк слишком медленное?
2. Как выглядит сравнение ('ABC' == 'abc' или 'ABC'! = 'Abc')?
3. Сколько строк вам нужно сравнить?
4. Сколько сравнений вам нужно сделать?
5. Как выглядят ваши струны (длина, регистр букв)?

Насколько я помню, String в Java - это объект, и две идентичные строки указывают на один и тот же объект.

Так что, может быть, будет достаточно сравнить объекты (возможно, сравнение строк уже реализовано таким образом).

Если это не помогает, вы можете попробовать использовать реализацию строкового объекта на языке Pascal, когда первый элемент имеет длину, и если ваши строки имеют разную длину, это должно сэкономить некоторое время ЦП.

Если длина вашей строки не ограничена, вы не сможете избежать столкновений.

Существует 4294967296 возможных значений целого числа (2 ^ 32). Если у вас есть строка, содержащая более 4 символов ASCII или более двух символов Юникода, то возможных строковых значений больше, чем возможных целочисленных значений. У вас не может быть уникального целочисленного значения для каждой возможной 5-символьной строки. Длинные значения имеют больше возможных значений, но они предоставляют уникальное значение только для каждой возможной строки из 8 символов ASCII.

Хеш-коды полезны как двухэтапный процесс: сначала проверьте, совпадает ли хеш-код, а затем проверьте всю строку. Для большинства строк, которые не совпадают, вам нужно сделать только первый шаг, и это очень быстро.

String length may vary, but let's say 10 characters for now.

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

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

В конце концов, один буквенно-цифровой символ имеет не менее 36 возможных значений. Если вы включите знаки препинания, нижний регистр и т. д., Вы легко сможете передать 72 возможных значения.

Неконфликтующее число, которое позволяет быстро сравнивать строки, обязательно будет экспоненциально расти с увеличением длины строки.

Таким образом, вы первый должны выбрать самую длинную строку, которую вы собираетесь сравнивать. Предполагая, что это N символов в длину, и предполагая, что вам нужны ТОЛЬКО буквы в верхнем регистре и цифры 0-9, тогда вам нужно иметь целочисленное представление, которое может достигать 36 ^ с.ш.

Для строки длиной 25 (поле общего имени) вам понадобится двоичное число с 130 битами.

Если вы составите 32-битные числа, вам понадобится 4. Затем вы можете сравнить каждое число (четыре целочисленных сравнения не должны занимать времени по сравнению с перемещением строки). Я бы порекомендовал большую библиотеку чисел, но в этом специализированном случае я уверен, что вы можете написать свою собственную и получить лучшую производительность.

Если вы хотите обрабатывать 72 возможных значения на символ (прописные, строчные, цифры, знаки препинания ...) и вам нужно 10 символов, тогда вам понадобится 62 бита - два 32-битных целых числа (или одно 64-битное, если вы используете система, поддерживающая 64-битные вычисления)

Если, однако, вы не можете ограничить числа в строке (т. Е. Может быть любой из 256 букв / цифр / символов и т. д.), И вы не можете определить размер строки, то сравнение строк напрямую выполняется единственный путь, но есть ярлык.

Приведите указатель строки к 32-битному целочисленному массиву без знака и сравните строку по 4 байта за раз (или 64 бита / 8 байтов за раз на 64-битном процессоре). Это означает, что для строки из 100 символов требуется максимум 25 сравнений, чтобы найти, что больше.

Вам может потребоваться переопределить набор символов (и преобразовать строки), чтобы символам с более высоким приоритетом присваивались значения, близкие к 0, а значения с более низким приоритетом - ближе к 255 (или наоборот, в зависимости от того, как вы их сравниваете) .

Удачи!

-Адам

Пока это хэш-функция, будь то String.hashCode (), MD5 или SHA1, столкновение неизбежно, если у вас нет фиксированного ограничения на длину строки. Математически невозможно получить взаимно однозначное отображение бесконечной группы в конечную группу.

Отступая назад, необходимо ли предотвращение столкновений абсолютно?