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

哈希的提出

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

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

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


哈希函数

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

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

这里我们介绍几种方法:

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

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

直接定址法:

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

除留余数法:

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


哈希冲突

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

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

解决哈希冲突的方法:

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

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

线性探测

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

这里写图片描述

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

二次探测

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

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

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

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

2. 开散列法(开链法)

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


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

开散列法

优点:
①对于数据总数频繁可变的情况,处理的比较好(也就是避免了动态调整的开销) ②由于数据存储在结点中,而结点是动态分配,不会造成内存的浪费,所以尤其适合那种数据本身尺寸(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;
};
版权声明:本文为qq_34021920原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_34021920/article/details/79690490

智能推荐

使用欧几里得算法解决问题——求字符串的最大公因子(力扣第1071题)(JavaScript解法)

1、欧几里得算法的思想 基于辗转相除法的原理,具体做法:用较大数除以较小数,再用出现的余数(第一个余数)去除除数,,再用出现的余数(第二个余数)去除第一个余数,如此仿佛,直到最后一个余数为0 2、算法流程 3、JavaScript实现欧几里得算法 4、使用欧几里得算法解决问题 力扣1071字符串的最大公因子 题目描述: 对于字符串 S 和 T,只有在 S = T + … + T(T ...

spring与redis整合和序列化问题

spring与redis整合 首先用docker下载redis 下载:docker pull redis 运行:docker run -d -p 6379:6379 --name myredis docker.io/redis 连接redis Desktop Manager 然后开始在springboot上开始配置 application.yml: 自动配置好StringRedisTemplate...

CentOS 7配置南大docker镜像

文章目录 CentOS 7配置南大docker镜像 0.帮助页面 1.系统要求 2.卸载旧版本(没有旧版本可跳过) 3.安装方式 4.准备工作 5.可选操作 Stable Test Nightly 6.安装docker引擎 7. (可选)修改配置文件防止与xshell连接冲突 8.启动docker CentOS 7配置南大docker镜像 0.帮助页面 南大docker源:https://mirr...

Qcon演讲纪实:详解如何在实时视频通话中实现AR功能

2018年4月20日-22日,由 infoQ 主办的 Qcon 2018全球软件开发大会在北京如期举行。声网首席 iOS 研发工程师,iOS 端移动应用产品设计和技术架构负责人龚宇华,受邀分享了《基于 ARkit 和 ARcore,在实时视频通话中实现 AR 功能》,在演讲中剖析了 AR 与 VR 差异,ARKit 的工作原理,以及逐步讲解如何基于 ARKit 与声网Agora SDK 创建 AR...

POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4106    Accepted Submission(s): 1947 Probl...

猜你喜欢

使用Breeze.js编写更好的查询

这篇文章是由同行评审Agbonghama柯林斯 。 感谢所有SitePoint的审稿作出SitePoint内容也可以是最好的! 数据量正在迅速发展,他们正在变得越来越复杂,维护。 许多开发人员希望避免由数据问题他们的工作过程中造成的问题和头痛。 一个使我们的工作更轻松的图书馆是Breeze.js 。 在这篇文章中,我们将讨论我们如何能够写出更好的查询与Breeze.js。 但是首先,我们应该知道什...

Netty框架构建Nio编程

~~~ 随手点赞,养成习惯 ~~~ 为什么选择Netty框架 Netty是业界最流行的NIO框架之一,它的健壮性、功能、性能、可定制性和可扩展性在同类框架中都是首屈一指的。 优点: ① API使用简单,开发门槛低 ②功能强大,预置了多种编解码功能,支持多种主流协议 ③ 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展; ④性能高,通过与其他业界主流的NIO框架对比,Nett...

【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description Solution 首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],...

【String-easy】541. Reverse String II 反转的元素,有反转个数和间隔

1. 题目原址 https://leetcode.com/problems/reverse-string-ii/ 2. 题目描述 3. 题目大意 给定一个字符串,和字符串的间隔k, 这个k表示每k个数反转一次,然后再间隔k个元素再反转k个元素。 4. 解题思路 只要按照间隔去反转就可以了。然后间隔k个元素不反转是通过让i每次递增 2*k完成的。 5. AC代码 6. 相似题型 【1】344. Re...

【C语言笔记结构体】

我们都知道C语言中变量的类型决定了变量存储占用的空间。当我们要使用一个变量保存年龄时可以将其声明为int类型,当我们要使用一个变量保存某一科目的考试成绩时可以将其声明为float。 那么,当我们要做一个学生信息管理系统时,需要保存学生的姓名、学号、年龄等信息,该怎么做呢? 如当要保存三个学生的信息时, 方法一是: 方法二是: 显然,方法二跟更清晰,因为它把name、num、age都集成在一个模板,...