C++ 哈希表详解：开散列与闭散列

C++ 哈希表详解：开散列与闭散列 | 极客日志

//定义一个枚举来记录数组的三个状态
enum State { EXIST,//存在 EMPTY,//空 DELETE//删除 };
template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    State _state = EMPTY;//状态为空
};
template<class K, class V>
class HashTable {
public:
private:
    vector<HashData<K, V>> _tables;//表的空间大小
    size_t _n; // 记录数据个数
};

//素数表
inline unsigned long __stl_next_prime(unsigned long n) {
    // Note: assumes long is at least 32 bits.
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
        6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
        402653189, 805306457, 1610612741, 3221225473, 4294967291
    };
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

//扩容
// 负载因子 >= 0.7 扩容 n/m 数据个数/表的空间大小
//为了方便计算分子 n*10
if (_n * 10 / _tables.size() >= 7) {
    //创建一个新的哈希表 newht 哈希表里本来就有 vector
    HashTable<K, V> newht;
    //*2 是无法一直保持素数的
    //newht._tables.resize(_tables.size() * 2);
    //使用素数表来获取比素数表的值大一点的值
    newht._tables.resize(__stl_next_prime(_tables.size() + 1));
    for (auto& data : _tables) {
        // 遍历旧表，旧表的数据映射到新表
        if (data._state == EXIST) {
            //使用新对象去调用插入，把旧表的数据插入到新表
            newht.Insert(data._kv);
        }
    }
    //交换新旧表的空间
    _tables.swap(newht._tables);
}

bool Insert(const pair<K, V>& kv) {
    //如果值已经存在
    if (Find(kv.first)) return false;
    Hash hash;//仿函数，用于转换成为无符号整形
    //插入值之后从起始位置 hash0 去用插入的值对表的大小取模算出值对应的位置
    size_t hash0 = hash(kv.first) % _tables.size();//hash0 是第一次算出来的位置
    size_t hashi = hash0;
    size_t i = 1;
    int flag = 1;
    while (_tables[hashi]._state == EXIST)//如果 hashi 的状态为存在
    {
        //进行线性探测
        //如果到达表的最后一个位置那么就模一下表的空间大小
        hashi = (hash0 + i) % _tables.size();
        ++i;
        //二次探测
        /*hashi = (hash0 + (i*i*flag)) % _tables.size();
        if (hashi < _tables.size()) hashi += _tables.size();
        if (flag == 1) {
            flag = -1;
        } else {
            ++i;
            flag = 1;
        }*/
    }
    //当遇到空的位置就插入
    _tables[hashi].kv = kv;
    _tables[hashi]._state = EXIST;//将插入的位置标记为存在
    ++_n;
    return true;
}

HashData<K, V>* Find(const K& key) {
    Hash hash;
    size_t hash0 = hash(key) % _tables.size();
    size_t hashi = hash0;
    size_t i = 1;
    while (_tables[hashi]._state != EMPTY) {
        if (_tables[hashi]._state == EXIST//如果状态是存在并且是那个值
            && _tables[hashi]._kv.first == key) {
            return &_tables[hashi];
        }
        // 线性探测
        hashi = (hash0 + i) % _tables.size();
        ++i;
    }
    return nullptr;
}

bool Erase(const K& key) {
    HashData<K, V>* ret = Find(key);
    if (ret) {
        ret->_state = DELETE;
        return true;
    } else {
        return false;
    }
}

//定义一个枚举来记录数组的三个状态
enum State { EXIST,//存在 EMPTY,//空 DELETE//删除 };
template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    State _state = EMPTY;//状态为空
};
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};
/* 1. 将 string 类型转换成无符号整形 (BKDR_Hash)
   2. 字符串转换成整形，可以把字符 ascii 码相加即可
   3. 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
   4. 这里我们使用 BKDR 哈希的思路，用上次的计算结果去 乘以一个质数，这个质数一般去 31, 131 等效果会比较好 */
template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        // BKDR
        size_t hash = 0;
        for (auto ch : s) {
            hash += ch;
            hash *= 131;
        }
        return hash;
    }
};

inline unsigned long __stl_next_prime(unsigned long n) {
    // Note: assumes long is at least 32 bits.
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
        6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
        402653189, 805306457, 1610612741, 3221225473, 4294967291
    };
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

namespace open_address//开发定址法
{
    //加上一个仿函数 Hash，用于转换成为无符号整形
    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
    public:
        HashTable() :_tables(__stl_next_prime(0))//给一个 0 去获取>=0 的素数
            , _n(0)//数据个数 {}

