数据结构:哈希表

哈希概念:

构造一种存储结构,通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。当向该结构中插入元素时,根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。

当先结构中搜索元素时,对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。 该方式即为哈希方法,哈希方法中使用的转换函数称为哈希函数,构造出来的结构称为哈希表。
哈希冲突:不同的关键字通过相同哈希函数计算出相同的哈希地址。

哈希冲突解决方法:
(1)闭散列:

也叫开放地址法,当发生哈希表未被装满,说明在哈希表中必然还有空位置,可以把key存放到表中下一个空位中去。 那如何寻找下一个空余位置呢?

(a)线性探测:线性探测要做的就是把发生冲突的元素插入到从当前位置开始后移动到第一个空位置。

eg:假设哈希表的长度为10,我们有5个数据分别为74,29,39,44,4.用除留余数法插入到哈希表:
这里写图片描述
采用线性探测,实现起来很简单,缺陷是一旦发生哈希冲突,所有的冲突连在一起,容易产生数据“堆积”,即不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要许多次比较,导致搜索效率降低。
调试结果:
这里写图片描述
(b)二次探测 二次探测和线性探测差不多,只是发生冲突后后移的大小为后移次数的平方。
这里写图片描述

调试结果:
这里写图片描述
完整代码:

负载因子: 散列表负载因子定义为:a = 填入表中的元素个数/散列表的长度
a是散列表装满程度的标志因子。表长为定值,a与“填入表中的元素个数”成正比,所以a越大,表明填入表中的元素越多,产生冲突的可能性越大。
开放地址法中,载荷因子是特别重要因素,应严格控制在0.1-0.8.

代码实现:

#include<iostream>
#include<vector>
using namespace std;
enum State
{
    EXIST,//存在
    EMPTY,//空
    DELETE,//删除
};
template<class K,class V>
struct HashNode
{
    K _key;
    V _value;
    State _state;

    HashNode(const K& key=K(),const V& value=V())
        :_key(key)
        ,_value(value)
        ,_state(EMPTY)
    {}
};
template<class K>
struct Hash
{
    size_t operator()(const K& key)
    {
        return key;
    }
};
//模板的特化
template<>
struct Hash<string>
{
    static size_t BKDRHash(const char*str)
    {
        unsigned int seed = 131;
        unsigned int hash = 0;
        while(*str)
        {
            hash=hash*seed+(*str++);
        }
        return(hash &0x7FFFFFF);
    }
    size_t operator()(const string&s)
    {
        return BKDRHash(s.c_str());
    }
};


template<class K,class V,class __HashFunc = Hash<K>>
class HashTable
{
    typedef HashNode<K,V> Node;
public:
    HashTable()
        :_size(0)
    {}
    bool Insert(const K&key,const V&value)
    {
        CheckCapacity();
        if(Find(key))//滤重
        {
            return false;
        }
        size_t i = 1;
        size_t index = HashFunc(key);//生成下标值
        size_t start = index;
        while(_tables[index]._state == EXIST)
        {
            //二次探测
            //index = start+i*i;
            //index %= _tables.size();
            //++i;
            ++index;
            if(index == _tables.size())
            {
                index =0;//当到最后一个位置还没有找到,从第一个位置开始遍历
            }
        }
        _tables[index]._key = key;
        _tables[index]._value = value;
        _tables[index]._state = EXIST;
        _size++;
        return true;
    }
    bool Earse(const K& key)
    {
        Node *tmp = Find(key);
        if(tmp)
        {
            tmp->_state = DELETE;
            --_size;
            return true;
        }
        else
        {
            return false;
        }
    }
    Node* Find(const K& key)
    {
        size_t index = HashFunc(key);
        size_t start = index;
        size_t i = 1;
        while(_tables[index]._state != EMPTY)
        {
            if(_tables[index]._key == key)
            {
                if(_tables[index]._state == EXIST)
                {
                    return &_tables[index];
                }
                else
                {
                    return NULL;
                }
            }
            //二次探测
            index = start + i*i;
            index %= _tables.size();
            ++i;

            if(index == _tables.size())
            {
                index = 0;
            }
        }
        return NULL;
    }
    void CheckCapacity()
    {
        if(_tables.size()==0 || _size*10/_tables.size() >= 7)
        {
            size_t newsize = _tables.size()*2;//扩容两倍
            if(newsize == 0)
            {
                newsize = 10;
            }
            HashTable<K,V,__HashFunc>newht;
            newht._tables.resize(newsize);
            for(size_t i = 0;i < _tables.size();++i)
            {
                if(_tables[i]._state == EXIST)
                {
                    newht.Insert(_tables[i]._key,_tables[i]._value);//将数据插入新空间
                }
            }
            _tables.swap(newht._tables);
        }
    }

