哈希（unordered_map、unordered_set）

芝士就是菜

发布于 2023-04-20 19:12:06

3440

发布于 2023-04-20 19:12:06

文章被收录于专栏：芝士就是菜芝士就是菜

unordered系列关联式容器

内部是无序的，查询很快

几个函数说明：

函数声明	功能介绍
operator[]	返回与key对应的value值
bucket_count()	返回桶的个数
size_t bucket_size(size_t n)const	返回n号桶有效元素的个数
size_t bucket(const K& key)	返回元素key对应的桶号

底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

概念

通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

例如：数据集合{1，7，6，4，5，9} 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小

哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希函数

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。

哈希函数设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单

除留余数法

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

字符串哈希算法

解决哈希冲突

闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置

线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低

二次探测

每次平方的探测：hash+i^2 (i>=0)

负载因子

负载因子：填入表中元素个数 / 散列表的长度

负载因子越小越不容易冲突，但是空间利用率比较低，一般设置0.7左右

代码

namespace CloseHash
{
    enum State
    {
        EXIST,
        DELETE,
        EMPTY
    };
    template <class K, class V>
    struct HashData
    {
        std::pair<K, V> _kv;
        State _state = EMPTY;
    };

    template <class K>
    struct HashFunc
    {
        size_t operator()(const K &key)
        {
            return (size_t)key;
        }
    };

    template <>
    struct HashFunc<string>
    {
        size_t operator()(const string &key)
        {
            size_t val = 0;
            for (auto ch : key)
            {
                val *= 131;
                val += ch;
            }

            return val;
        }
    };

    template <class K, class V, class Hash = HashFunc<K>>
    class HashTable
    {
    public:
        bool insert(const pair<K, V> &data)
        {
            if (find(data.first))
            {
                return false;
            }

            if (_tables.size() == 0 || _size * 10 / _tables.size() >= 7)
            {
                size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                HashTable<K, V, Hash> newHT;
                newHT._tables.resize(newSize);
                for (auto e : _tables)
                {
                    if (e._state == EXIST)
                    {
                        newHT.insert(e._kv);
                    }
                }

                _tables.swap(newHT._tables);
            }

            Hash hash;
            size_t hashi = hash(data.first) % _tables.size();

            while (_tables[hashi]._state == EXIST)
            {
                hashi++;
                hashi %= _tables.size();
            }

            _tables[hashi]._kv = data;
            _tables[hashi]._state = EXIST;
            _size++;

            return true;
        }

        HashData<K, V> *find(const K &key)
        {
            if (_tables.size() == 0)
            {
                return nullptr;
            }
            Hash hash;
            size_t start = hash(key) % _tables.size();
            size_t hashi = start;
            while (_tables[hashi]._state != EMPTY)
            {
                if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
                {
                    return &_tables[hashi];
                }

                hashi++;
                hashi %= _tables.size();

                if (hashi == start)
                {
                    break;
                }
            }

            return nullptr;
        }

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

        void print()
        {
            for (size_t i = 0; i < _tables.size(); i++)
            {
                if (_tables[i]._state == EXIST)
                {
                    printf("[%llu:%d] ", i, _tables[i]._kv.first);
                }
                else
                {
                    printf("[%llu:*] ", i);
                }
            }
            cout << endl;
        }

    private:
        vector<HashData<K, V>> _tables;
        size_t _size = 0;
    };

    void test1()
    {
        int a[] = {1, 11, 4, 15, 26, 7, 44};
        HashTable<int, int> ht;
        for (auto e : a)
        {
            ht.insert(make_pair(e, e));
        }
        ht.print();

        ht.erase(4);

        cout << ht.find(44)->_kv.first << endl;
        cout << ht.find(4) << endl;
        ht.print();
    }
}

开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

开散列闭散列比较

应用链地址法（开散列）处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

unordered_map和unordered_set封装

hash表（开散列）

几个点：

模板类，第一个模板参数是K，第二个参数T，上层决定这个T是什么
传入仿函数KeyOfT，这个可以从T类型中取K
insert插入，返回值设为迭代器和bool的键值对
迭代器（一个是节点指针，一个是哈希表指针）
迭代器用了哈希表，需要在迭代器前面进行哈希表的声明
迭代器有哈希表的指针，所以要将迭代器类，声明为哈希表类的友元

