从零开始的 STL 实现记录：Container-8.3

前言

上一节简要分析了 hashtable 的数据结构，包括节点的结构、迭代器的结构以及 hashtable 自身的结构，还是需要说明一下，本文实现的 hashtable 与 STL 中的原生 hashtable 有一定的差别，但逻辑几乎相同，读者如果想完整地实现原生 STL-hashtable 还请阅读源码。

本节将会介绍 hashtable 的构造与析构函数等的实现。

hashtable 的构造与析构

public:  // 构造、复制、移动、析构函数
    // 这里使将构造函数声明为 explicit，因为后两个参数都缺省了，可以通过 size_type 
    // 直接进行隐式转换，会产生一些不必要的 bug
    explicit hashtable(size_type bucket_count, 
                       const Hash& hash = Hash(), 
                       const KeyEqual& equal = KeyEqual())
        : size_(0), hash_(hash), equal_(equal), mlf_(1.0f) {
        init(bucket_count);
    }


    template <class Iter, typename std::enable_if<
        tinystl::is_input_iterator<Iter>::value, int>::type = 0>
    hashtable(Iter first, Iter last, size_type bucket_count, 
              const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual())
        : size_(tinystl::distance(first, last)), hash_(hash), equal_(equal), mlf_(1.0f) {
        init(tinystl::max(bucket_count, static_cast<size_type>(tinystl::distance(first, last))));
    }

    hashtable(const hashtable& rhs) : hash_(rhs.hash_), equal_(rhs.equal_) {
        copy_init(rhs);
    }

    hashtable(hashtable&& rhs) noexcept :
        bucket_size_(rhs.bucket_size_), 
        size_(rhs.size_),
        hash_(rhs.hash_),
        equal_(rhs.equal_),
        mlf_(rhs.mlf_) {
        buckets_ = tinystl::move(rhs.buckets_);
        rhs.bucket_size_ = 0;
        rhs.size_ = 0;
        rhs.mlf_ = 1.0f;
    }

    hashtable& operator=(const hashtable& rhs);
    hashtable& operator=(hashtable&& rhs) noexcept;

    ~hashtable() { clear(); }

hashtable 也支持多种构造方式。其中，有一种特殊构造方式，如下：

template <class Iter, typename std::enable_if<
        tinystl::is_input_iterator<Iter>::value, int>::type = 0>
hashtable(Iter first, Iter last, size_type bucket_count, 
            const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual())
    : size_(tinystl::distance(first, last)), hash_(hash), equal_(equal), mlf_(1.0f) {
    init(tinystl::max(bucket_count, static_cast<size_type>(tinystl::distance(first, last))));
}

这里依然使用了 SFINAE技术，只有在 Iter为输出迭代器时才会实例化这个函数，其中，type = 0被赋予了默认值，如果不给 std::enable_if 的 ::type 成员提供默认值，而且条件不满足时，那么这个 ::type 成员将不存在。这将导致编译器无法正确解析使用这个类型的代码，可能会产生编译错误。给 ::type 成员提供默认值，即使条件不满足，也会使得代码中的使用更加稳定，因为无论条件是否满足，::type 成员都会存在。

hashtable 初始化

构造函数会调用 init() 函数进行哈希表的初始化，查看这个函数的实现：

/// @brief 初始化能容纳 n 个元素的 hashtable
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::init(size_type n) {
    const auto bucket_count = next_size(n);
    try {
        buckets_.reserve(bucket_count);
        // 初始化 buckets_，将每个 bucket 置为空
        // buckets_ 为 vector，可以使用 vector 的 assign 方法
        buckets_.assign(bucket_count, nullptr);
    }
    catch (...) {
        bucket_size_ = 0;
        size_ = 0;
        throw;
    }
    bucket_size_ = buckets_.size();
}

init(n) 函数就是简单地初始化了一个大小为 n 的 bucket 表，并将每个 bucket 均赋为 nullptr，由于 bucket 本身由 vector 实现，因此可以调用 vector 的 reserve 及 assign 方法简单地对其进行空间分配及赋值。

同时，拷贝构造函数调用了 copy_init()，查看该函数的实现可以发现，该函数就是遍历 rhs 所有非空 bucket 中的节点并在新的 hashtable 中构造相同的节点，以完成拷贝构造。

/// @brief 用一个 hashtable 初始化当前 hashtable
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::copy_init(const hashtable& rhs) {
    bucket_size_ = 0;
    buckets_.reserve(rhs.bucket_size_);
    buckets_.assign(rhs.bucket_size_, nullptr);
    try {
        for (size_type i = 0; i < rhs.bucket_size_; ++i) {
            auto cur = rhs.buckets_[i];
            // 如果 rhs 的某个 bucket 处存在链表
            if (cur) {
                auto copy = create_node(cur->value);
                buckets_[i] = copy;
                // 复制链表
                for (auto next = cur->next; next; cur = next, next = cur->next) {
                    copy->next = create_node(next->value);
                    copy = copy->next;
                }
                copy->next = nullptr;
            }
        }
        bucket_size_ = rhs.bucket_size_;
        size_ = rhs.size_;
        mlf_ = rhs.mlf_;
    }
    catch (...) {
        clear();
        // throw;
    }
}

