CPP|简单实现Hashtable

引言

哈希表,是一个重要的底层数据结构,无序的关联容器包括unordered_set,unordered_map内部都是基于哈希表实现. ~~继续灌水~~

hash

哈希表是一种通过哈希函数将键映射到索引的数据结构,哈希函数负责将任意大小的输入映射到固定大小的输出,即为哈希值.这个哈希值用作在数组中存储键值对的索引.

由于哈希函数的映射不是一对一的,可能会出现两个不同的键映射到相同的索引,即为哈希表冲突,可以使用链地址法解决冲突,即为在哈希表的每个槽中维护一个链表,将哈希值相同的元素存储在同一个槽中的链表中.

哈希表的扩容,是为了避免哈希表中链表过长导致性能下降,会在需要的时候进行扩容,扩容需要重新计算过所有元素的哈希值,并分布到新的更难打的哈希表中,这一过程称为rehashing.

哈希表的性能优化,包含试用二次哈希函数,空间配置器,内存池等,以减小内存分配的开销,提高访问速度.

并发性多线程安全.哈希表常常会考虑试用锁或其他机制来保护共享的数据结构.

这里简单实现一个哈希表,试用分链地址法,每个哈希表的桶（bucket）是一个链表，当发生冲突时，将新元素插入到链表的末尾。

来构造出hash表的框架

template <typename K, typename V, typename H = std::hash<K>>
class HashTable {
private:
    std::vector<std::list<std::pair<K, V>>> bucket;
    size_t numElements;
    float maxLoadFactor;
    H hashFunction;

private:
    size_t hash(const K &key) const { return hashFunction(key) % bucket.size(); }
    void rehash() {
        size_t newSize = bucket.size() * 2;
        std::vector<std::list<std::pair<K, V>>> newTable(newSize);
        for (auto &chain : bucket) {
            for (auto &[key, value] : chain) {
                size_t newIndex = hashFunction(key) % newSize;
                newTable[newIndex].emplace_back(key, value);
            }
        }
        bucket = std::move(newTable);
    }

    void checkLoadFactorAndRehash() {
        float loadFactor = static_cast<float>(numElements) / bucket.size();
        if (loadFactor > maxLoadFactor) {
            rehash();
        }
    }

public:
    HashTable(size_t size, float maxLoadFactor = 0.75f, const H &hashFunc = H())
        : bucket(size)
        , numElements(0)
        , maxLoadFactor(maxLoadFactor),hashFunction(hashFunc) {}

    void insert(const K &key, const V &value) {
        size_t index = hash(key);
        auto &chain = bucket[index];
        auto it = std::ranges::find_if(chain, [&key](const auto &pair) { return pair.first == key; });
        if (it == chain.end()) {
            chain.emplace_back(key, value);
            numElements++;
            checkLoadFactorAndRehash();
        }
    }

    std::optional<V> find(const K &key) const {
        size_t index = hash(key);
        const auto &chain = bucket[index];
        for (const auto &[k, v] : chain) {
            if (k == key) {
                return v;
            }
        }
        return std::nullopt;
    }

    bool remove(const K &key) {
        size_t index = hash(key);
        auto &chain = bucket[index];
        auto it = std::ranges::find_if(chain, [&key](const auto &pair) { return pair.first == key; });
        if (it != chain.end()) {
            chain.erase(it);
            numElements--;
            return true;
        }
        return false;
    }

需要考虑的式负载因子,动态调整.和哈希函数,基础实现使用 std::vector 与 std::list和std::pair , 哈希函数则使用std::hash来做模运算计算哈希值将其映射到哈希表的大小范围内.

实现其实比较简单.毕竟直接使用的STL为基础.需要注意的是其中用到了std::optional (cpp17) 和std::ranges(cpp20),还有结构化绑定(cpp17) .

C++20引入了范围(Ranges)的新特性，这是一种现代化的、功能强大的处理序列数据的机制。范围(Ranges)的目标是提供一种更简洁、更易读、更安全且更高效的方式来操作数据序列，代替传统的迭代器和手动循环操作。

而std::optional 是 C++17 中引入的标准库模板类。它提供了一种表示可选值的方式，也就是值可能存在，也可能不存在。std::optional 的主要目的是避免使用特殊的标志值（例如，空指针或魔法数）来表示缺少值。相反，它封装了一个可选值，让您以更类型安全和表达性更强的方式处理它。

再轻车熟路的加入一个迭代器.

  // 嵌套的迭代器类
    class iterator {
    private:
        using OuterIter = typename std::vector<std::list<std::pair<K, V>>>::iterator;
        using InnerIter = typename std::list<std::pair<K, V>>::iterator;

        OuterIter outer;
        OuterIter outerEnd;
        InnerIter inner;

        void skipEmptyBuckets() {
            while (outer != outerEnd && inner == outer->end()) {
                ++outer;
                if (outer != outerEnd) {
                    inner = outer->begin();
                }
            }
        }

    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = std::pair<K, V>;
        using difference_type = std::ptrdiff_t;
        using pointer = value_type *;
        using reference = value_type &;

        iterator(OuterIter outer, OuterIter outerEnd, InnerIter inner)
            : outer(outer)
            , outerEnd(outerEnd)
            , inner(inner) {
            skipEmptyBuckets();
        }

