数据结构------哈希

青旅半醒 2022-05-27 22:19 217阅读 0赞

## 哈希的提出 ##

之前我们已经接触过很多的数据结构了，比如线性表，二叉搜索树、AVL树、红黑树、B树等。当我们在这些数据结构中要查找一个元素时，会发现我们需要进行一系列的关键码比较，因为元素在存储结构中的位置与元素的关键码之间不存在直接的对应关系，所以搜索的效率就取决于搜索过程中比较的次数。

那有没有什么查找方法是可以不经过任何比较，一次直接得到要搜索的元素呢？

有一种存储结构，使元素的存储位置与它的关键码之间建立一个确定的对应函数关系 **Hash()**，那么每个元素关键码与结构中的一个唯一的存储位置相对应：  
**Address = Hash(Key)**  
在插入时，根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。 在搜索时，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。这种方法就是哈希方法(Hash Method)，在哈希方法中使用的转换函数叫哈希函数(Hash function)，构造出来的结构叫哈希表(Hash Table)。  
**（注：哈希方法也叫散列方法）**

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

## 哈希函数 ##

从上面的讲解中我们可以发现，哈希表中最重要的就是哈希函数了，那么哈希函数应该如何选取呢？

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

这里我们介绍几种方法：

*  直接定址法
 *  除留余数法
 *  平方取中法
 *  折叠法
 *  数学分析法
 *  随机数法

我们主要来谈谈直接定址法和除留余数法

###### 直接定址法： ######

取关键字的某个线性函数为地址：**Hash(Key)= Key** 或 **Hash(Key)= A\*Key + B**，其中A、B为常数。  
优点：简单，均匀  
缺点：需要事先知道关键字的分布情况  
适合于元素较小而且比较连续的场景

###### 除留余数法： ######

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

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

## 哈希冲突 ##