以上的两个构造函数也都遵循 commit or rollback，要么构造出所有元素，要么一点都不构造。

创建与销毁 node

在 copy_init() 中也调用了 create_node() 函数，该函数的作用就是创建一个节点，十分简单，与 destroy_node() 一同在下方列出，这里就不再分析。

/// @brief 创建一个节点
template <class T, class Hash, class KeyEqual>
template <class ...Args>
typename hashtable<T, Hash, KeyEqual>::node_ptr
hashtable<T, Hash, KeyEqual>::create_node(Args&& ...args) {
    node_ptr np = node_allocator::allocate(1);
    try {
        data_allocator::construct(tinystl::address_of(np->value), tinystl::forward<Args>(args)...);
        np->next = nullptr;
    }
    catch (...) {
        node_allocator::deallocate(np);
        throw;        
    }
    return np;
}

/// @brief 销毁一个节点
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::destroy_node(node_ptr node) {
    data_allocator::destroy(tinystl::address_of(node->value));
    node_allocator::deallocate(node);
    node = nullptr;
}

析构函数

hashtable 的析构函数调用了 clear()，该函数遍历所有的 bucket，逐个摧毁 bucket 中的节点，并在最后将每个 bucket 都置为 nullptr。

/// @brief 清空 hashtable
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::clear() {
    if (size_ != 0) {
        for (size_type i = 0; i < bucket_size_; ++i) {
            auto cur = buckets_[i];
            while (cur) {
                auto next = cur->next;
                destroy_node(cur);
                cur = next;
            }
            buckets_[i] = nullptr;
        }
        size_ = 0;
    }
}

值得注意的是，clear() 并未释放维护 bucket 结构所分配的空间，但由于 bucket 是由 vector 实现的，会随着 hashtable 一起析构并自己释放内存。

辅助函数

为方便使用，hashtable 内提供了一些辅助函数，实现如由 node 转化为迭代器，查找第一个不为空的 bucket 等功能。

private:  // 辅助函数
    bool is_equal(const key_type& key1, const key_type& key2) {
        return equal_(key1, key2);
    }

    bool is_equal(const key_type& key1, const key_type& key2) const {
        return equal_(key1, key2);
    }

    /// @brief 将 node 转换为 const_iterator 指针
    const_iterator M_cit(node_ptr node) const noexcept {
        return const_iterator(node, const_cast<hashtable*>(this));
    }

    iterator M_begin() noexcept {
        for (size_type i = 0; i < bucket_size_; ++i) {
            // 找到第一个不为空的 bucket
            if (buckets_[i]) {
                return iterator(buckets_[i], this);
            }
        }
        return iterator(nullptr, this);
    }

    const_iterator M_begin() const noexcept {
        for (size_type n = 0; n < bucket_size_; ++n) {
            // 找到第一个不为空的 bucket
            if (buckets_[n]) {
                return M_cit(buckets_[n]);
            }
        }
        return M_cit(nullptr);
    }

利用上述函数可以很方便地得到如下的信息：

public:  // 迭代器相关
    iterator begin() noexcept { return M_begin(); }
    const_iterator begin() const noexcept { return M_begin(); }
    const_iterator cbegin() const noexcept { return M_begin(); }

    iterator end() noexcept { return iterator(nullptr, this); }
    const_iterator end() const noexcept { return M_cit(nullptr); }
    const_iterator cend() const noexcept { return M_cit(nullptr); }

public:  // 容量相关
    bool      empty()    const noexcept { return size_ == 0; }
    size_type size()     const noexcept { return size_; }
    size_type max_size() const noexcept { return static_cast<size_type>(-1); }

hash & rehash

如何获取哈希值以及在当前的哈希表负载较大时重新哈希是对于哈希表十分重要的功能，下面来就来分析一下如何这两部分的逻辑。

hash 值的获取

哈希值的获取就是简单地调用模板中提供的哈希函数或仿函数来计算哈希值，并对 bucket_size_ 取模，若提供了第二个参数 n 则会对 n 取模，以此确定哈希值，也就是 bucket 的索引。

STL 中采取质数作为 bucket 的大小可以减少哈希冲突。

/// @brief 根据 key 计算 hash 值，对 n 取模
template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::size_type
hashtable<T, Hash, KeyEqual>::hash(const key_type& key, size_type n) const {
    return hash_(key) % n;
}

/// @brief 根据 key 计算 hash 值，对 bucket_size_ 取模
template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::size_type
hashtable<T, Hash, KeyEqual>::hash(const key_type& key) const {
    return hash_(key) % bucket_size_;
}

rehash 策略