        bool Insert(const pair<K, V>& kv) {
            //如果值已经存在
            if (Find(kv.first)) return false;
            //扩容
            // 负载因子 >= 0.7 扩容 n/m 数据个数/表的空间大小
            //为了方便计算分子 n*10
            if (_n * 10 / _tables.size() >= 7) {
                //创建一个新的哈希表 newht 哈希表里本来就有 vector
                HashTable<K, V> newht;
                //*2 是无法一直保持素数的
                //newht._tables.resize(_tables.size() * 2);
                //使用素数表来获取比素数表的值大一点的值
                newht._tables.resize(__stl_next_prime(_tables.size() + 1));
                for (auto& data : _tables) {
                    // 遍历旧表，旧表的数据映射到新表
                    if (data._state == EXIST) {
                        //使用新对象去调用插入，把旧表的数据插入到新表
                        newht.Insert(data._kv);
                    }
                }
                //交换新旧表的空间
                _tables.swap(newht._tables);
            }
            Hash hash;//仿函数，用于转换成为无符号整形
            //插入值之后从起始位置 hash0 去用插入的值对表的大小取模算出值对应的位置
            size_t hash0 = hash(kv.first) % _tables.size();//hash0 是第一次算出来的位置
            size_t hashi = hash0;
            size_t i = 1;
            int flag = 1;
            while (_tables[hashi]._state == EXIST)//如果 hashi 的状态为存在
            {
                //进行线性探测
                //如果到达表的最后一个位置那么就模一下表的空间大小
                hashi = (hash0 + i) % _tables.size();
                ++i;
                //二次探测
                /*hashi = (hash0 + (i*i*flag)) % _tables.size();
                if (hashi < _tables.size()) hashi += _tables.size();
                if (flag == 1) {
                    flag = -1;
                } else {
                    ++i;
                    flag = 1;
                }*/
            }
            //当遇到空的位置就插入
            _tables[hashi].kv = kv;
            _tables[hashi]._state = EXIST;//将插入的位置标记为存在
            ++_n;
            return true;
        }

        HashData<K, V>* Find(const K& key) {
            Hash hash;
            size_t hash0 = hash(key) % _tables.size();
            size_t hashi = hash0;
            size_t i = 1;
            while (_tables[hashi]._state != EMPTY) {
                if (_tables[hashi]._state == EXIST//如果状态是存在并且是那个值
                    && _tables[hashi]._kv.first == key) {
                    return &_tables[hashi];
                }
                // 线性探测
                hashi = (hash0 + i) % _tables.size();
                ++i;
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            auto* ret = Find(key);
            if (ret) {
                ret->_state = DELETE;
                return true;
            }
            return false;
        }

    private:
        vector<HashData<K, V>> _tables;//表的空间大小
        size_t _n; // 记录数据个数
    };
}

//将普通类型转换成无符号整形
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};
/* 1. 将 string 类型转换成无符号整形 (BKDR_Hash)
   2. 字符串转换成整形，可以把字符 ascii 码相加即可
   3. 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
   4. 这里我们使用 BKDR 哈希的思路，用上次的计算结果去 乘以一个质数，这个质数一般去 31, 131 等效果会比较好 */
template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        // BKDR
        size_t hash = 0;
        for (auto ch : s) {
            hash += ch;
            hash *= 131;
        }
        return hash;
    }
};

namespace hash_bucket//哈希桶
{
    template<class K, class V>
    struct HashNode//给一个节点用来挂节点
    {
        pair<K, V> _kv;
        HashNode<K, V>* _next;
        HashNode(const pair<K, V>& kv) :_kv(kv), _next(nullptr) {}
    };

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
        typedef HashNode<K, V> Node;
    public:
        //构造
        HashTable() :_tables(11), _n(0) {}
    private:
        vector<Node*> _tables; // 指针数组
        size_t _n = 0;// 表中存储数据个数
    };
}

bool Insert(const pair<K, V>& kv) {
    Hash hs;
    size_t hashi = kv.first % _tables.size();
    // 头插
    //让新节点变成哈希表里的第一个也就是说要让哈希表里存储新节点的地址
    Node* newnode = new Node(kv);//创建一个新节点 new Node
    //将新节点的下一个节点指向原来的第一个节点的地址
    //第一个节点的地址在哈希表里
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;//再把新节点给与_tables[hashi] 里存储的指针
    ++_n;
    return true;
}

// 负载因子 == 1 时扩容
if (_n == _tables.size()) {
    vector<Node*> newTatble(_tables.size() * 2);
    //遍历旧表
    for (size_t i = 0; i < _tables.size(); i++) {
        Node* cur = _tables[i];
        while (cur) {
            Node* next = cur->_next;
            // 旧表数据头插到新表
            size_t hashi = cur->_kv.first % newTatble.size();
            cur->_next = newTatble[hashi];
            newTatble[hashi] = cur;
            cur = next;
        }
        //交换
        _tables[i] = nullptr;
    }
    _tables.swap(newTatble);
}