在理想的情况下，不同的键会被转换为不同的索引值，但在有些情况下我们会发现需要处理多个键被哈希到同一个索引值的情况。这种情况叫做**哈希冲突**(或者说哈希碰撞）  
上一张图帮助大家理解：  
![这里写图片描述][70]

我们会发现不管什么样的哈希函数，都不能避免哈希冲突，那么应该怎么办呢？

#### 解决哈希冲突的方法： ####

**1. 闭散列法(开放定址法)**

它的核心思想就是把发生冲突的元素放到哈希表中的另一个位置。只要哈希表足够大，总能找到空的位置。闭散列法具体又可分为线性探测和二次探测。

###### 线性探测 ######

简单来说线性探测要做的就是把发生冲突的元素插入从当前位置开始后移的第一个空位置。(继续上图)  
比如我们要插入的一组关键码是 \{ 17,34,22,36,24,69,58,19 \}  
我们的哈希函数：**Hash=key%10**

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

线性探测法简单，但是容易产生数据“堆积”，即不同探查序列的关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索时间增加

###### 二次探测 ######

二次探测的大致思想与线性探测相同，不同之处在于后移过程中它移动的大小为后移次数的平方。我们设后移的次数为i。  
**Hi = (H0 + i^2)%m**，**Hi = (H0 - i^2)%m**，i = 1,2,3…，(m-1)/2  
H0是通过散列函数Hash(x)对元素的关键码x进行计算得到的位置，m是表的大小  
还是插入刚刚的元素：  
![这里写图片描述][70 2]

我们会发现，如果插入表中的元素越少，发生冲突的可能性也就比较小，那么这个哈希表我们就不能把它存满，就需要在合适的时候去增容，那么到底改在什么时候增容呢？  
针对闭散列方法(开放定址法)，哈希表有一个载荷因子来解决这个问题

**哈希表的载荷因子α = 插入表中元素个数 / 散列表的长度**

α是散列表装满程度的标志因子。由于表长的定值，α与“填入表中元素个数”成正比，α越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α越小，表明填入表中的元素越少，产生冲突的可能性就越小。  
对于闭散列方法，载荷因子是特别重要的元素，应严格限制在0.7~0.8以下。当载荷因子超出范围时，就应该扩容

**2. 开散列法(开链法)**

开散列法首先对关键码集合用哈希函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点组成 一个向量，因此，向量的元素个数与可能的桶数一致  
简单来说就是：将哈希表变成一个指针数组。每次发生冲突，就把发生冲突的元素链到当前位置下。 (上图)  
同样的关键码和哈希函数  
![这里写图片描述][70 3]

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

## 开散列法和闭散列法的比较 ##

**开散列法**

**优点：**  
①对于数据总数频繁可变的情况，处理的比较好（也就是避免了动态调整的开销） ②由于数据存储在结点中，而结点是动态分配，不会造成内存的浪费，所以尤其适合那种数据本身尺寸（size）很大的情况，因为此时指针的开销可以忽略不计了  
③删除数据时，比较方便，直接通过指针操作即可

**缺点：**  
①存储的数据是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型（比如数组），哈希表的跳转访问会带来额外的时间开销  
②如果所有的 键值对是可以提前预知，并之后不会发生变化时（即不允许插入和删除），可以人为创建一个不会产生冲突的完美哈希函数，此时闭散列的性能将远高于开散列  
③由于使用指针，数据不容易进行序列化操作

**闭散列法**

**优点：**  
①数据更容易进行序列化操作  
②如果数据总数可以预知，可以创建完美哈希函数，此时处理数据的效率是非常高的

**缺点：**  
①存储数据的数目不能超过桶数组的长度，如果超过就需要扩容，而扩容会导致某次操作的时间成本飙升，这在实时或者交互式应用中可能会是一个严重的缺陷  
②使用探测序列，有可能其计算的时间成本过高，导致哈希表的处理性能降低  
③由于数据是存放在桶数组中的，而桶数组必然存在空槽，所以当记录本身尺寸很大并且记录总数规模很大时，空槽占用的空间会导致明显的内存浪费  
④删除数据时，比较麻烦。比如需要删除记录a，记录b是在a之后插入桶数组的，但是和记录a有冲突，是通过探测序列再次跳转找到的地址，所以如果直接删除a，a的位置变为空槽，而空槽是查询记录失败的终止条件，这样会导致记录b在a的位置重新插入数据前不可见，所以不能直接删除a，而是设置删除标记。这就需要额外的空间和操作

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

## 哈希表的实现 ##

我们先用闭散列方法实现

**HashTable.h**

#include <iostream>
    using namespace std;
    #include <stdlib.h>
    
    typedef enum State
    {
        EMPTY,
        EXSIT,
        DELETE
    }State;
    
    template <class K>
    struct Elem
    {
        K _key;
        State _state;
    };
    
    template <class K>
    struct _HashFun
    {
        size_t operator()(const K& key)
        {
            return key;
        }
    };
    //利用模板的特化来解决存储字符串哈希函数的问题
    template <>
    struct _HashFun<string>
    {
    public:
        size_t operator()(const string& str)
        {
            return BKDRHash(str.c_str());
        }
    private:
        //字符串哈希处理函数
        static size_t BKDRHash(const char * str)
        {
            unsigned int seed = 131; // 31 131 1313 13 131 1313 13  
            unsigned int hash = 0;
            while (*str)
            {
                hash = hash * seed + (*str++);
            }
            return(hash & 0x7FFFFFFF);
        }
    };
    //动态版本
    //除留余数法---素数
        template <class K, bool IsLine = true, class _HashFun = _HashFun<K>>
    class HashTable
    {
    public:
    
        HashTable(size_t capacity = 10)
            :_size(0)
        {
            capacity = GetNextPrime(capacity);
            _hashtable = new Elem<K>[capacity];
            _capacity = capacity;
            for (int i = 0; i < capacity; i++)
                _hashtable[i]._state = EMPTY;
        }
    
        bool Insert(const K& key)
        {
            CheckCapacity();
            size_t hashaddr = HashFun(key);
            size_t i = 1;
            while (_hashtable[hashaddr]._state != EMPTY)
            {
                if (_hashtable[hashaddr]._state == EXSIT&&key == _hashtable[hashaddr]._key)
                {
                    return false;
                }
    
                //线性探测
                if (IsLine)
                    LineCheck(hashaddr);
                //二次探测
                else
                    SecondCheck(hashaddr, i++);//加一个模板参数判断决定线性探测还是二次探测
            }
    
            _hashtable[hashaddr]._key = key;
            _hashtable[hashaddr]._state = EXSIT;
            _size++;
            return true;
        }
    
        int Find(const K& key)
        {
            size_t hashaddr = HashFun(key);
            int i = 1;
            while (_hashtable[hashaddr]._state != EMPTY)
            {
                if (_hashtable[hashaddr]._state == EXSIT)
                {
                    if (_hashtable[hashaddr]._key == key)
                        return hashaddr;
                }
                //线性探测
                if (IsLine)
                    LineCheck(hashaddr);
                //二次探测
                else
                    SecondCheck(hashaddr, i++);//加一个模板参数判断该用线性探测还是二次探测
            }
            return -1;
        }
    
        bool Delete(const K& key)
        {
            int ret = Find(key);
            if (ret != -1)
            {
                _hashtable[ret]._state = DELETE;
                --_size;
                return true;
            }
            return false;
        }
        ~HashTable()
        {
            if (_hashtable)
            {
                delete[] _hashtable;
                _size = 0;
                _capacity = 0;
            }
        }
        size_t Size()
        {
            return _size;
        }
        bool Empty()
        {
            return _size == 0;
        }
    private:
    
        void CheckCapacity()
        {
            //负载因子
            if (_size * 10 / _capacity >= 7)
            {
                //增容
                size_t newcapacity = GetNextPrime(_capacity);
                HashTable<K> newHash(newcapacity);//创建一个临时的哈希表
                for (size_t i = 0; i < _capacity; ++i)//搬移旧哈希表中的元素
                {
                    if (_hashtable[i]._state == EXSIT)
                    {
                        newHash.Insert(_hashtable[i]._key);
                    }
                }
                Swap(newHash);
            }
        }
    
        size_t HashFun(const K& key)
        {
            //return key%_capacity;
            _HashFun h;
            return h(key) % _capacity;
        }
        //线性探测
        void LineCheck(size_t& hashaddr)
        {
            ++hashaddr;
            if (hashaddr >= _capacity)
                hashaddr = 0;
        }
        //二次探测
        void SecondCheck(size_t& hashaddr, size_t i)
        {
            hashaddr = hashaddr + ((i << 1) + 1);
            if (hashaddr >= _capacity)
                hashaddr %= _capacity;
        }
    
        void Swap(HashTable<K>& ht)
        {
            swap(_hashtable, ht._hashtable);
            swap(_capacity, ht._capacity);
            swap(_size, ht._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
        };
        size_t GetNextPrime(size_t num)
        {
            for (size_t i = 0; i < _PrimeSize; i++)
            {
                if (_PrimeList[i]>num)
                    return _PrimeList[i];
            }
            return _PrimeList[_PrimeSize - 1];
        }
    
    private:
        Elem<K>* _hashtable;
        size_t _size;
        size_t _capacity;
    };

再来看看开散列的实现方法  
**HashBucket.h**

#include <iostream>
    using namespace std;
    #include <stdlib.h>
    #include <vector>
    
    //利用模板特化实现不同类型的存储
    template <class K>
    struct _HashFun
    {
        size_t operator()(const K& key)
        {
            return key;
        }
    };
    
    template <>
    struct _HashFun<string>
    {
    public:
        size_t operator()(const string& str)
        {
            return BKDRHash(str.c_str());
        }
    private:
        //字符串处理函数
        static size_t BKDRHash(const char * str)
        {
            unsigned int seed = 131; // 31 131 1313 13 131 1313 13  
            unsigned int hash = 0;
            while (*str)
            {
                hash = hash * seed + (*str++);
            }
            return(hash & 0x7FFFFFFF);
        }
    };
    
    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, class V, class _HashFun = _HashFun<K>>
    class HashBucket
    {
        typedef HashNode<K, V> Node;
        typedef HashNode<K, V>* pNode;
    public:
    
        HashBucket(size_t capacity = 10)
            :_size(0)
        {
            _table.resize(GetNextPrime(capacity));
        }
        //插入元素可以重复
        bool InertEqual(const K& key, const V& value)
        {
            CheckCapacity();
    
            size_t bucketNo = HashFun(key);
            pNode cur = _table[bucketNo];
    
            if (cur == NULL)
            {
                _table[bucketNo] = new Node(key, value);
                ++_size;
                return true;
            }
    
            pNode newNode = new Node(key, value);
            newNode->_next = _table[bucketNo];
            _table[bucketNo] = newNode;
            ++_size;
            return true;
        }
        //插入元素不能重复
        bool InertUnique(const K& key, const V& value)
        {
            CheckCapacity();
    
            size_t bucketNo = HashFun(key);
            pNode cur = _table[bucketNo];
    
            if (cur == NULL)
            {
                _table[bucketNo] = new Node(key, value);
                ++_size;
                return true;
            }
            while (cur)
            {
                if (cur->_key == key)
                {
                    return false;
                }
                cur = cur->_next;
            }
            pNode newNode = new Node(key, value);
            newNode->_next = _table[bucketNo];
            _table[bucketNo] = newNode;
            ++_size;
            return true;
        }
        //查找
        pNode Find(const K& key)
        {
            if (_size == 0)
                return NULL;
            size_t addr = HashFun(key);
            pNode cur = _table[addr];
            while (cur)
            {
                if (cur->_key == key)
                    return cur;
                cur = cur->_next;
            }
            return NULL;
        }
        //删除所有的key
        bool DeleteEqual(const K& key)
        {
            size_t bucketNo = HashFun(key);
            pNode cur = _table[bucketNo];
            pNode pre = _table[bucketNo];
            size_t oldsize = _size;
            while (cur)
            {
                if (cur->_key == key)
                {
                    if (_table[bucketNo] == cur)
                    {
                        _table[bucketNo] = cur->_next;
                        delete cur;
                        cur = _table[bucketNo];
                    }
                    else
                    {
                        pre->_next = cur->_next;
                        delete cur;
                        cur = pre->_next;
                    }
                    --_size;
                }
                else
                {
                    pre = cur;
                    cur = cur->_next;
                }
            }
            if (oldsize != _size)
                return true;
            return false;
        }
        //只删除一个key
        bool DeleteUnique(const K& key)
        {
            size_t bucketNo = HashFun(key);
            pNode cur = _table[bucketNo];
            pNode pre = _table[bucketNo];;
            while (cur)
            {
                if (cur->_key == key)
                {
                    if (_table[bucketNo] == cur)
                        _table[bucketNo] = cur->_next;
                    else
                        pre->_next = cur->_next;
                    delete cur;
                    --_size;
                    return true;
                }
                pre = cur;
                cur = cur->_next;
            }
            return false;
        }
    
    
        size_t Size()const
        {
            return _size;
        }
    
        bool Empty()const
        {
            return 0 == _size;
        }
    
        void Clear()
        {
            for (size_t i = 0; i < _table.capacity(); i++)
            {
                pNode cur = _table[i];
                while (cur)
                {
                    _table[i] = cur->_next;
                    delete cur;
                    cur = _table[i];
                    --_size;
                }
            }
        }
    
        ~HashBucket()
        {
            Clear();
        }
    private:
        //增容
        void CheckCapacity()
        {
            if (_size == _table.capacity())
            {
                size_t capacity = GetNextPrime(_table.capacity());
                HashBucket<K, V> newHash(capacity);
    
                for (size_t i = 0; i < _table.capacity(); i++)
                {
                    pNode cur = _table[i];
                    while (cur)
                    {
                        newHash.InertEqual(cur->_key, cur->_value);
                        cur = cur->_next;
                    }
                }
                Swap(newHash);
            }
        }
        //哈希函数
        size_t HashFun(const K& key)
        {
            _HashFun h;
            return h(key) % _table.capacity();
        }
    
        void Swap(HashBucket<K, V>& ht)
        {
            swap(_table, ht._table);
            swap(_size, ht._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
        };
        size_t GetNextPrime(size_t num)
        {
            for (size_t i = 0; i < _PrimeSize; i++)
            {
                if (_PrimeList[i]>num)
                    return _PrimeList[i];
            }
            return _PrimeList[_PrimeSize - 1];
        }
    
    private:
        vector<pNode> _table;
        size_t _size;
    };

[70]: /images/20220528/9115d37f076f451499344ed86d387dc3.png
[70 1]: /images/20220528/81d8158aa1d24b16a5843ddab9f8b197.png
[70 2]: /images/20220528/8d7619f63a9a47a7980aace585f8117a.png
[70 3]: /images/20220528/bda9f499c60642a6aeeb43bcb7dd3ded.png