        iterator &operator++() {
            ++inner;
            if (inner == outer->end()) {
                ++outer;
                if (outer != outerEnd) {
                    inner = outer->begin();
                }
                skipEmptyBuckets();
            }
            return *this;
        }
        iterator operator++(int) {
            iterator temp = *this;
            ++(*this);
            return temp;
        }
        reference operator*() const { return *inner; }
        pointer operator->() const { return &(*inner); }
        bool operator==(const iterator &other) const { return outer == other.outer && (outer == outerEnd || inner == other.inner); }
        bool operator!=(const iterator &other) const { return !(*this == other); }
    };

    iterator begin() { return iterator(bucket.begin(), bucket.end(), bucket.empty() ? bucket.begin()->end() : bucket.begin()->begin()); }

    iterator end() { return iterator(bucket.end(), bucket.end(), bucket.empty() ? bucket.begin()->end() : bucket.end()->begin()); }

到此,一个简单的哈希容器就实现了,实际上STL的unordered_set,unordered_map 远远比这复杂,异常处理,内存池等性能优化,有更复杂的重哈希策略。

以上简单使用例

    HashTable<std::string, int> hashTable(5);

    hashTable.insert("key1", 1);
    hashTable.insert("key2", 2);
    hashTable.insert("key3", 3);
    hashTable.insert("key4", 4);

    for (const auto &[key, value] : hashTable) {
        std::cout << key << ": " << value << "\n";
    }

    hashTable.insert("key5", 5);

    for (const auto &[key, value] : hashTable) {
        std::cout << key << ": " << value << "\n";
    }

Q&A

什么是哈希表？它是如何工作的？
- A：哈希表是一种使用哈希函数组织数据，以便快速插入和搜索的数据结构。它通过将键映射到表中的位置来存储键值对。哈希函数将每个键转换为哈希表中的索引，该索引决定了键值对在表中的存储位置。如果两个键映射到同一个索引，就会产生冲突，这通常通过链表或开放寻址法来解决。
哈希冲突是什么？如何处理哈希冲突？
- A：哈希冲突发生在不同的键通过哈希函数映射到哈希表的同一位置时。处理哈希冲突的方法有：
  - 链表法（分离链接法）：在每个哈希表索引上维护一个链表，所有映射到该索引的元素都会被存储在链表中。
  - 开放寻址法：如果发生冲突，就会寻找下一个空闲的哈希表索引。
  - 双重哈希：使用一系列哈希函数而不是单一哈希函数来确定元素的存储位置。
如何选择一个好的哈希函数？
- A：一个好的哈希函数应该满足以下条件：
  - 快速计算。
  - 哈希值均匀分布，以减少冲突。
  - 一致性：相同的输入总是产生相同的输出。
  - 不同的输入应尽可能映射到不同的输出。
什么是负载因子？对哈希表有什么影响？
- A：负载因子是哈希表中已存储元素数量与位置总数的比率。它是衡量哈希表满程度的指标。当负载因子过高时，冲突的可能性增加，这会降低哈希表的性能。因此，通常在负载因子达到一定阈值时，哈希表会进行扩容（即重哈希）来增加存储位置，从而减少冲突和维护操作的效率。
解释重哈希（rehashing）。何时以及为什么需要重哈希？
- A：重哈希是在哈希表的负载因子超过预定的阈值时，增加哈希表容量并重新分配现有元素的过程。这个过程需要计算每个元素的新哈希值，并将它们移动到新表中的正确位置。重哈希可以帮助减少冲突和维持操作的快速性能。
在哈希表中插入、删除和搜索操作的复杂度是多少？
- A：理想情况下，即没有发生冲突或冲突非常少时，插入、删除和搜索操作的时间复杂度为O(1)。但是，在最坏的情况下，如果所有的键都映射到同一索引，则这些操作的时间复杂度会退化到O(n)，其中n是哈希表中元素的数量。使用良好的哈希函数和冲突解决策略可以帮助保持操作的平均时间复杂度为接近O(1)。
如何解决哈希表的扩容问题？
- A：扩容通常发生在哈希表的负载因子超过预定阈值时。解决方案通常包括：
  - 创建一个更大的哈希表：创建一个容量更大的新哈希表。
  - 重新哈希所有元素：将所有现有的元素重新计算哈希值并插入到新的哈希表中。
  - 逐步迁移：在某些实现中，可以逐步迁移元素到新表，分摊重哈希的成本到多次插入操作中。
如何确保哈希表的线程安全？
- A：确保哈希表的线程安全可以通过以下方式之一：
  - 互斥锁：使用互斥锁来同步对哈希表的访问。每次一个线程访问哈希表时，它都需要先获取锁。
  - 读写锁：如果读操作远多于写操作，使用读写锁可以提高性能，因为它允许多个线程同时读取，但写入时需要排他访问。
  - 原子操作：对于简单的操作，可以使用原子操作来避免使用锁。
  - 细粒度锁：而不是对整个哈希表加锁，可以对哈希表的一部分（例如单个桶或链表）加锁，以减少锁的粒度。
有哪些常见的哈希表实现问题？
- A：常见的哈希表实现问题包括：
  - 内存使用不当：如果哈希表过大或者存在许多空桶，可能会导致内存浪费。
  - 冲突处理不佳：如果冲突没有得到有效处理，会严重影响哈希表的性能。
  - 哈希函数选择不当：一个不好的哈希函数可能会导致频繁的冲突。
  - 扩容代价高：重哈希是一个代价很高的操作，如果发生得太频繁，可能会严重影响性能。