Node* Find(const K& key) {
    Hash hash;
    size_t hashi = hash(key) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur) {
        if (cur->_kv.first == key) {
            return &cur->_kv.first;
        } else {
            cur = cur->_next;
        }
    }
    return nullptr;
}

bool Erase(const K& key) {
    Hash hash;
    size_t hashi = hash(key) % _tables.size();
    Node* cur = _tables[hashi];
    Node* prev = nullptr;
    while (cur) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                _tables[hashi] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;
            return true;
        } else {
            prev = cur;
            cur = cur->_next;
        }
    }
    return false;
}

namespace hash_bucket//哈希桶
{
    template<class K, class V>
    struct HashNode//给一个节点用来挂节点
    {
        pair<K, V> _kv;
        HashNode<K, V>* _next;
        HashNode(const pair<K, V>& kv) :_kv(kv), _next(nullptr) {}
    };

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
        typedef HashNode<K, V> Node;
    public:
        //构造
        HashTable() :_tables(11), _n(0) {}

        bool Insert(const pair<K, V>& kv) {
            // 负载因子 == 1 时扩容
            if (_n == _tables.size()) {
                vector<Node*> newTatble(_tables.size() * 2);
                //遍历旧表
                for (size_t i = 0; i < _tables.size(); i++) {
                    Node* cur = _tables[i];
                    while (cur) {
                        Node* next = cur->_next;
                        // 旧表数据头插到新表
                        size_t hashi = cur->_kv.first % newTatble.size();
                        cur->_next = newTatble[hashi];
                        newTatble[hashi] = cur;
                        cur = next;
                    }
                    //交换
                    _tables[i] = nullptr;
                }
                _tables.swap(newTatble);
            }
            size_t hashi = kv.first % _tables.size();
            // 头插
            //让新节点变成哈希表里的第一个也就是说要让哈希表里存储新节点的地址
            Node* newnode = new Node(kv);//创建一个新节点 new Node
            //将新节点的下一个节点指向原来的第一个节点的地址
            //第一个节点的地址在哈希表里
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;//再把新节点给与_tables[hashi] 里存储的指针
            ++_n;
            return true;
        }

        Node* Find(const K& key) {
            Hash hash;
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            while (cur) {
                if (cur->_kv.first == key) {
                    return &cur->_kv.first;
                } else {
                    cur = cur->_next;
                }
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            Hash hash;
            size_t hashi = hash(key) % _tables.size();
            Node* cur = _tables[hashi];
            Node* prev = nullptr;
            while (cur) {
                if (cur->_kv.first == key) {
                    if (prev == nullptr) {
                        _tables[hashi] = cur->_next;
                    } else {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    return true;
                } else {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }

    private:
        vector<Node*> _tables; // 指针数组
        size_t _n = 0;// 表中存储数据个数
    };
}

C++ 哈希表详解：开散列与闭散列

C++ 哈希表详解

1. 哈希的概念

1.1 直接定址法

1.2 哈希冲突

1.3 负载因子

1.4 哈希函数

1.4.1 除法散列法/除留余数法

1.4.2 乘法散列法

1.4.3 全域散列法

1.5 处理哈希冲突

1.5.1 开放定址法（闭散列）

1. 线性探测（挨着查找）

2. 二次探测（跳跃着查找）

3. 双重散列

2. 闭散列实现哈希表

2.1 开发地址法的基础构架

2.2 扩容

2.3 插入

2.4 查找

2.5 删除

2.6 闭散列代码

3. key 不能取模的问题

4. 链地址法（开散列/哈希桶）

4.1 链地址法的基础框架

4.2 插入

4.3 扩容

4.4 查找

4.5 删除

4.6 开散列代码

更多推荐文章

相关免费在线工具

C++ 哈希表详解：开散列与闭散列

C++ 哈希表详解

1. 哈希的概念

1.1 直接定址法

1.2 哈希冲突

1.3 负载因子

1.4 哈希函数

1.4.1 除法散列法/除留余数法

1.4.2 乘法散列法

1.4.3 全域散列法

1.5 处理哈希冲突

1.5.1 开放定址法（闭散列）

1. 线性探测（挨着查找）

2. 二次探测（跳跃着查找）

3. 双重散列

2. 闭散列实现哈希表

2.1 开发地址法的基础构架

2.2 扩容

2.3 插入

2.4 查找

2.5 删除

2.6 闭散列代码

3. key 不能取模的问题

4. 链地址法（开散列/哈希桶）

4.1 链地址法的基础框架

4.2 插入

4.3 扩容

4.4 查找

4.5 删除

4.6 开散列代码

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具