Хеш-таблица позволяет эффективно вставлять и извлекать данные (обычно в постоянном / O (1)) времени.Для этого мы используем очень большой массив для хранения целевых значений и хеш-функцию, которая обычно отображает целевые значения в хеш-значения, которые являются ничем иным, как действительными индексами в этом большом массиве.Хеш-функция, которая идеально хэширует значения, которые должны быть сохранены в уникальном ключе (или индексе в таблице), называется идеальной хеш-функцией.Но на практике для хранения таких значений, для которых нет известного способа получения уникальных хеш-значений (индексов в таблице), мы обычно используем хеш-функцию, которая может сопоставить каждое значение с конкретным индексом, чтобы коллизия могла быть минимальной.Здесь столкновение означает, что два или более элементов, которые должны быть сохранены в хеш-таблице, соответствуют одному и тому же хеш-значению.
Теперь перейдем к исходным вопросам, а именно: «Разработайте хеш-таблицу. Вы можете использовать любую структуру данных, какую пожелаете. Я хотел бы посмотреть, как вы реализуете время поиска O (1)».».В заключение он сказал, что это больше похоже на моделирование хеш-таблицы с помощью другой структуры данных. "
Просмотр возможен ровно за O (1) раз, в случае, если мы можем разработать идеальную хеш-функцию.структура все еще является массивом. Но это зависит от значений, которые будут сохранены, можем ли мы разработать идеальную хеш-функцию или нет. Например, рассмотрим строки в английском алфавите. Так как не существует известной хеш-функции, которая могла бы сопоставить каждое действительное английское слово суникальное значение типа int (32 бита) (или long long int 64 бита), поэтому всегда будут возникать коллизии. Чтобы справиться с коллизиями, мы можем использовать отдельный метод цепочки обработки коллизий, в котором каждый слот хеш-таблицы хранит указатель на связанныйсписок, который фактически хранит все хеширование элемента в этом конкретном слоте или индексе. Например, рассмотрим хеш-функцию, которая рассматривает каждую строку английского алфавита как число на основе 26 (потому что в английском алфавите 26 символов), это можно закодировать как:
unsigned int hash(const std::string& word)
{
std::transform(word.begin(), word.end(), word.begin(), ::tolower);
unsigned int key=0;
for(int i=0;i<word.length();++i)
{
key = (key<<4) + (key<<3)+(key<<2) + word[i];
key = key% tableSize;
}
return key;
}
Где tableSizeэто правильно выбранное простое число, которое больше, чем общее количество слов английского языка, предназначенных для сохранения в хеш-таблице.
Ниже приведены результаты со словарем размера 144554 и таблицей размера = 144563:
[Элементы, отображаемые в одну ячейку -> Количество таких слотов в хеш-таблице] =======>
[ 0 --> 53278 ]
[1 --> 52962 ]
[2 --> 26833 ]
[3 --> 8653 ]
[4 --> 2313 ]
[5 --> 437 ]
[6 --> 78 ]
[7 --> 9 ]
В этом случае для поиска элементов, которые были отображеныдля ячеек, содержащих только один элемент, поиск будет O (1), но в случае, если он сопоставляется с ячейкой, которая содержит более 1 элементов, мы должны выполнить итерацию по этому связанному списку, который может содержать от 2 до 7 узлов, а затемсможет узнать этот элемент.Так что это не постоянно в этом случае.
Таким образом, зависит только от наличия совершенной хеш-функции, можем ли мы выполнить поиск в ограничении O (1).В противном случае это будет не совсем O (1), но очень близко к нему.