    size_t HashFunc(const K&key)
    {
        __HashFunc hf;
        return hf(key)%_tables.size();
    }
protected:
    vector<Node>_tables;
    size_t _size;//有效字段
};
int main()
{
    HashTable<int,int> ht;
    int a[]= {74,29,39,44,4};
    for(size_t i = 0;i<sizeof(a)/sizeof(a[0]);i++)
    {
        ht.Insert(a[i],i);
    }
    ht.Earse(29);
}

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

通常,每个桶对应的链表节点都很少,将n个关键码通过某一个散列函数,存放到散列表的m个桶中,那么每一个桶中链表的平均长度为n/m,以搜索平均长度为n/m的链表代替了搜索长度为n的顺序表,搜索效率快得多。 应用拉链法处理溢出,需要增设链接指针,似乎增加了存储开销,事实上由于开放地址法必须保证大量的空闲空间以确保搜索效率,如二次探测法要求装载因子a<=0.7,而表项所占空间又比指针大的多,所以使用链地址法反而比开地址法节省存储空间。

哈系桶的实现:顺序表+(挂)链表
这里写图片描述
这里写图片描述
代码实现:

#include<iostream>
#include<vector>
using namespace std;
namespace HASH_BUCKET
{
    template<class V>
    struct HashNode
    {
        V _v;
        HashNode<V>* _next;
        //构造函数
        HashNode(const V& v)
            :_v(v)
            ,_next(NULL)
        {}
    };
    template<class K,class V,class KeyOfValue>
    class HashTable
    {
        typedef HashNode<V> Node;
    public:
        //表的初始化
        HashTable()
            :_size(0)
        {}
        bool Insert(const V& v)
        {
            CheckCapacity();
            KeyOfValue kov;
            size_t index = HashFunc(kov(v),_tables.size());
            Node* cur = _tables[index];
            while(cur)
            {
                if(kov(cur->_v) == kov(v))//滤重
                {
                    return false;
                }
                cur = cur->_next;
            }
            Node* node = new Node(v);

            node->_next = _tables[index];
            _tables[index] = node;
            ++_size;

            return true;
        }
        bool Earse(const K& key)
        {
            KeyOfValue kov;
            size_t index = HashFunc(key,_tables.size());
            Node* cur = _tables[index];
            if(cur == NULL)
            {
                return NULL;
            }
            if(kov(cur->_v) == key)
            {
                _tables[index] = cur->_next;
                delete cur;
                return true;
            }
            else//不是头的情况
            {
                Node* prev = cur;
                cur = cur ->_next;
                while(cur)
                {
                    if(kov(cur->_v) == key)
                    {
                        prev->_next = cur->_next;
                        delete cur;
                        return true;
                    }
                    prev = cur;
                    cur = cur->_next;
                }
                return false;
            }
        }

        Node* Find(const K& key)
        {
            size_t index = HashFunc(kov(v),_tables.size());
            Node* cur = _tables[index];
            KeyOfValue kov;
            whiel(cur)
            {
                if(kov(cur->_v)==key)
                {
                    return cur;
                }
                else
                {
                    cur = cur->_next;
                }
            }
            return NULL;
        }
        //扩容
        void CheckCapacity()
        {
            if (_tables.size() == 0)
            {
                _tables.resize(10, NULL);
            }
            //哈希表满的情况(平均每个下面挂了一个)
            else if (_size == _tables.size())
            {
                //创建一个新表,将旧表的数据依次拷贝到新表
                size_t newsize = _tables.size() * 2;
                vector<Node*> newtables;
                newtables.resize(newsize,NULL);
                KeyOfValue kov;
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        //对节点cur在新表中重新定位
                        size_t index = HashFunc(kov(cur->_v),newsize);
                        Node* next = cur->_next;
                        cur->_next = _tables[i];
                        newtables[index] = cur;

                        //对旧表中下一个数据进行插入
                        cur = next;
                    }
                    _tables[i] = NULL;
                }
                //将新表和旧表进行交换
                _tables.swap(newtables);
            }
        }
        //计算下标位置
        size_t HashFunc(const K& key,size_t size)
        {
            return key%size;
        }

    private:
        vector<Node*> _tables;
        size_t _size;
    };
    template<class K>
    struct SetKeyOfValue
    {
        const K& operator()(const K& key)
        {
            return key;
        }
    };
    template<class K,class V>
    struct MapKeyOfValue
    {
        const V& operator()(const pair<K,V>& kv)
        {
            return kv.first;
        }
    };
    void TestHashTable()
    {
        HashTable<int,int,SetKeyOfValue<int>> ht;
        ht.Insert(4);
        ht.Insert(15);
        ht.Insert(14);
        ht.Insert(24);
        ht.Insert(33);
        ht.Insert(55);
        ht.Earse(33);
    }
}
int main()
{
    HASH_BUCKET::TestHashTable();
    return 0;
}
版权声明:本文为zjx624bjh原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zjx624bjh/article/details/80026319

