Иван Кисляков (Программист) - Хеш-таблицы
Название: | Хеш-таблицы | |
Автор: | Иван Кисляков (Программист) | |
Жанр: | Статьи и рефераты, Самиздат, сетевая литература, Литература ХXI века (эпоха Глобализации экономики), Алгоритмы и структуры данных, C, C++, C# | |
Изадано в серии: | неизвестно | |
Издательство: | Интернет-издательство «Stribog» | |
Год издания: | 2022 | |
ISBN: | неизвестно | |
Отзывы: | Комментировать | |
Рейтинг: | ||
Поделись книгой с друзьями! Помощь сайту: донат на оплату сервера |
Краткое содержание книги "Хеш-таблицы"
Я много раз заглядывал на просторы интернета, нашел много интересных статей о хеш-таблицах, но вразумительного и полного описания того, как они реализованы, так и не нашел. В связи с этим мне просто не терпелось написать пост на данную, столь интересную, тему.
Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.
Читаем онлайн "Хеш-таблицы". [Страница - 3]
// удаление предыдущего массива
for (int i = 0; i < buffer_size; ++i)
if (arr2[i])
delete arr2[i];
delete[] arr2;
}
Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.
Начнем с самого простого — метод Find элемент по значению.
bool Find(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2())
{
int h1 = hash1(value, buffer_size); // значение, отвечающее за начальную позицию
int h2 = hash2(value, buffer_size); // значение, ответственное за "шаг" по таблице
int i = 0;
while (arr[h1] != nullptr && i < buffer_size)
{
if (arr[h1]->value == value && arr[h1]->state)
return true; // такой элемент есть
h1 = (h1 + h2) % buffer_size;
++i; // если у нас i >= buffer_size, значит мы уже обошли абсолютно все ячейки, именно для этого мы считаем i, иначе мы могли бы зациклиться.
}
return false;
}
Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.
bool Remove(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2())
{
int h1 = hash1(value, buffer_size);
int h2 = hash2(value, buffer_size);
int i = 0;
while (arr[h1] != nullptr && i < buffer_size)
{
if (arr[h1]->value == value && arr[h1]->state)
{
arr[h1]->state = false;
--size;
return true;
}
h1 = (h1 + h2) % buffer_size;
++i;
}
return false;
}
Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.
Помимо этого в данном методе есть еще одна часть, поддерживающая правильную асимптотику. Это запоминание первого подходящего для вставки элемента (даже если он deleted). Именно туда мы вставим элемент, если в нашей хеш-таблицы нет такого же. Если ни одного deleted-элемента на нашем пути нет, мы создаем новый Node с нашим вставляемым значением.
bool Add(const T& value, const THash1& hash1 = THash1(),const THash2& hash2 = THash2())
{
if (size + 1 > int(rehash_size * buffer_size))
Resize();
else if (size_all_non_nullptr > 2 * size)
Rehash(); // происходит рехеш, так как слишком много deleted-элементов
int h1 = hash1(value, buffer_size);
int h2 = hash2(value, buffer_size);
int i = 0;
int first_deleted = -1; // запоминаем первый подходящий (удаленный) элемент
while (arr[h1] != nullptr && i < buffer_size)
{
if (arr[h1]->value == value && arr[h1]->state)
return false; // такой элемент уже есть, а значит его нельзя вставлять повторно
if (!arr[h1]->state && first_deleted == -1) // находим место для нового элемента
first_deleted = h1;
h1 = (h1 + h2) % buffer_size;
++i;
}
if (first_deleted == -1) // если не нашлось подходящего места, создаем новый Node
{
arr[h1] = new Node(value);
++size_all_non_nullptr; // так как мы заполнили один пробел, не забываем записать, что это место теперь занято
}
else
{
arr[first_deleted]->value = value;
arr[first_deleted]->state = true;
}
++size; // и в любом случае мы увеличили количество элементов
return true;
}
В заключение приведу полную реализацию хеш-таблицы.
int HashFunctionHorner(const std::string& s, int table_size, const int key)
{
int hash_result = 0;
for (int i = 0; s[i] != s.size(); ++i)
{
hash_result = (key * hash_result + s[i]) % table_size;
}
hash_result = (hash_result * 2 + 1) % table_size;
return hash_result;
}
struct HashFunction1
{
int operator()(const std::string& s, int table_size) const
{
return HashFunctionHorner(s, table_size, table_size - 1);
}
};
struct HashFunction2
{
int operator()(const std::string& s, int table_size) const
{
return HashFunctionHorner(s, table_size, table_size + 1);
}
};
template <class T, class THash1 = HashFunction1, class THash2 = HashFunction2>
class HashTable
{
static const int default_size = 8;
constexpr static const double rehash_size = 0.75;
struct Node
{
T value;
bool state;
Node(const T& value_) : value(value_), state(true) {}
};
Node** arr;
int size;
int buffer_size;
int size_all_non_nullptr;
void Resize()
{
int past_buffer_size = buffer_size;
buffer_size *= 2;
size_all_non_nullptr = 0;
size = 0;
Node** arr2 = new --">