Хеш-таблицы [Иван Кисляков Программист] (fb2) читать постранично, страница - 3
- Хеш-таблицы 299 Кб, 10с. скачать: (fb2) читать: (полностью) - (постранично) - Иван Кисляков (Программист)
[Настройки текста] [Cбросить фильтры]
зациклиться.
}
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 Node * [buffer_size]; for (int i = 0; i < buffer_size; ++i) arr2[i] = nullptr; std::swap(arr, arr2); for (int i = 0; i < past_buffer_size; ++i) { if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); } for (int i = 0; i < past_buffer_size; ++i) if (arr2[i]) delete arr2[i]; delete[] arr2; }
void Rehash() { size_all_non_nullptr = 0; size = 0; Node** arr2 = new Node * [buffer_size]; for (int i = 0; i < buffer_size; ++i) arr2[i] = nullptr; std::swap(arr, arr2); for (int i = 0; i < buffer_size; ++i) { if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); } for (int i = 0; i < buffer_size; ++i) if (arr2[i]) delete arr2[i]; delete[] arr2; }
public: HashTable() { buffer_size = default_size; size = 0; size_all_non_nullptr = 0; arr = new Node*[buffer_size]; for (int i = 0; i < buffer_size; ++i) arr[i] = nullptr; } ~HashTable() { for (int i = 0; i < buffer_size; ++i) if (arr[i]) delete arr[i]; delete[] arr; }
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(); 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
Далее мы реализуем удаление элемента — 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 Node * [buffer_size]; for (int i = 0; i < buffer_size; ++i) arr2[i] = nullptr; std::swap(arr, arr2); for (int i = 0; i < past_buffer_size; ++i) { if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); } for (int i = 0; i < past_buffer_size; ++i) if (arr2[i]) delete arr2[i]; delete[] arr2; }
void Rehash() { size_all_non_nullptr = 0; size = 0; Node** arr2 = new Node * [buffer_size]; for (int i = 0; i < buffer_size; ++i) arr2[i] = nullptr; std::swap(arr, arr2); for (int i = 0; i < buffer_size; ++i) { if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); } for (int i = 0; i < buffer_size; ++i) if (arr2[i]) delete arr2[i]; delete[] arr2; }
public: HashTable() { buffer_size = default_size; size = 0; size_all_non_nullptr = 0; arr = new Node*[buffer_size]; for (int i = 0; i < buffer_size; ++i) arr[i] = nullptr; } ~HashTable() { for (int i = 0; i < buffer_size; ++i) if (arr[i]) delete arr[i]; delete[] arr; }
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(); 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
Последние комментарии
1 день 5 часов назад
1 день 9 часов назад
1 день 12 часов назад
1 день 13 часов назад
1 день 19 часов назад
1 день 19 часов назад