Хеш-таблица (Hash-Table). Реализация C++.

Хеш-таблица-динамическая структура данных, которая реализует интерфейс ассоциативного массива, то есть позволяет хранить пару <Ключ, Значение> и выполнять 3 операции: добавление новой пары, операции поиска, операции удаления по ключу.

Чтобы понять, что такое хеш-таблица, вспомним массив. Мы можем получить доступ к элементу с помощью его ключа, причем может быть такой случай, что есть ячейки содержащие элементы и есть не содержащие.
Представим ситуацию, что нам нужно найти элемент, например, массив состоит из строк большой длины. Нам придется нашу подстроку поиска сравнивать со всеми элементами массива, что неудобно, так как поиск займет O(n). НО мы хотим O(1). Решение есть! Использовать специальную хеш функцию, для того, чтобы мы имели доступ по индексу.

Пример:

• Каждой строке соответствует индекс равный (n=длина строки-1). Например: строка "Alex" индекс 3. Вот так можно записать строки. 
• Хеш функция у нас будет: Hash_Func(string)=Strlen(string) (то есть вычисление длины).
• Доступ к массиву мы получаем вот так: Mas[Hash_Func(string)].

length        value
------------------------
 2           "joe"
 3           "Alex"
 4           "Pavel"
Но! вот в чем беда! Если мы хотим вставить еще 1 имя, например "Petr", то этому имени будет соответствовать ОДИН И ТОТ ЖЕ КЛЮЧ 3, который является индексом 3. Это называется Коллизией, когда один и тот же ключ указывает на несколько значений ключа.
Иллюстрация коллизии (2 ключа относятся к одной и той же ячейки массива, ключи k2 и k3):

Разрешение случаев с коллизией является важной задачей Computer Science. Решениями проблемы являются:

1. Метод цепочек (открытое хеширование).
2. Метод открытой адресации (закрытое хеширование).

1. Идея метода цепочек состоит в том, что все элементы множества, которые относятся к одному и тому же ключу входят в связный список.

Итак! В этом примере, в i позициях содержится указатель на голову списка. Т.е. в массиве с ячейками (1,3,4); в остальных других хранится null (0,2,5);

Возвращаясь к нашему примеру с именами, переделаем его в соответствии с новым методом:
length        value
------------------------
 2           *head1 ["Joe"->"Rex"->Null]
 3           *head2 ["Alex"->"Petr"->"Oleg"->Null]
 4           *head3 ["Pavel"->Null]
В этом примере 0,1,5 элементы указатели равны Null
Процедура вставки происходит так: Вычисляется хеш-функция от строки и вставляется в голову списка (push_front) на определенный индекс равный значению функции.
Вставка происходит за O(1).
Поиск или удаление элемента зависит от длины списка, худший случай: O(n) - когда, все элементы хешируются в одну и ту же ячейку. Если функция распределяем n ключей по m ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка k=n/m ключей. Это число называется коэффициентом заполнения хеш-таблицы. В этом случае время поиска: O(1+k), это показано в книжке Кормана, могу скинуть ссылку на нее, если интересно.
Добавлю, что в случае, когда коэффициент заполнения будет слишком велик, надо будет увеличить размер массива и, возможно, перестроить таблицу.

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

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

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

Общий прием состоит в следующем: если хеш-функция вырабатывает позицию для первого кандидата i = Hash_Func(key) Mod (capacity), то последующие позиции определяются как i + increment, i +2 * increment, i +3 * increment и так далее, все по модулю capacity. Величина increment вычисляется как: 
Hash_Func(key) Mod (capacity -1)

Пример:

i,i1,i2 ячейки заняты, i=2, i1=4, i2=6, i3=8, capacity=11
Последующие index=i+increment (increment = 2 Mod 10 = 2)

Хеш-таблицы имеют очень большое практическое применение:

• Для поиска информации о водители лишь по его номеру в водительском удостоверении.

• Таблица символов компилятора. Хеширование является методом ускорения поиска. Компилятор встре­чает некоторую лексему и пытается найти ее в своей базе данных или таб­лице символических имен. Таблица символических имен современного компилятора в MS Windows может содержать несколько тысяч или десятков тысяч лексем. Для ускорения поиска был придуман следующий прием. Компилятор, найдя лексему в тексте программы, определяет ее хеш-ключ. Наша лексема — это просто слово, состоящее из последовательности кодов символов. Для определения хеш-кода следует сложить все коды символов. Лексем с таким хеш-кодом в базе данных уже значительно меньше. Компи­лятор определяет номер списка с заданным кодом и перебирает этот спи­сок, а не всю базу данных.
• При программировании шахмат тоже используется хеширование. Основная особенность состоит в том, что хеш-индекс должен очень точно отражать позицию, и поиск должен производиться максимально быстро. У нас даже нет времени на перебор списков с одним индексом. Списков, как правило, нет вообще. Для каждого значения хеш-ключа существует только одна по­зиция. Если возникла коллизия и встретилась позиция с таким же ключом, то она записывается поверх прежней. Зачем при программировании шахмат и других подобных игр хеширование и запоминание позиций? Дело в том, что при переборе мы имеем не дерево игры в прямом смысле, а граф. По­зиции повторяются через некоторое количество полуходов, и даже в одну и ту же позицию можно прийти различными путями. Можно воспользоваться некоторой информацией о позиции, которая уже встречалась. Самое про­стое и эффективное — это использовать позицию, чтобы улучшить порядок ходов. Это особенно выразительно при итеративных углублениях. Улучше­ние упорядочивания ходов — основное назначение хеш-таблицы. Переста­новки или повторы позиций тоже играют свою роль. Особенно их много в конце игры.
• Для баз данных телефонных номеров.
• Каталог книг.
• Для хранения паролей пользователей.
• Браузер хранит адреса посещенных страниц в хеш-таблице.

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