智能推荐

android问题记录

Error: Cannot fit requested classes in a single dex file (# methods: 80441 > 65536) 解决办法: gradle文件的defaultConfig默认配置里面增加...

ROS机器人Diego 1# 利用人工智能 风格迁移技术拍摄不同画风的视频

风格迁移,就是将一种图片的风格迁移到其他图片上,改变其他图片的风格,很好玩的一个人工自能模型,github上已经有很多实现的方法,本文参考https://github.com/hzy46/fast-neural-style-tensorflow 的算法,利用Diego1#的平台实现实时视频的风格转换,先上两张图看效果: 是不是很酷呢,其实实现方法和上篇博文中的原理是一样的,只是把人工智能的算法包装...

数据分析学习总结笔记17:文本分析入门案例实战

文章目录 1 数据准备 2 分词 3 统计词频 4 词云 5 提取特征 6 用sklearn进行训练 1 数据准备 数据样例如下, 数据总量为7.7万+: 本节通过一个实战的例子来展示文本分析的最简单流程。首先设定因变量为原始数据中的"评分"。自变量是"评价内容",这里根据评价内容提取TF-IDF特征。之后,通过评价内容的特征建模预测下整体评分。 以上只是最...

LeetCode 150. 逆波兰表达式求值

题目描述 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。 换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1: 输入:[“2”, “1”, “+”, “3&r...

猜你喜欢

并查集原理及应用

并查集 树形的数据结构,每个集合有其代表节点,代表节点相同的元素属于同一集合。 find:通过查找节点的代表节点,判断节点所属集合。 union:合并两集合,小集合合并到大集合,使用大集合的代表节点。 在find的递归过程中,让路过节点的父节点直接赋值为代表节点,节省下次查找时间,如图所示。 计算岛的个数 遍历二维数组,遇到1时就将所相连的1都改为2,看看遇到多少次1,就是岛的数量。改数时使用回溯...

linux nutch1.0安装配置

1,下载nutch1.0 下载地址:http://archive.apache.org/dist/nutch/,下载这个文件nutch-1.0.tar.gz   2,上传到服务器 上传位置:/home/www/,解压nutch-1.0.tar.gz #tar -xvf nutch-1.0.tar.gz 重命名 #mv nutch-1.0 nutch   3,修改配置文...

如何搭建自己的博客?附加美化

如何搭建自己的blog?附加美化 前言: 之前在腾讯云以学生优惠租了一年的服务器,还买了一年的域名,忽然觉得不能闲置着域名,所以搭建了个博客,过程也遇到了很多的问题,望在此阐述,予以他人帮助,祝好~ 准备工作:使用Xshell连接上Linux服务器,我的是centos系统,方便进行操作。使用Xftp连接上Linux服务器,方便传输文件。 安装apache服务器:yum install httpd ...

rabbitmq五种模式详解(含实现代码)

1.简单模式 当生产端发送消息到交换机,交换机根据消息属性发送到队列,消费者监听绑定队列实现消息的接收和消费逻辑编写.简单模式下,强调的一个队列queue只被一个消费者监听消费. 1.1 结构   生产者:生成消息,发送到交换机 交换机:根据消息属性,将消息发送给队列 消费者:监听这个队列,发现消息后,获取消息执行消费逻辑 1.2应用场景 常见的应用场景就是一发,一接的结构 例如: 手机...

AndroidStudio 常用配置

1. 设置主题&左侧导航栏字体 AndroidStudio->Preferences(下同) 2. 设置字体大小 3. 取消竖线 间距设置大些 4. 控制台字体大小 5. 修改LogCat颜色 LogCat 色值 Verbose BBBBBB Debug 48BB31 Info 0070BB Warn BBBB23 Error FF0006 Assert 8F0005 5. 修改变量...