Что такое хеш-таблицы?
В информатике хеш-таблица - это структура данных, которая реализует массив связанных списков для хранения данных. Используя хеш-алгоритм, хеш-таблица может вычислять индекс для хранения строковых различных пар ключ-значение.
Сегодня я продемонстрирую, как создать эту структуру данных на C ++. Это мое первое приложение, написанное на этом языке, поэтому вся критика и отзывы, которые помогут мне стать лучше, приветствуются. :)
Начиная с малого
Первое, что нам нужно сделать, это создать класс Node для хранения нашей пары ключ-значение.
class Node
{
private:
string key;
string value;
Node *next;
public:
Node();
Node(string, string);
string get_key();
string get_value();
Node *get_next();
void set_key(string);
void set_value(string);
void set_next(Node *);
};
Вы заметите, что у этого класса есть два перегруженных конструктора и сеттеры / геттеры для каждого значения. У каждого узла будут строки в качестве ключей и значений, а также указатель на следующий узел на случай конфликта.
Коллизия определяется как два ключа с одним и тем же хеш-индексом, и мы будем работать над этим, создав связанный список по этому индексу для хранения всех последующих коллизий. Это также называется «цепочкой».
#хеш-таблица
Далее мы создадим наш класс Hash_Table.
class Hash_Table
{
private:
unsigned int size;
Node **array;
public:
Hash_Table(unsigned int);
unsigned int get_size();
unsigned long int hash_djb2(string);
void addNode(string, string);
string get_value(string);
void printHash();
void delete_table();
};
Наш класс Hash Table будет иметь размер, определяемый пользователем, и массив узлов в качестве частных атрибутов. Что касается наших методов, у нас есть функции, которые будут индексировать нашу строку, добавлять новые узлы, извлекать значение с заданным ключом, распечатывать все содержимое хеш-таблицы и удалять хеш-таблицу. Мы подробно рассмотрим все эти методы.
Тестирование кода
В нашем основном файле давайте начнем с динамического выделения памяти для хеш-таблицы.
<main.cpp>
int main()
{
unsigned int s = 1024;
Hash_Table *ht = new Hash_Table(s);
}
Это вызывает наш конструктор, который выполняет следующие действия:
Hash_Table::Hash_Table(unsigned int size)
{
unsigned int i;
if (!size)
throw "Value must be over 0";
this->size = size;
this->array = new Node * [size];
for (i = 0; i < size; i++)
this->array[i] = nullptr;
}
В этом методе мы проверяем, что пользователь не ввел 0 в качестве размера, а затем мы создаем массив с пустыми узлами, которые все указывают на null. Давайте проверим, правильно ли мы это сделали.
cout << "Address of hash table is " << &ht << endl; /* Address of hash table is 0x7ffee06eca20 */
Алгоритм djb2
Алгоритм для нашей хеш-функции разработан компьютерным ученым Дэном Бернстайном. Он использует битовые манипуляции и простые числа для создания хеш-индекса из строки.
unsigned long int Hash_Table::hash_djb2(string str)
{
unsigned long int hash;
int c;
hash = 5381;
for (auto x: str)
{
c = x;
hash = ((hash << 5) + hash) + c;
/* hash * 33 + c */
}
return (hash % this->size);
}
Давайте посмотрим на это в действии.
<main.cpp> string str = "c++isfun"; cout << "Hash index of " << str << " is " << ht->hash_djb2(str) << endl; /* Hash index of c++isfun is 611 */ str = "oopiscool"; cout << "Hash index of " << str << " is " << ht->hash_djb2(str) << endl; /* Hash index of oopiscool is 124 */
Добавление узлов
Следующий метод, который мы рассмотрим, - это добавление узлов.
void Hash_Table::addNode(string key, string value)
{
Node *curr;
unsigned long int idx;
if (key.empty())
throw "Invalid Key";
idx = this->hash_djb2(key);
curr = this->array[idx];
while (curr)
{
if (curr->get_key() == key)
{
cout << "Collision detected!" << endl;
curr->set_value(value);
return;
}
curr = curr->get_next();
}
Node *n = new Node(key, value);
n->set_next(this->array[idx]);
this->array[idx] = n;
}
Цикл while в середине проверяет каждый индекс, если уже существует ключ с тем же именем, что и входная строка. Если есть, он заменит значение в этом узле новым строковым значением. В противном случае узел с новым ключом и значением будет вставлен в начало каждого связанного списка по хешированному индексу. Чтобы это проверить, нам понадобится метод печати.
cout - твой друг
void Hash_Table::printHash()
{
unsigned long int i;
Node *curr;
bool first = false;
cout << "{";
for (i = 0; i < this->size; i++)
{
if ((curr = this->array[i]))
{
while (curr)
{
if (first)
cout << ", ";
cout << ""' << curr->get_key() << "': '" << curr->get_value() << "'";
first = true;
curr = curr->get_next();
}
}
}
cout << "}" << endl;
}
Собираем все вместе
Чтобы проверить, что наши методы работают правильно, нам нужно добавить пару узлов, некоторые из которых, возможно, придется перезаписать, а некоторые будут конфликтовать.
<main.cpp>
ht->addNode("betty", "holberton");
ht->addNode("stylist", "kevin");
ht->addNode("stylist", "shawna");
ht->addNode("subgenera", "chicken");
/* stylist and subgenera will collide at index 225 */
ht->printHash();
/*
{'betty': 'holberton', 'subgenera': 'chicken', 'stylist': 'shawna'}
*/
Как видите, «стилист» имеет правильное значение «шона», потому что оно было добавлено позже. Кроме того, наш список печати может печатать как «subgenerea», так и «stylist», даже если они имеют один и тот же индекс, благодаря его способности перемещаться по связному списку.
Покажи мне ценность
Что, если нам просто нужно значение данного ключа, без необходимости распечатывать всю хеш-таблицу? Точно так же, когда мы получаем доступ к значению словаря в Python или объекту в Javascript, когда мы вводим:
print(hash_table["betty"])
, мы можем написать метод, который будет получать это значение за нас.
string Hash_Table::get_value(string key)
{
unsigned long int idx;
Node *curr;
if (key.empty())
throw "Invalid key";
idx = this->hash_djb2(key);
curr = this->array[idx];
while (curr)
{
if (curr->get_key() == key)
return curr->get_value();
curr = curr->get_next();
}
return nullptr;
}
Теперь, чтобы проверить это:
<main.cpp> string key = "stylist"; cout << key << "'s value is " << ht->get_value(key) << endl; /* stylist's value is shawna */ key = "betty"; cout << key << "'s value is " << ht->get_value(key) << endl; /* betty's value is holberton */
Все бесплатно!
И последнее, но не менее важное: нам нужна функция, которая удалит все выделения памяти в куче.
void Hash_Table::delete_table()
{
Node *tmp, *curr;
unsigned long int i;
for (i = 0; i < this->size; i++)
{
if ((curr = this->array[i]))
{
while (curr)
{
tmp = curr;
curr = curr->get_next();
delete tmp;
}
}
}
delete[] this->array;
}
Также нам нужно освободить экземпляр класса в нашем main:
<main.cpp> ht->delete_table(); delete ht;
Это все, ребята. Удачного хеширования и спасибо за чтение!
