Как я могу создать уникальный Int из уникальной строки? - PullRequest
14 голосов
/ 28 марта 2011

У меня есть объект со строкой, которая содержит уникальный идентификатор. (например, "ocx7gf" или "67hfs8") Мне нужно предоставить ему реализацию int hascode (), которая, очевидно, будет уникальной.

как я могу преобразовать строку в уникальное int самым простым / быстрым способом?

10x.

Редактировать - ОК. Я уже знаю, что String.hashcode возможен. Но это не рекомендуется в любом месте. На самом деле «если какой-либо другой метод не рекомендуется - должен ли я его использовать или нет, если у меня есть объект в коллекции, и мне нужен хэш-код. я должен соединить это с другой строкой, чтобы сделать это более успешным?

Ответы [ 5 ]

20 голосов
/ 28 марта 2011

Нет, у вас нет необходимости иметь реализацию, которая возвращает уникальное значение, "очевидно", поскольку очевидно, что большинство реализаций будет нарушено.

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

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

Редактировать: При хорошем разбросе битов.

Как указано здесь и в других ответах, быть полностью уникальным невозможно и возможны коллизии хешей. Методы, использующие хэш, знают это и могут с этим справиться, но это оказывает влияние на производительность, поэтому мы хотим, чтобы коллизии были редкими.

Кроме того, хэши, как правило, повторно хэшируются, поэтому наше 32-битное число может в конечном итоге быть уменьшено до, например. один в диапазоне от 0 до 22, и мы хотим максимально хорошее распределение в пределах этого.

Мы также хотим сбалансировать это с тем, что нам не нужно так много времени для вычисления нашего хэша, что это само по себе становится узким местом. Несовершенный балансировочный акт.

Классический пример метода плохого хэширования - один для пары координат X, Y, который выполняет:

return X ^ Y;

Хотя это отлично справляется с возвратом 2 ^ 32 возможных значений из 4 ^ 32 возможных входов, в реальном мире довольно часто иметь наборы координат, где X и Y равны ({0, 0} , {1, 1}, {2, 2} и т. Д.), Которые все хэшируются на ноль, или совпадающие пары ({2,3} и {3, 2}), которые будут хэшироваться на одно и то же число. Скорее всего, нас лучше обслуживают:

return ((X << 16) | (x >> 16)) ^ Y;

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

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

Следовательно, если я, например, знал, что данная строка всегда будет состоять из 6 символов без учета регистра в диапазоне [az] или [0-9] (что кажется вашим, но это не ясно из ваш вопрос, что он делает) тогда я мог бы использовать алгоритм, который присваивает значение от 0 до 35 (36 возможных значений для каждого символа) для каждого символа, а затем пройтись по строке, каждый раз умножая текущее значение на 36 и добавляя значение следующего символа.

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

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

Одно из преимуществ, которое у вас есть, состоит в том, что, поскольку он сам по себе является идентификатором, то, по-видимому, никакой другой неравный объект не имеет такого идентификатора, и, следовательно, никакие другие свойства проверять не нужно. Это не всегда верно.

11 голосов
/ 28 марта 2011

Вы не можете получить уникальное целое число из строки неограниченной длины.Существует 4 миллиарда (2 ^ 32) уникальных целых чисел, но почти бесконечное количество уникальных строк.

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

РЕДАКТИРОВАТЬ

Ваш отредактированный вопрос говорит, что String.hashCode () не рекомендуется.Это не так, рекомендуется, если у вас нет особых причин не использовать его.Если у вас есть особая причина, просьба сообщить подробности.

5 голосов
/ 28 марта 2011

Похоже, у вас там есть номер base-36 (az + 0-9).Почему бы не преобразовать его в int, используя Integer.parseInt(s, 36)?Очевидно, что если слишком много уникальных идентификаторов, он не поместится в int, но в этом случае вам не повезло с уникальными целыми числами, и вам нужно будет использовать String.hashCode(), что делает все возможное длябыть близким к уникальному.

3 голосов
/ 28 марта 2011

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

Допустим, у вас есть 32-разрядное целое число и набор из 64 символов для ваших строк. Это означает шесть битов на символ. Это позволит вам хранить пять символов в целое число. Более того, и оно не подходит.

0 голосов
/ 09 октября 2015

Один из способов сделать это - присвоить каждой букве значение, и каждому месту строки соответствует ее кратность, т.е. a = 1, b = 2 и т. Д., Тогда все в первой цифре (читается слева направо) будетумножить на простое число, следующее на следующее простое число и так далее, чтобы конечная цифра была умножена на простое число, большее, чем число возможных подмножеств в этой цифре (26 + 1 для пробела или 52 + 1 с капитолиямии так далее для других поддерживаемых персонажей).Если число сопоставляется с первыми цифрами (крайним левым символом), любое число, которое вы генерируете из уникальной строки, сопоставляющей 1 или 6, какой бы ни была первая буква, дает уникальное значение.

Собака может быть 30,3 (15), 101 (7) или 782, в то время как Бог 33,3 (15), 101 (4) или 482. Что важнее, чем генерируемые уникальные строки, они могут быть полезныв поколении, если исходная цифра сохраняется, например, 30 (782) будет уникальным для некоторых 12 (782) с целью различения подобных строк, если вам когда-либо удавалось использовать уникальные возможности.Собака всегда будет собакой, но никогда не будет кошкой или мышью.

...