////////////////////////////////Hash_Table class//////////////////////////////////////////

template < typename TKey, typename TValue>
class Hash_Table {
private:
 unsigned static const defaultCapacity=17;
 std::vector< Single_Linked_List< std::pair< TKey,TValue> > > table;
 unsigned capacity;
 unsigned count;

public:
 Hash_Table();
 Hash_Table(unsigned divisor);
 ~Hash_Table();
 unsigned HashIntKey(int key) const;
 unsigned DataToKey(const TValue& Data) const;
 const TValue& Search(const TKey& key) const;
 void Insert(const TKey& key_val,TValue& el_value);
 void Output() const;// output the hash table
 void Delete(TValue element);
 const TValue& operator[](int key);
};

template < typename TKey, typename TValue>
unsigned Hash_Table< TKey,TValue>::HashIntKey(int key) const{
 return key%capacity;
}


template < typename TKey, typename TValue>
Hash_Table< TKey,TValue>::Hash_Table(){
 //////////////////////////////////////////////////////////////////////////
 count=0;
 capacity=defaultCapacity;
 //////////////////////////////////////////////////////////////////////////
 table.resize(defaultCapacity, Single_Linked_List >());
}

template < typename TKey, typename TValue>
Hash_Table< TKey,TValue>::Hash_Table(unsigned divisor){
 count=0;
 capacity=divisor;
 //////////////////////////////////////////////////////////////////////////
 table.resize(capacity, Single_Linked_List< pair< TKey,TValue> >());
}

template < typename TKey, typename TValue>
Hash_Table< TKey,TValue>::~Hash_Table(){
 table.clear();
}

template < typename TKey, typename TValue>
const TValue& Hash_Table< TKey,TValue>::Search(const TKey& key) const{
 unsigned pos=HashIntKey(key);
 //////////////////////////////////////////////////////////////////////////
 Single_Linked_List< pair< TKey,TValue> >& lst = table.at(pos);
 try {
  if(lst.GetSize()< 1) //if list hasnt elements
   throw inv_ex;
  for(Single_Linked_List< pair< TKey,TValue> >::iterator it = lst.begin(); it != lst.end(); ++it) {
   if(it->first == key){
    return (it->second); 
   } 
  }
 }
 catch(exception &e){
  cout< < e.what()< < endl;
 }
 Insert(key,TValue()); //insert element with default data
 return operator[](key);
}

template < typename TKey, typename TValue>
void Hash_Table< TKey,TValue>::Insert(const TKey& key_val,TValue& el_value){
 unsigned pos=HashIntKey((int)key_val); //get pos by hashing
 //////////////////////////////////////////////////////////////////////////
 pair< TKey,TValue> toInsert(key_val, el_value);
 //////////////////////////////////////////////////////////////////////////
 Single_Linked_List< pair >& lst = table.at(pos);
   //If key already store, replace data
  if(!lst.isEmpty()) {
  for(Single_Linked_List< pair >::iterator it = lst.begin(); it != lst.end(); ++it) {
   if(it->first == key_val){
    //it->second=el_value;
    it.SetValue(toInsert);
        return;
      } 
    }
  }
    //No items with that key, store a new one
  table[pos].Push_Front(toInsert);
 count++;
}

template < typename TKey, typename TValue>
void Hash_Table< TKey,TValue>::Output() const {
 int NumOfCollision = 0;
 //////////////////////////////////////////////////////////////////////////
 cout< < "Hash table capacity "< 1) {
   NumOfCollision += table[i].GetSize() - 1;
  }
  //////////////////////////////////////////////////////////////////////////
    for(Single_Linked_List< pair >::const_iterator it = table[i].begin(); it != table[i].end();it++) {
   cout< < "HashTable["< < i< < "]: "< < (it->second)< < endl;
    }
  }
 cout< < "N.Hash collisions: "< < NumOfCollision< < endl;
}


template < typename TKey, typename TValue>
const TValue& Hash_Table< TKey,TValue>::operator[](int key){
 unsigned pos=HashIntKey(key);
 //////////////////////////////////////////////////////////////////////////
 Single_Linked_List< pair< TKey,TValue> >& lst = table.at(pos);
 try {
  if(lst.GetSize()< 1)
   throw inv_ex;
  for(Single_Linked_List< pair< TKey,TValue> >::iterator it = lst.begin(); it != lst.end(); ++it) {
   if(it->first == key){
    return (it->second);
   } 
  }
 }
 catch(exception &e){
  cout< < e.what()< < endl;
 }
 Insert(key,TValue());
 return operator[](key);
}

Код тестирования:

Hash_Table< int,string> ht(9);
  ht.Insert(223, string("Ololoshenka"));
  ht.Insert(5345, string("This is matrix, Neo"));
  ht.Insert(1, string("Use yourrr power, Luke"));
  
  ht.Output();
 cout< < ht[1]< < endl;

Вывод:

Posted in: Алгоритмы, Структуры данных, CPP