关于 rehash 的策略，STL 中的 hashtable 提供了一个模板参数 _RehashPolicy，并在 unordered_set 与 unordered_map 中指定了该值为 __detail::_Prime_rehash_policy，感兴趣的读者可以自行查看 hashtable_policy.h 中关于这部分的定义，由于完整地实现这些功能太过繁杂，因此 TinySTL 简单地在 hashtable 中自行指定了一个与 STL 中类似的 rehash 策略。

// hashtable.h

/*
*  @tparam _RehashPolicy  Policy class with three members, all of
*  which govern the bucket count. _M_next_bkt(n) returns a bucket
*  count no smaller than n.  _M_bkt_for_elements(n) returns a
*  bucket count appropriate for an element count of n.
*  _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
*  current bucket count is n_bkt and the current element count is
*  n_elt, we need to increase the bucket count.  If so, returns
*  make_pair(true, n), where n is the new bucket count.  If not,
*  returns make_pair(false, <anything>)
*/

// unordered_set.h

template<typename _Value,
    typename _Hash = hash<_Value>,
    typename _Pred = std::equal_to<_Value>,
    typename _Alloc = std::allocator<_Value>,
    typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>>
using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
                    __detail::_Identity,
                    _Pred, _Hash,
                    __detail::_Mod_range_hashing,
                    __detail::_Default_ranged_hash,
                    __detail::_Prime_rehash_policy, _Tr>;

TinySTL 中的哈希策略简单地根据负载因子来决定，负载因子被定义为 size_ / bucket_size_ 即元素个数除以桶的个数，如果负载因子大于一则认为需要重新哈希。

float load_factor() const noexcept {
    return bucket_size_ != 0 ? static_cast<float>(size_) / bucket_size_ : 0.0f;
}

float max_load_factor() const noexcept { return mlf_; }

void max_load_factor(float ml) noexcept {
    // ml != ml 用于判断 ml 是否为 NaN
    THROW_OUT_OF_RANGE_IF(ml != ml || ml < 0, "invalid hash load factor");
    mlf_ = ml;
}

rehash 会调用 ht_next_prime 获取下一个 bucket 的大小，并且重新计算当前所有节点的哈希值，并放进新的桶中。

/// @brief 如果插入 n 个元素后，负载因子大于最大负载因子，就重新分配桶的个数
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::rehash_if_need(size_type n) {
    if (static_cast<float>(size_ + n) > static_cast<float>(bucket_size_) * max_load_factor()) {
        rehash(next_size(size_ + n));
    }
}

/// @brief 根据 n 计算 bucket 的大小
template <class T, class Hash, class KeyEqual>
typename hashtable<T, Hash, KeyEqual>::size_type
hashtable<T, Hash, KeyEqual>::next_size(size_type n) const {
    return ht_next_prime(n);
}

/// @brief 重新对元素进行一遍哈希，插入到新的位置
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::rehash(size_type count) {
    auto n = ht_next_prime(count);  // 获取 bucket 的大小
    if (n > bucket_size_) {
        replace_bucket(n);
    }
    else {
        // 判断是否值得重新哈希
        if (static_cast<float>(size_) / static_cast<float>(n) < max_load_factor() - 0.25f
            && static_cast<float>(n) < static_cast<float>(bucket_size_) * 0.75f) {
            replace_bucket(n);
        }
    }
}

/// @brief 用新的桶替换旧的桶
template <class T, class Hash, class KeyEqual>
void hashtable<T, Hash, KeyEqual>::replace_bucket(size_type bucket_count) {
    bucket_type bucket(bucket_count);
    if (size_ != 0) {
        // 遍历每一个 bucket
        for (size_type i = 0; i < bucket_size_; ++i) {
            // 遍历 bucket 中的每一个节点
            for (auto first = buckets_[i]; first; first = first->next) {
                auto tmp = create_node(first->value);
                // 计算新的哈希值，即新的 bucket 的位置
                const auto n = hash(value_traits::get_key(first->value), bucket_count);
                auto f = bucket[n];
                bool is_inserted = false;
                for (auto cur = f; cur; cur = cur->next) {
                    // 找到与当前节点相同键值的节点，插入到该节点之后
                    if (is_equal(value_traits::get_key(cur->value), value_traits::get_key(tmp->value))) {
                        tmp->next = cur->next;
                        cur->next = tmp;
                        is_inserted = true;
                        break;
                    }
                }
                // 如果没有找到相同键值的节点，就插入到链表头部
                if (!is_inserted) {
                    tmp->next = f;
                    bucket[n] = tmp;
                }
            }
        }
    }
    buckets_.swap(bucket);
    bucket_size_ = buckets_.size();
}

/// @brief 交换两个 hashtable
template <class T, class Hash, class KeyEqual>
void swap(hashtable<T, Hash, KeyEqual>& lhs, hashtable<T, Hash, KeyEqual>& rhs) noexcept {
    lhs.swap(rhs);
}

总结

本节主要分析了 hashtable 的构造、析构以及与哈希相关的策略等，这里实现的 hashtable 与 STL 还是有一定的差别的，下一节将会分析 hashtable 的增删查改等功能的实现。