#pragma once

template <class K>
struct HashFunc
{
    size_t operator()(const K &key)
    {
        return (size_t)key;
    }
};

template <>
struct HashFunc<string>
{
    size_t operator()(const string &key)
    {
        size_t val = 0;
        for (auto ch : key)
        {
            val *= 131;
            val += ch;
        }

        return val;
    }
};

namespace OpenHash
{

    template <class T>
    struct HashData
    {
        T _data;
        HashData<T> *_next;
        HashData(const T &data)
            : _data(data), _next(nullptr)
        {
        }
    };

    template <class K, class T, class Hash, class KeyOfT>
    class HashTable;

    template <class K, class T, class Hash, class KeyOfT>
    struct __HashIterator
    {
        typedef HashData<T> Node;
        typedef HashTable<K, T, Hash, KeyOfT> HT;
        typedef __HashIterator<K, T, Hash, KeyOfT> self;

        Node *_node;
        HT *_pht;

        __HashIterator(Node *node, HT *pht)
            : _node(node), _pht(pht)
        {
        }

        T &operator*()
        {
            return _node->_data;
        }

        T *operator->()
        {
            return &_node->_data;
        }

        self &operator++()
        {
            if (_node->_next)
            {
                // 如果当前桶的下一个不为空，直接走到下一个位置
                _node = _node->_next;
            }
            else
            {
                // 说明当前位置为空，要找下一个不为空的桶
                Hash hash;
                KeyOfT kot;
                size_t i = hash(kot(_node->_data)) % _pht->size();
                ++i;
                for (; i < _pht->size(); ++i)
                {
                    if (_pht->_tables[i])
                    {
                        _node = _pht->_tables[i];
                        break;
                    }
                }

                if (i == _pht->size())
                {
                    _node = nullptr;
                }
            }

            return *this;
        }

        bool operator!=(const self &s) const
        {
            return _node != s._node;
        }
        bool operator==(const self &s) const
        {
            return _node == s._node;
        }
    };

    template <class K, class T, class Hash, class KeyOfT>
    class HashTable
    {
        friend struct __HashIterator<K,T,Hash,KeyOfT>;

    public:
        typedef HashData<T>
            Node;
        typedef __HashIterator<K, T, Hash, KeyOfT> iterator;

        iterator begin()
        {
            for (size_t i = 0; i < size(); i++)
            {
                if (_tables[i])
                {
                    return iterator(_tables[i], this);
                }
            }

            return end();
        }

        iterator end()
        {
            return iterator(nullptr, this);
        }

        inline size_t __stl_next_prime(size_t n)
        {
            static const size_t __stl_num_primes = 28;
            // 按素数，扩容，stl源码中
            static const size_t __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};

            for (size_t i = 0; i < __stl_num_primes; ++i)
            {
                if (__stl_prime_list[i] > n)
                {
                    return __stl_prime_list[i];
                }
            }

            return -1;
        }

        ~HashTable()
        {
            for (size_t i = 0; i < _tables.size(); i++)
            {
                Node *cur = _tables[i];
                while (cur)
                {
                    Node *next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }
        pair<iterator, bool> insert(const T &data)
        {
            KeyOfT kot;
            Hash hash;

            iterator ret = find(kot(data));

            if (ret != end())
            {
                return make_pair(ret, false);
            }
            if (_tables.size() == _size)
            {
                // size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();
                vector<Node *> newTables;
                newTables.resize(__stl_next_prime(_tables.size()), nullptr);
                for (size_t i = 0; i < _tables.size(); i++)
                {
                    Node *cur = _tables[i];
                    while (cur)
                    {
                        Node *next = cur->_next;
                        size_t hashi = hash(kot(cur->_data)) % newTables.size();
                        cur->_next = newTables[hashi];
                        newTables[hashi] = cur;
                        cur = next;
                    }

                    _tables[i] = nullptr;
                }

                _tables.swap(newTables);
            }

            size_t hashi = hash(kot(data)) % _tables.size();
            Node *newNode = new Node(data);
            newNode->_next = _tables[hashi];
            _tables[hashi] = newNode;
            ++_size;

            return make_pair(iterator(newNode, this), true);
        }

        iterator find(const K &key)
        {
            Hash hash;
            KeyOfT kot;
            if (_tables.size() == 0)
                return end();
            size_t hashi = hash(key) % _tables.size();

            Node *cur = _tables[hashi];
            while (cur)
            {
                if (kot(cur->_data) == key)
                {
                    return iterator(cur, this);
                }

                cur = cur->_next;
            }

            return end();
        }

        bool erase(const K &key)
        {
            if (_tables.size() == 0)
            {
                return false;
            }
            Hash hash;
            size_t hashi = hash(key) % _tables.size();

            Node *cur = _tables[hashi];
            Node *parent = nullptr;
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    // 1、头删
                    // 2、中间删

                    if (parent == nullptr)
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else
                    {
                        parent->_next = cur->_next;
                    }
                    delete cur;

                    return true;
                }
                parent = cur;
                cur = cur->_next;
            }

            return false;
        }

