Уникальное свойство строк для построения эффективного хэш-таблицы

Question

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

Answer 1

Стандартные строки C++ являются по существу векторами символов. Таким образом, сравнивать строки означает сравнивать их символ за символом с самого начала. Я не уверен, что вы подразумеваете под "уникальным свойством", но для вашего сценария должен подойти любой алгоритм хеширования. Если я правильно понимаю ваш сценарий использования, вы можете использовать std::set или std::map. Таким образом, вам не придется заботиться о том, было ли слово уже добавлено или нет.

Answer 2

Самый простой алгоритм, который вычисляет ключ хеш-функции для строки в стиле C с нулевым символом в конце, заключается в следующем:

UINT HashKey(const char* key) const
{
    UINT nHash = 0;
    while (*key)
        nHash = (nHash<<5) + nHash + *key++;
    return nHash;
}

Answer 3

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

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

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