C++模拟实现unordered_map和unordered_set（哈希）

**C++模拟实现unordered_map和unordered_set**

在C++中，`unordered_map`和`unordered_set`是两个非常重要的容器类，它们使用哈希表来存储数据。虽然C++标准库已经提供了这些类，但是了解它们的内部工作原理可以帮助我们更好地理解它们的使用方式和优缺点。

在本文中，我们将尝试模拟实现`unordered_map`和`unordered_set`，以便于读者更好地理解它们的内部工作原理。

**哈希表**

哈希表是一种数据结构，它使用一个函数（称为哈希函数）来将输入值映射到一个固定范围内的整数。这个整数被称为哈希值。哈希表通常使用一个数组或链表来存储数据，每个元素对应一个哈希值。

在我们的实现中，我们将使用一个`std::vector`作为哈希表的底层结构。

**unordered_map**

`unordered_map`是一种关联容器，它使用哈希表来存储键值对。每个键值对由一个关键字（key）和一个值（value）组成。

在我们的实现中，我们将使用一个`std::vector`作为哈希表的底层结构，每个元素代表一个键值对。我们还将使用一个`std::unordered_map`来存储哈希值到索引的映射关系。

cpptemplate <typename Key, typename Value>
class unordered_map {
public:
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;

 struct hash_value {
 size_type operator()(const Key& key) const {
 // 使用std::hash函数来计算哈希值 return std::hash<Key>{}(key);
 }
 };

 class iterator {
 public:
 using value_type = std::pair<const Key, Value>;
 using pointer = value_type*;
 using reference = value_type&;

 iterator(size_type index) : index_(index) {}

 reference operator*() const {
 return buckets_[index_];
 }

 pointer operator->() const {
 return &buckets_[index_];
 }

 iterator& operator++() {
 ++index_;
 return *this;
 }

 bool operator!=(const iterator& other) const {
 return index_ != other.index_;
 }

 private:
 size_type index_;
 };

 unordered_map(size_type bucket_count =16, float load_factor =0.75f)
 : buckets_(bucket_count), hash_value_to_index_(bucket_count) {}

 ~unordered_map() = default;

 iterator begin() const {
 return iterator(0);
 }

 iterator end() const {
 return iterator(buckets_.size());
 }

 size_type size() const {
 return buckets_.size();
 }

 bool empty() const {
 return buckets_.empty();
 }

 void clear() {
 buckets_.clear();
 hash_value_to_index_.clear();
 }

 Value& operator[](const Key& key) {
 // 使用哈希函数来计算哈希值 size_type index = hash_value()(key);

 // 如果哈希表中已经有这个键值对，则直接返回其值 if (hash_value_to_index_[index] != buckets_.size()) {
 return buckets_[hash_value_to_index_[index]];
 }

 // 如果哈希表中没有这个键值对，则创建一个新元素并插入到哈希表中 size_type new_index = buckets_.size();
 buckets_.push_back(std::make_pair(key, Value()));
 hash_value_to_index_[new_index] = buckets_.size() -1;
 return buckets_.back().second;
 }

private:
 std::vector<std::pair<Key, Value>> buckets_;
 std::unordered_map<size_type, size_type> hash_value_to_index_;
};

cpptemplate <typename Key>
class unordered_set {
public:
 using size_type = std::size_t;
 using difference_type = std::ptrdiff_t;

 struct hash_value {
 size_type operator()(const Key& key) const {
 // 使用std::hash函数来计算哈希值 return std::hash<Key>{}(key);
 }
 };

 class iterator {
 public:
 using value_type = Key;
 using pointer = value_type*;
 using reference = value_type&;

 iterator(size_type index) : index_(index) {}

 reference operator*() const {
 return buckets_[index_];
 }

 pointer operator->() const {
 return &buckets_[index_];
 }

 iterator& operator++() {
 ++index_;
 return *this;
 }

 bool operator!=(const iterator& other) const {
 return index_ != other.index_;
 }

 private:
 size_type index_;
 };

 unordered_set(size_type bucket_count =16, float load_factor =0.75f)
 : buckets_(bucket_count), hash_value_to_index_(bucket_count) {}

 ~unordered_set() = default;

 iterator begin() const {
 return iterator(0);
 }

 iterator end() const {
 return iterator(buckets_.size());
 }

 size_type size() const {
 return buckets_.size();
 }

 bool empty() const {
 return buckets_.empty();
 }

 void clear() {
 buckets_.clear();
 hash_value_to_index_.clear();
 }

 bool operator==(const Key& key) {
 // 使用哈希函数来计算哈希值 size_type index = hash_value()(key);

 // 如果哈希表中已经有这个元素，则直接返回true if (hash_value_to_index_[index] != buckets_.size()) {
 return true;
 }

 // 如果哈希表中没有这个元素，则创建一个新元素并插入到哈希表中 size_type new_index = buckets_.size();
 buckets_.push_back(key);
 hash_value_to_index_[new_index] = buckets_.size() -1;
 return true;
 }

private:
 std::vector<Key> buckets_;
 std::unordered_map<size_type, size_type> hash_value_to_index_;
};

cppint main() {
 unordered_map<int, int> map;

 // 插入元素 map[1] =10;
 map[2] =20;
 map[3] =30;

 // 打印元素 for (auto& pair : map) {
 std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
 }

 unordered_set<int> set;

 // 插入元素 set[1] = true;
 set[2] = true;
 set[3] = true;

 // 打印元素 for (auto& element : set) {
 std::cout << "Element: " << element << std::endl;
 }

 return0;
}