SeniorКодРедкоЕщё не отвечали
Реализуйте алгоритм хеширования с обработкой коллизий
Реализуйте хеш FNV-1a для строк и хеш-таблицу, разрешающую коллизии методом цепочек (separate chaining).
Требования:
каждый бакет — цепочка записей.
при превышении коэффициентом нагрузки порога, например 0.75.
fnv1a: быстрый некриптографический хеш с хорошим распределением.- Таблица поддерживает
insert,find,erase; один бакет на хеш-слот, - Держите среднее время операций O(1): рехешируйте (увеличивайте таблицу)
uint64_t fnv1a(const std::string& s) {
// ваш код здесь
}
template<typename K, typename V>
class HashMap {
public:
void insert(const K& key, const V& val); // ваш код здесь
std::optional<V> find(const K& key) const; // ваш код здесь
bool erase(const K& key); // ваш код здесь
};Допишите реализацию.
Хорошая хеш-функция равномерно распределяет ключи и быстро вычисляется (FNV-1a, djb2). Разрешение коллизий: метод цепочек или открытая адресация (линейное/квадратичное зондирование, двойное хеширование). std::unordered_map обычно использует цепочки.
- ✗Использовать плохую хеш-функцию, кластеризующую значения — приводит к O(n) поиску в худшем случае
- ✗Не обрабатывать рост таблицы (рехеширование) при превышении порогового коэффициента нагрузки
- ✗Использовать криптографический хеш (SHA, MD5) для хеш-таблицы — слишком медленно
- →Что такое коэффициент нагрузки и как он влияет на производительность?
- →Сравните открытую адресацию и метод цепочек с точки зрения кэш-производительности.
Оглавление
Задача
Реализуйте простую хеш-таблицу с методом цепочек (separate chaining) и хеш-функцию FNV-1a для строк.
Решение
#include <vector>
#include <list>
#include <string>
#include <functional>
#include <optional>
#include <cassert>
// FNV-1a хеш для строк — быстрый, хорошее распределение
uint64_t fnv1a(const std::string& s) {
uint64_t hash = 14695981039346656037ULL; // FNV offset basis
for (unsigned char c : s) {
hash ^= c;
hash *= 1099511628211ULL; // FNV prime
}
return hash;
}
// Хеш-таблица с методом цепочек
template<typename K, typename V>
class HashMap {
public:
explicit HashMap(size_t buckets = 16) : buckets_(buckets) {}
void insert(const K& key, const V& val) {
auto& chain = buckets_[index(key)];
for (auto& [k, v] : chain) {
if (k == key) { v = val; return; } // обновить
}
chain.emplace_back(key, val);
++size_;
if (loadFactor() > 0.75) rehash();
}
std::optional<V> find(const K& key) const {
for (const auto& [k, v] : buckets_[index(key)])
if (k == key) return v;
return std::nullopt;
}
bool erase(const K& key) {
auto& chain = buckets_[index(key)];
for (auto it = chain.begin(); it != chain.end(); ++it) {
if (it->first == key) { chain.erase(it); --size_; return true; }
}
return false;
}
size_t size() const { return size_; }
private:
using Bucket = std::list<std::pair<K, V>>;
size_t index(const K& key) const {
return std::hash<K>{}(key) % buckets_.size();
}
double loadFactor() const {
return static_cast<double>(size_) / buckets_.size();
}
void rehash() {
std::vector<Bucket> old = std::move(buckets_);
buckets_.assign(old.size() * 2, {});
size_ = 0;
for (auto& chain : old)
for (auto& [k, v] : chain) insert(k, v);
}
std::vector<Bucket> buckets_;
size_t size_ = 0;
};
int main() {
// FNV-1a тест
assert(fnv1a("hello") != fnv1a("world"));
assert(fnv1a("hello") == fnv1a("hello"));
// HashMap тест
HashMap<std::string, int> map;
map.insert("one", 1);
map.insert("two", 2);
map.insert("three", 3);
assert(map.find("one") == std::optional<int>{1});
assert(map.find("two") == std::optional<int>{2});
assert(!map.find("four"));
map.insert("one", 100); // обновление
assert(map.find("one") == std::optional<int>{100});
assert(map.erase("two"));
assert(!map.find("two"));
}Ключевые моменты
- FNV-1a — быстрый некриптографический хеш, хорошее распределение, прост в реализации.
- Метод цепочек прост, но хуже для кэша, чем открытая адресация.
- Рехеширование при коэффициенте нагрузки > 0.75 держит среднее время операции O(1).
std::unordered_mapиспользуетstd::hash<K>— его можно специализировать для пользовательских типов.
Оглавление