        size_t size()
        {
            return _tables.size();
        }

        // 桶的个数
        size_t bucket_num()
        {
            size_t num = 0;
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                if (_tables[i])
                {
                    ++num;
                }
            }
            return num;
        }

        size_t maxbucket_lenth()
        {
            size_t maxlen = 0;
            for (size_t i = 0; i < size(); i++)
            {
                size_t len = 0;
                Node *cur = _tables[i];
                while (cur)
                {
                    len++;
                    cur = cur->_next;
                }

                if (len > maxlen)
                {
                    maxlen = len;
                }
            }

            return maxlen;
        }

    private:
        vector<Node *> _tables;
        size_t _size = 0;
    };
}

unordered_map

unordered_map的底层是哈希表，第二个模板参数传个pair<K,V>，同时要配对应的仿函数，返回first

#pragma once

#include "hash.h"

namespace st
{
    template <class K, class V, class Hash = HashFunc<K>>
    class unordered_map
    {
        struct KeyOfT
        {
            const K &operator()(const pair<K, V> &kv)
            {
                return kv.first;
            }
        };

    public:
        typedef typename OpenHash::HashTable<K, pair<K, V>, Hash, KeyOfT>::iterator iterator;

        iterator begin()
        {
            return _ht.begin();
        }

        iterator end()
        {
            return _ht.end();
        }

        pair<iterator, bool> insert(const pair<K, V> &kv)
        {
            return _ht.insert(kv);
        }

        V &operator[](const K &key)
        {
            pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));
            return ret.first->second;
        }

    private:
        OpenHash::HashTable<K, pair<K, V>, Hash, KeyOfT> _ht;
    };

    void test()
    {
        unordered_map<string, int> countMap;
        string arr[] = {"a", "a", "b", "a", "b", "c", "c", "c", "d", "d", "d"};
        for (auto e : arr)
        {
            countMap[e]++;
        }

        for (auto &kv : countMap)
        {
            cout << kv.first << ":" << kv.second << endl;
        }
    }
}

unordered_set

unordered_set的底层也是哈希表，第二个模板参数传个K，同时要配对应的仿函数，返回K就好了

#pragma once

#include "hash.h"

namespace st
{
    template <class K, class Hash = HashFunc<K>>
    class unordered_set
    {
        struct KeyOfT
        {
            const K &operator()(const K& key)
{
                return key;
            }
        };

    public:
        typedef typename OpenHash::HashTable<K, K, Hash, KeyOfT>::iterator iterator;

        iterator begin()
{
            return _ht.begin();
        }

        iterator end()
{
            return _ht.end();
        }

        pair<iterator, bool> insert(const K& key)
        {
            return _ht.insert(key);
        }

    private:
        OpenHash::HashTable<K, K, Hash, KeyOfT> _ht;
    };

    void test_set()
{
        unordered_set<string> s;
        string arr[] = {"a", "a", "b", "a", "b", "c", "c", "c", "d", "d", "d"};
        for(auto e: arr)
        {
            s.insert(e);
        }

        for(auto e: s)
        {
            cout << e << endl;
        }
    }
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-12-24，如有侵权请联系 cloudcommunity@tencent.com 删除

存储