алгоритм хеширования для строк

Question

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

И это привело к большему вопросу .. Как языковые библиотеки (например, Java) реализуют структуры данных, такие как hashmap, которые генерируют уникальные значения хэша в случае строк?

Я хочу знать математическую конструкцию, связанную с реализацией такого алгоритма.

Answer 1

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

Нет такой функции. Пространство строк бесконечно, но целевое пространство конечно (скажем, вы используете 32-битные целые числа). Вы не можете инъективно отображать бесконечное пространство в конечное пространство; должны быть столкновения.

Как библиотеки языков (например, Java) реализуют структуры данных, такие как hashmap, которые генерируют уникальные значения хэша в случае строк?

Их нет; не существует уникальной функции хэширования для строк по приведенному выше.

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

У вас есть правильная идея. Просто используйте словарь, сопоставляющий string с по номеру int. Например, в C# мы использовали бы Dictionary<string, int>.Нечто похожее на это существует на большинстве современных языков. Пусть язык/структура справляется с проблемой столкновений, а что не для вас, и просто сосредоточьтесь на выражении своей идеи в рамках этого языка/структуры.

Answer 2

Вы не можете быть уверены на 100%, хэш по определению может иметь коллизии.

Вы можете увидеть на grepcode, как String хэшируется в java. И в основном HashMap (и другие структуры, основанные на хеше) каждый раз используют метод hashCode().

Итак, если вы хотите подсчитать количество итераций определенного слова, вы должны использовать Map<String, Integer> (в java) и подсчитывать оттуда.

Например:

Map<String, Integer> words = new HashMap<String, Integer>(); 
String word = "lol"; 

Integer count = words.get(word); 
if(count == null){ 
    count = 0; 
} 
words.put(word, count + 1); 

Answer 3

Вы не можете иметь алгоритм хэширования, который гарантирует уникальность; это pigeonhole principle. Почему бы не использовать двоичное дерево?

Answer 4

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

Для подробного объяснения этого, пожалуйста, см. «Are Hash Codes Unique?» от Tom Archer.

Answer 5

В Java, хэш-код для String реализуется следующим образом:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

Используя Int арифметику, где s [I] является г-й символ строки, п есть длина строки, и^указывает на возведение в степень. (Хэш-значение пустой строки равно нуль.)

Источник: JavaDoc for java.lang.String

Вы могли бы рассмотреть возможность использования аналогичного алгоритма, чтобы сделать ваше Hashcode пуленепробиваемым (в основном).

Answer 6

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

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

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

сторона примечание: если я не ошибаюсь, Java Hashtable не использует открытую адресацию. Всякий раз, когда обнаружено столкновение, элемент помещается в ту же, уже занятую ячейку через список. Так что это, безусловно, противоположное тому, что вы думаете .. implmentations не пытается гарантировать уникальность, они вместо того, чтобы выбрать стратегию разрешения коллизий хороших, что сводит к минимуму некоторых аспектов

Answer 7

Исходники стоит тысяч слов ...

String.java, посмотрите на хэш-код() метод: http://www.google.com/codesearch/p?hl=zh-TW#ih5hvYJNSIA/src/share/classes/java/lang/String.java&q=String.java%20hashcode&sa=N&cd=1&ct=rc

HashMap.java, смотреть на положить() метод: http://www.google.com/codesearch/p?hl=zh-TW#ih5hvYJNSIA/src/share/classes/java/util/HashMap.java&q=hashMap.java%20%22V%20put%22&sa=N&cd=1&ct=rc

Answer 8

Я думаю, что вы ищете Substring Index или Поиск по строкам. Я что-то упускаю?