数据结构-哈希表理解与实现

我会带着你远行 2022-06-01 06:51 213阅读 0赞

#### 一、哈希表的简介 ####

> ##### 1、在我们C++11中的unordered\_set/unordered\_map以及unordered\_multiset/unordered\_multimap底层最主要的实现就是哈希表；而哈希表则是通过关键字(key)按照一定的规律映射到表中的位置。 #####
> 
> ##### 2、最常用构造哈希表的方法： #####
> 
> ##### <1>直接定址法：将关键字通过某个线性函数，算出在表中对应的下标； #####
> 
> ##### <2>除留余数法：取关键字%表长的余数，作为下标，进行数据的写入。 #####

--------------------

#### 二、哈希冲突 ####

##### 有了上面的介绍，应该知道大概是怎么一回事了。也就是说，假如给我们一个键值对，我们就需要利用key的数值按照一定的规律算出该数据在表中的下标，再进行写入。但是会出现一种情况：比如我们按照除留余数法，现在表长为10（下标为0~9）；有两个key值分别为11，21；计算出除留余数的结果都是1，可是下标为1的位置却只有一个，那么到底该谁写入呢？这就是所谓的哈希冲突问题。下面就重点介绍如何解决哈希冲突问题。 #####

--------------------

#### <1>开放定址法。 ####

> ##### **开放定址法分类：** #####
> 
> ##### 1. 线性探测：假如key值对应算出下标为1，且该位置已经有元素，那么就继续向后探测，直到存在一个位置没有数据写入。需要注意的是，当探测到表的最后一个元素时，可将index置为0，再次从头探测。 #####
> 
> ##### 2. 二次探测：将现有的下标值每次挪动2的挪动次数次的次方； #####

![这里写图片描述][SouthEast]

--------------------

#### <2>哈希桶 ####

> ##### 在之前的结构中，我们总是将数据一直按照一定的规律，重新找到一个位置将数据安置下来；但是在哈希桶这种方法中，每个数据都保存在他们算出来的下标中，只不过将表的结构改为了一个指针数组；每个元素底下都是一条链表，将对应的元素链接起来。 #####

![这里写图片描述][SouthEast 1]

--------------------

#### <3>使用素数表 ####

> ##### 保证表的大小都为素数，可有效降低哈希冲突。至于为什么，如果有兴趣可以自行查阅资料。下面的代码中就使用了素数表，给定当前表的大小，返回比当前数大且最差最小的素数。 #####

--------------------

#### <4>控制负载因子 ####

> ##### 负载因子 = 填入表中的元素个数 / 表的长度； #####
> 
> ##### 其实也不难想到，负载因子越接近于0，说明空间浪费越大，但是冲突越小，也就是效率越高；反之同理。但是重要的就是负载因子应该控制到多少才好？一旦负载因子到达这个值，就进行扩容，在保证效率的同时也相对节省内存。 #####
> 
> #### 对于开放定址法，一般严格控制在0.7~0.8之间。 ####

##### 注：在哈希桶中可能会出现一条支链的长度过长，影响搜索效率；有些底层在遇到该类问题时，会将该支链构造为一棵红黑树，这样就会缩小带来的问题。 #####

--------------------

#### 三、时间复杂度 ####

> ##### 对于一般的时间复杂度计算，我们都考虑的是最坏的情况，而在哈希表中则不是，哈希表查找的时间复杂度为O(1)；如此高的效率完全得益于对于结构的优势以及一些情境下优化的保证。 #####

--------------------

#### 接下来分别用代码实现下开放定址法和哈希桶。需要注意的点都在注释中标出。 ####

//开放定址法
    #pragma once
    #include <iostream>
    #include <vector>
    using namespace std;
    
    enum State
    {
        EXIST = 1,  //表示当前位置已有元素
        DELETE = 2, //当前位置内容已被删除
        EMPTY = 3,  //当前位置为空
    };
    
    template <class K, class V>
    struct HashNode
    {
        K _key;
        V _value;
        State _state;
    
        HashNode()
            :_state(EMPTY)
        {}
    };
    
    
    //一些key值类型需要特殊处理
    template <class K>
    struct __HashFunc
    {
        size_t operator()(const K& key)
        {
            return key;
        }
    };
    
    
    template <class K, class V, class _HashFunc = __HashFunc<K>>
    class HashTable
    {
        typedef HashNode<K, V> Node;
    protected:
        vector<Node> _tables;   
        size_t _size;   //元素个数
    
    public:
        HashTable()
            :_size(0)
        {}  
    
        bool Insert(const K& key, const V& value)
        {
            CheckCapacity();
            size_t begin = GetIndex(key);
            size_t index = begin;
            size_t count = 0; //二次探测使用
    
            //开放定址法寻找
            while (_tables[index]._state == EXIST)
            {
                //去重，保证key值唯一
                if (_tables[index]._key == key)
                    return false;
    
                //线性探测
                ++index;
                if (index == _tables.size())
                    index = 0;
    
                //二次探测：已第一次算出的下标作为起点计算
                /*index = hash + (count*count) % _tables.size();
                i++;*/
            }
    
            //找到位置
            _tables[index]._key = key;
            _tables[index]._value = value;
            _tables[index]._state = EXIST;
            _size++;
            return true;
        }
    
        Node* find(const K& key)
        {
            size_t index = GetIndex(key);
            while (_tables[index]._state != EMPTY)
            {
                if (_tables[index]._key == key)
                {
                    if (_tables[index]._state != DELETE)
                        return &(_tables[index]);
                    else
                        return NULL;
                }
    
                ++index;
                if (index == _tables.size())
                    index = 0;
            }
            return false;
        }
    
        bool Remove(const K& key)
        {
            Node* ret = find(key);
            if (ret != NULL)
            {
                ret->_state = DELETE;
                --_size;
                return true;
            }
            return false;
        }
    
    
    protected:
    
        //利用除留余数法
        size_t GetIndex(const K& key)
        {
            _HashFunc func;
            return func(key) % _tables.size();
        }
    
        void CheckCapacity()
        {
            //控制负载因子在0.7
            if (_tables.size() == 0)
            {
                _tables.resize(GetNextPrime(1));
            }
            else if (_size * 10 / _tables.size() >= 7)
            {
                HashTable<K, V> newTable;
                newTable._tables.resize(GetNextPrime(_size));
                for (size_t i = 0; i < _size; ++i)
                {
                    if (_tables[i]._state == EXIST)
                    {
                        newTable.Insert(_tables[i]._key, _tables[i]._value);
                    }
                }
                _tables.swap(newTable._tables);
            }
    
        }
    
        //取下一个素数
        size_t GetNextPrime(size_t size)
        {
            const int _PrimeSize = 28;
            static const unsigned long _PrimeList[_PrimeSize] =
            {
                53ul,         97ul,         193ul,       389ul,       769ul,
                1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
                49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
                1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
                50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
                1610612741ul, 3221225473ul, 4294967291ul
            };
    
            for (int i = 0; i < _PrimeSize; ++i)
            {
                if (_PrimeList[i] > size)
                {
                    return _PrimeList[i];
                }
            }
    
            return _PrimeList[_PrimeSize - 1];
        }
    };

