Отображение строк в целые числа

Question

Какой самый простой способ в Java для сопоставления строк (Java String) с (положительными) целыми числами (Java int), чтобы

• одинаковые строки отображаются на равные целые числа, а
• разные строки отображаются на разные целые числа?

Итак, аналогично hashCode(), но разные строки требуются для получения разных целых чисел. Так что, в некотором смысле, это был бы hasCode () без возможности коллизии.

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

Answer 1

Взгляните на идеальное хеширование .

Answer 2

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

Решение возможно только тогда, когда вы ограничиваете количество используемых строк. Тогда вы можете использовать простой счетчик. Вот простая реализация, в которой могут использоваться все (2 ^ 32 = 4294967296 разных строк). Не берите в голову, что это использует много памяти.

import java.util.HashMap;
import java.util.Map;

public class StringToInt {

    private Map<String, Integer> map;

    private int counter = Integer.MIN_VALUE;

    public StringToInt() {
        map = new HashMap<String, Integer>();
    }

    public int toInt(String s) {
        Integer i = map.get(s);
        if (i == null) {
            map.put(s, counter);
            i = counter;
            ++counter;
        }
        return i;
    }
}

Answer 3

В большинстве реализаций типа hashcode () коллизии принимаются как неизбежные и проверяются на.

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

Помимо этого, существуют криптографические хеш-функции, такие как MD5 и SHA, где коллизии крайне маловероятны (хотя с большими усилиями можно их форсировать). У Криптографической Архитектуры Java есть реализации их. Эти методы могут быть быстрее, чем хорошая реализация вашего решения для очень больших наборов. Они также будут выполняться в постоянное время и давать один и тот же код для одной и той же строки, независимо от того, в каком порядке добавляются строки. Кроме того, не требуется хранить каждую строку. Результаты хеширования в криптографии могут рассматриваться как целые числа, но они не вписываются в Java-int - вы можете использовать BigInteger, чтобы сохранить их, как предложено в другом ответе.

Кстати, если вас отталкивает мысль о том, что коллизия является «крайне маловероятной», вероятно, аналогичная вероятность того, что бит случайно перевернется в памяти вашего компьютера или на жестком диске, приведет к тому, что любая программа будет вести себя не так, как вы ожидаете :-)

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

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

Answer 4

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

Answer 5

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

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

В более общем случае вы можете создать высокоуровневый подкласс Object, ввести там метод "integerize" и расширить каждый отдельный класс от этого. Я думаю, однако, что эта дорога ведет к слезам.

Answer 6

Поскольку строки в java имеют неограниченную длину и каждый символ имеет 16 бит, а целые имеют 32 бита, вы можете создать уникальное сопоставление строк и их только в том случае, если строки содержат до двух символов. Но вы можете использовать BigInteger для создания уникального сопоставления, например:

String s = "my string";
BigInteger bi = new BigInteger(s.getBytes());

Обратное отображение:

String str = new String(bi.toByteArray());

Answer 7

Как вы отметили, хеш-таблица, которая разрешает коллизии, является стандартным решением. Вы также можете использовать поиск в стиле Bentley / Sedgewick, который во многих приложениях быстрее, чем хеширование.

Если вы замените «уникальный указатель» на «уникальное целое число», вы увидите решение Дейва Хансона для этой проблемы в C . Это довольно хорошая абстракция, потому что

• Указатели все еще можно использовать как строки C.

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

Если Java предлагает тест для идентификации объекта на String объектах, тогда вы можете играть в ту же игру там.

Answer 8

Можно ли использовать карту, чтобы указать, каким строкам вы уже присвоили целые числа? Это своего рода решение «database-y», где вы присваиваете каждой строке «первичный ключ» из последовательности по мере ее появления. Затем вы помещаете пару String и Integer в карту, чтобы вы могли снова ее найти. И если вам нужна строка для данного целого числа, вы также можете поместить эту пару в карту.

Answer 9

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

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

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

Интересный вопрос.