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

Question

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

Для подробного объяснения этого пожалуйстасм. " Уникальны ли хэш-коды? " Тома Арчера.

Answer 5

Вы не можете быть уверены на 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 6

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

Answer 7

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

String.java, посмотрите на метод hashCode (): 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, посмотрите на метод put () : 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

В Java hashCode для String реализован следующим образом:

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

Используя int арифметику, где s [i] - i-й символ строки, n - длина строки, а ^ - возведение в степень (Значение хеша пустой строки равно нулю.)

Источник: JavaDoc для java.lang.String

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