--------------------

//哈希桶
    #pragma once
    #include <vector>
    using namespace std;
    
    template<class K, class V>
    struct HashNode
    {
        K _key;
        V _value;
        HashNode<K, V>* _next;
    
        HashNode(const K& key,const V& value)
            :_key(key)
            ,_value(value)
            ,_next(NULL)
        {}
    };
    
    
    template <class K>
    struct _HashFunc
    {
        size_t operator()(const K& key)
        {
            return key;
        }
    };
    
    template <class K, class V, class __HashFunc =_HashFunc<K>>
    class HashBucket
    {
        typedef HashNode<K, V> Node;
    protected:
        vector<Node*> _tables;
        size_t _size;
    
    public:
        HashBucket()
            :_size(0)
        {}
    
        void Resize(size_t size)
        {
            _tables.resize(GetNextPrime(size));
        }
    
        bool Insert(const K& key,const V& value)
        {
            CheckCapacity();
            size_t index = GetIndex(key, _tables.size());
            Node* cur = _tables[index];
            //确定key唯一
            while (cur)
            {
                if (cur->_key == key)
                    return false;
                cur = cur->_next;
            }
    
            //进行头插
            Node* newNode = new Node(key, value);
            newNode->_next = _tables[index];
            _tables[index] = newNode;
            ++_size;
            return true;
        }
    
        Node* find(const K& key)
        {
            size_t index = GetIndex(key,_tables.size());
            Node* cur = _tables[index];
            while (cur)
            {
                if (cur->_key == key)
                    return cur;
                cur = cur->_next;
            }
            return NULL;
        }
    
    
        bool Remove(const K& key)
        {
            size_t index = GetIndex(key,_tables.size());
            Node* cur = _tables[index];
            Node* prev = NULL;
    
            //先处理头
            if (cur && cur->_key == key)
            {
                _tables[index] = cur->_next;
                delete cur;
                --_size;
                return true;
            }
            //使用替代删除法
            while (cur)
            {
                if (cur->_key == key)
                {
                    prev->_next = cur->_next;
                    delete cur;
                    --_size;
    
                    return true;
                }
                else
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }
    
    
    protected:
    
        void CheckCapacity()
        {
            if (_size == _tables.size())
            {
                vector<Node*> newTable;
                newTable.resize(GetNextPrime(_size), NULL);
                //将旧表中的所有节点插入新表中
                for (size_t i = 0; i < _size; ++i)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;
                        size_t index = GetIndex(cur->_key, newTable.size());
    
                        //进行头插
                        cur->_next = _tables[index];
                        _tables[index] = cur;
    
                        cur = next;
                    }
                }
                _tables.swap(newTable);
            }
        }
    
        size_t GetIndex(const K& key, size_t size)
        {
            __HashFunc func;
            return func(key) % size;
        }
    
        //素数表
        size_t GetNextPrime(size_t size)
        {
            const int _PrimeSize = 28;
            static const unsigned long _PrimeList[_PrimeSize] =
            {
                53ul,         97ul,         193ul,       389ul,       769ul,
                1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
                49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
                1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
                50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
                1610612741ul, 3221225473ul, 4294967291ul
            };
    
            for (int i = 0; i < _PrimeSize; ++i)
            {
                if (_PrimeList[i] > size)
                {
                    return _PrimeList[i];
                }
            }
    
            return _PrimeList[_PrimeSize - 1];
        }
    
        size_t HashFunc(const K& key)
        {
            __HashFunc func;
            return func(key) % _tables.size();
        }
    
    };

[SouthEast]: /images/20220601/4181f753fd3640bb8deb824e5d5bf627.png
[SouthEast 1]: /images/20220601/406409f777134c76ab0cfdfdcf46fa82.png