精华内容
下载资源
问答
  • 哈希之开散列和闭散列
    2020-09-24 10:27:18

    以下内容转载自 https://blog.csdn.net/Yinghuhu333333/article/details/81364739

    目的:实现一种结构,不经过任何比较,一次直接得到想要的元素。通过某种函数使元素的存储位置与它的关键码之间建立一种一一映射的关系。那么就可以在查找时快速的找到需要的元素。


    哈希概念

    哈希之散列方法:

    • 插入元素时:根据需要插入元素的值,通过某种计算得出元素的存储位置,将该元素插入到其对应的位置。
    • 查找元素时:根据需要查找的元素进行某种计算得到其存储位置,将该位置的元素与查找的元素进行比较,若相同则查找成功。

    例如:数据集合为{180,750,460,430,800,600,541}
    哈希函数:Hash(key) = key%m;(m为内存单元的个数)
    假设在该例子中,m为12;
    Hash(180) = 0;
    Hash(750) = 6;
    Hash(460) = 4;
    Hash(430) = 10;
    Hash(800) = 8;
    Hash(603) = 3;
    Hash(541) = 1;
    所以这些数据集合在内存中的存储为:
    这里写图片描述
    可是如果数据有冲突 了应该怎么办???

    哈希冲突

    哈希冲突:对于值不相同的元素但是却有相同的哈希值。
    例如:对于两个元素a,b并且a!=b
    但是Hash(a) == Hash(b);
    不同的元素通过相同的哈希函数得到相同的哈希地址。


    引起哈希冲突的原因:哈希函数设计的不够合理。
    哈希函数的设计原则:

    • 如果哈希表允许容纳的元素个数为m,那么元素的值域为0~m-1。
    • 哈希函数计算出来的地址尽量均匀的分布整个空间之中。

    常见的哈希函数

    • 直接定制法:
      即取元素的某个线性函数为散列地址:Hash(key) = A*key +B;
      例如:找出字符串中只出现一次的字符。时间复杂度为O(N),空间复杂度为:O(1);(就可以使用该方法,开辟一个256个元素的数组,进行统计每个元素出现的次数)
      优点:简单,均匀
      适合于查找比较小而且连续的情况。
    • 除留取余法:(比较常用的方法)
      Hash(key) = key % p;(p <= m && p 质数),m为散列表中允许的地址个数。
    • 平方取中法:
      对数据进行平方,然后取数据的中间3位为哈希地址。
      适合于:不知道数据的分布情况,但是数字又不是很大的情况

    若哈希函数设计的非常合理,那么产生哈希冲突的概率就非常低,但是哈希冲突是无法避免的。


    哈希冲突的处理:
    方法一:
    闭散列(即开放地址法):当发生哈希冲突时,如果该哈希表还没有被填满,那么就把该元素放到哈希表的下一个空闲的位置。
    线性探测法查找下一个位置:
    例如:关键码集合为:{37,25,14,36,49,57,11},设表的长度为12,Hash(key) = key%p(p = 11);
    Hash(37) = 4;
    Hash(25) = 3;
    Hash(14) = 3;
    Hash(36) = 3;
    Hash(49) = 5;
    Hash(57) = 2;
    Hash(11) = 0;
    很明显:这组数据的哈希地址有冲突。
    在插入时,如果该位置已经有元素了,就从该位置起向后找,找到一个空闲的位置就进行插入。
    如下图所示:
    线性探测法
    优点:简单 易懂
    缺点:一旦发生了哈希冲突,所有的冲突连接在一起,很容易产生数据”堆积”。即不同的数据占用可以利用的位置,就使得寻找其余数据的位置需要进行多次比较,就会导致查找的效率降低。


    负载因子
    散列表的负载因子的值为:α = 填入表中的元素个数 / 散列表的长度。
    分析:由于表长是定值,那么α就与”填入表中的元素个数”成正比。所以,α越大,就说明填入表中的元素个数越多,那么产生冲突的可能性就越大;反之,α越小,就说明填入表中的越少,产生的冲突就越小,但是可能浪费的空间就越多。
    对于开放地址法:负载因子特别重要,应该限制在07-0.8之内。若超过0.8,就可能产生冲突的概率非常大,那么CPU缓存不命中率也就越高。


    二次探测法:
    就是当有哈希冲突时,寻找下一个空闲位置时,首先在该位置处加1的平方,若加1的平方的位置处依然有元素,那就加2的平方,知道找到一个空闲的位置为止。


    方法2:开散列法(哈希桶):又名链地址法,先用哈希函数计算每个数据的散列地址,把具有相同地址的元素归于同一个集合之中,把该集合处理为一个链表,链表的头节点存储于哈希表之中。
    例如:还是上面闭散列中的例子,当使用开散列的方法后,其每个元素的存储为下图所示:
    哈希桶

    由此可见:开散列法有效的解决了数据溢出,不过需要增设链接指针,增加了存储的开销。但是,总体而言,效率还是快的多。

    更多相关内容
  • 哈希 unordered系列关联式容器 unordered_map&& unordered_set 关联性容器介绍 介绍 底层结构 哈希概念 哈希冲突 闭散列 闭散列介绍 实现 开散列 介绍 开散列增容机制 实现 开散列和闭散列比较 unordered系列关联式...

    unordered系列关联式容器

    unordered_map&& unordered_set

    关联性容器介绍

    在STL底层map和set使用红黑树封装实现的,而其复杂度为基本为logn因为高度可控,但往后发展还是有大神想出了另一种容器结构也就是哈希。也就是底层用哈希来封装出map和set

    介绍

    1. unordered_map是存储<key, value>键值对的关联式容器,其允许通过keys快速的索引到与其对应的value。
    2. 在unordered_map中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此键关联。键和映射值的类型可能不同。
    3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。
    4. unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭代方面效率较低。
    5. unordered_maps实现了直接访问操作符(operator[]),它允许使用key作为参数直接访问value。
    6. 它的迭代器至少是前向迭代器。
      注意:unordered_map中key是不能重复的,因此count函数的返回值最大为1
      无论是unordered_map/se其使用规则和map和set没有多大差别就是底层实现不同。效率不同。

    底层结构

    哈希概念

    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(N),搜索的效率取决于搜索过程中元素的比较次数。

    理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。

    插入元素:
    根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放

    搜索元素:
    对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功

    该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称散列表)

    例如:
    每次给一个数对其进行取模,得到一个值对其进行插入,有点之前计数排序那意思。
    在这里插入图片描述
    差的元素多了不可避免地就会有重复的字眼。

    哈希冲突

    对于不同关键字取模相同出一样的哈希地址,这个我们叫做哈希冲突。
    通过哈希函数来解决。
    设计原则:

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

    常见哈希函数:直接定制法,除留余数法,平方取中法,折叠法,随机数法,数学分析法。
    经常用的就是前两个

    注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

    闭散列

    闭散列介绍

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

    1.线性探测
    对于已经冲突的关键字,我们对其进行线性查找,通过哈希函数找到对应的位置,若没有就插入,若有就一次往后找空位置插入。
    在这里插入图片描述
    这里就对于散列的每一个位置进行状态的定义,采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素
    在这里插入图片描述

    扩容机制:
    当所有元素插满时候,其状态都为存在那么就无法找出对应空的位置一致循环下去,所以我们要保证闭散列不能为满或者不能使它快满了,在达到一定的比例时,就要对其进行扩容机制。
    在这里插入图片描述

    2.二次探测
    可以通过一次探测得出如果同一块区域有大量的数据堆积在一起,效率会降低,也就是将一个个探测变成次方的查找
    在这里插入图片描述
    研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。
    空间利用率比较低,哈希的缺陷

    实现

    	enum State
    	{
    		EXIST,
    		EMPTY,
    		DELETE,
    	};
    
    	template<class T>
    	struct HashNode
    	{
    		State _state = EMPTY; // 状态
    		T _t;
    	};
    
    	template<class K, class T, class HashFunc = Hash<K>>
    	class HashTable
    	{
    	public:
    		bool Insert(const T& t)
    		{
    			// 负载因子>0.7就增容
    			if (_tables.size() == 0 || _size * 10 / _tables.size() == 7)
    			{
    
    				size_t newsize = GetNextPrime(_tables.size());
    
    
    				HashTable<K, T> newht;
    				newht._tables.resize(newsize);
    				for (auto& e : _tables)
    				{
    					if (e._state == EXIST)
    					{
    						// 复用冲突时探测的逻辑
    						newht.Insert(e._t);
    					}
    				}
    
    				_tables.swap(newht._tables);
    			}
    
    			HashNode<T>* ret = Find(t);
    			if (ret)
    				return false;
    
    
    			size_t start = t % _tables.size();
    			// 线性探测,找一个空位置
    			size_t index = start;
    			size_t i = 1;
    			while (_tables[index]._state == EXIST)
    			{
    				index = start + i;
    				index %= _tables.size();
    
    				++i;
    			}
    
    			_tables[index]._t = t;
    			_tables[index]._state = EXIST;
    			_size++;
    
    			return true;
    		}
    

    如果传入的是个字符串,那么我们就需要将其转成ASC||码进行计算,就需要引入仿函数特化一个结构体如果传入的是string就去调特化的。

    template<class K>
    struct Hash
    {
    	size_t operator()(const K& key)
    	{
    		return key;
    	}
    };
    
    // 特化
    template<>
    struct Hash < string >
    {
    	size_t operator()(const string& s)
    	{
    		size_t hash = 0;
    		for (auto ch : s)
    		{
    			//hash += ch;
    			hash = hash * 131 + ch;
    		}
    
    		return hash;
    	}
    };
    

    当然查找和删除也类似:查找存在并且相等的值,遇到空则失败。删除就得先查找然后设置状态。插入的时候要先对其进行查找如果有了就失败

    开散列

    介绍

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

    在这里插入图片描述

    开散列增容机制

    开散列的扩容机制不会让自己的插入影响,如果通过一个桶中插入的节点过多不回去影响其他的只会影响自己的效率,最好的情况就是每个桶中一个节点就是不需要二次搜索,不会出现哈希冲突。

    实现

    当进入size为0就给第一个素数(这里大神们研究的通过开成某些素数大小的容量不容易冲突),创建一个新对象并将旧表上的点一个个的插入新表当中,然后释放旧表节点并至空。

    pair<Node*, bool> Insert(const T& t)
    		{
    			KeyOfT kot;
    			// 负载因子 == 1时增容
    			if (_size == _tables.size())
    			{
    				size_t newsize = GetNextPrime(_tables.size());
    				vector<Node*> newtables;
    				newtables.resize(newsize, nullptr);
    				for (size_t i = 0; i < _tables.size(); i++)
    				{
    					// 旧表中节点直接取下来挂到新表
    					Node* cur = _tables[i];
    					while (cur)
    					{
    						Node* next = cur->_next;
    						size_t index = HashFunc(kot(cur->_t), newtables.size());
    						// 头插
    						cur->_next = newtables[index];
    						newtables[index] = cur;
    						cur = next;
    					}
    					_tables[i] = nullptr;
    				}
    				newtables.swap(_tables);
    			}
    			size_t index = HashFunc(kot(t), _tables.size());
    			// 查找t在在不在
    			Node* cur = _tables[index];
    			while (cur)
    			{
    				if (kot(cur->_t) == kot(t))
    					return make_pair(cur, false);
    				cur = cur->_next;
    			}
    			Node* newnode = new Node(t);
    			newnode->_next = _tables[index];
    			_tables[index] = newnode;
    			return make_pair(newnode, true);
    		}
    

    开散列和闭散列比较

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

    展开全文
  • 文章目录前言一、闭散列二、开散列1.引入库2.读入数据三、再散列(了解) 前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器...


    一、冲突——概念

    不同关键字通过相同的哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或者哈希碰撞。
    首先,我们要明确一点,由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一个问题,冲突的发生是必然的,我们能做的是尽量降低冲突率。

    二、冲突——避免——哈希函数设计

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

    1.哈希函数设计原则

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

    2.常见哈希函数

    1.直接定制法
    取关键字的某个线性函数为散列地址:Hash(Key)=A*Key+B
    优点:简单、均匀
    缺点:需要事先知道关键字的分布情况
    使用场景:适合查找比较小且连续的情况

    2.除留余数法
    设置列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key)=key%p(p<=m),将关键码转换成哈希地址。
    还有平方取中法、折叠法、随机数法和数学分析法等几种不常用的方法,这里不再作过多阐述。
    注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突。

    二、冲突——解决——闭散列

    1.概念

    当发生哈希冲突时,从发生哈希冲突的位置开始按照某种方式找“下一个”空位置。
    1.通过哈希函数计算哈希地址
    2.插入元素----注意:可能会产生哈希冲突
    在这里插入图片描述

    找“下一个”空位置的方式:

    1.线性探测

    从发生哈希冲突的位置开始,逐个挨着依次往后查找,如果走到空间末尾再从头开始。
    那么我们这里要插入36,求出哈希地址为6,但此位置已经被占据,我们就挨着往后进行查找,走到8号位置发现是空的,插入36即可。
    那么这里有一个问题:我们怎么知道哪个位置有元素,哪个位置没有元素呢?
    所以这里我们要给哈希表格中的每个空间进行状态标记:
    有元素:EXIST 无元素:EMPTY
    在这里插入图片描述
    查找要插入的位置:
    在这里插入图片描述

    但是当删除表格内元素的时候,就会出现一些意外的情况:
    当我们要删除6时,先要计算6的哈希地址,算出来为6号位置,直接将该位置状态修改成EM,但是如果把该位置修改了,就会造成我们后边的36找不到,因为我们要删除36求其哈希地址为6,但是6号位置已经为空了,就不会再往后找了,这样就会导致后期有些元素找不到。
    所以在删除元素时,不能直接将其状态改为EM,得需要再给一个状态DELETE,表明该位置上的元素被删除了,所以把6删完,将其状态改为DELETE,说明该位置之前有元素,只是后来被删除了而已,我们就可以往后查找,就可以找到36。

    但是我们会发现,上面写的程序最终会进入死循环,其实前面这种事有很大问题的,当表格快要存满时,哈希表的效率就会降低,发生冲突的概率也会升高
    比如下图:当我们要在此基础上插入44时,我们需要从四号位置一直走,知道走到3号位置,效率很低了
    在这里插入图片描述
    因此哈希表格当中是不会将元素存满的,那么存多少个才算合适呢?
    存的少了空间利用率不高,存的多了冲突的概率就大。

    负载因子调节:
    散列表中负载因子的定义为:α=填入表中的元素个数 / 散列表的长度
    负载因子越小:存的元素越少,发生冲突的概率越低

    负载因子的冲突率的关系粗略演示:
    在这里插入图片描述
    负载因子应严格限制在0.7~0.8以下,在线性探测中,我们一般情况下规定负载因子为0.75。
    已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中数组的大小。

    优点:
    处理哈希冲突的方式简单—逐个挨着依次往后找

    缺陷:
    容易产生数据的堆积—一旦发生冲突,数据就容易连成一片。
    在这里插入图片描述

    解决方式: 二次探测

    2.二次探测

    线性探测的缺陷就是产生冲突的数据堆积在一块,这与其找下一个空位置有关,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:Hi=(H0+i2)%m,或者:Hi=(H0-i2)%m。 其中:i=1,2,3…,H0是通过散列函数Hash(x)计算出来的哈希地址,m是表的大小。
    如果index越界,接着取模运算

    优点:
    解决了线性探测数据堆积的问题。

    缺陷:
    当表格中的元素不断增多,二次探测可能要找的次数更多
    在这里插入图片描述
    所以二次探测的负载因子可能会被放得很低,比如α=0.5。

    三、冲突——解决——开散列

    1.概念

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

    2.开散列的模拟实现

    1.创造一个不带头的单链表:
        public static class ListNode{
            private int key;
            private int value;
            ListNode next;
    
            public ListNode(int key,int value){
                this.key=key;
                this.value=value;
            }
        }
    

    2.创造一个数组用来存放链表的头结点并定义初始容量

        ListNode[] table;
        int size;
    
        public HashBucket(int initCapacity){
            initCapacity=initCapacity<=0?16:initCapacity;
            table=new ListNode[initCapacity];
        }
    
        private int size(){
            return size;
        }
    

    3.写哈希函数

        private int hashFunc(int key){
            return key%table.length;
        }
    

    4.V put(K key,V value) :插入元素 O(1)

    根据哈希函数找到对应的桶号
    遍历该链表,如果找到相等的就替换value并返回旧的value
    没有相等的则将新的头插在链表中

        public int put(int key,int value){
            //求初始哈希地址
            int hash=hashFunc(key);
            //找到对应的链表
            ListNode cur=table[hash];
            while(cur!=null){
                //相等则替换
                if(key==cur.key){
                    int oldValue=cur.value;
                    cur.value=value;
                    return oldValue;
                }
                cur=cur.next;
            }
            //不相等则头插
            ListNode newNode=new ListNode(key,value);
            newNode.next=table[hash];
            table[hash]=newNode;
            size++;
            return value;
        }
    

    5.V get(Object key) :获取key对应的value O(1)

    根据哈希函数找到对应的桶号
    遍历该桶号所对应的链表,如果key相等返回对应的value,如果没有找到则返回null

        public Integer get(int key){
            int hash=hashFunc(key);
    
            ListNode cur=table[hash];
            while(cur!=null){
                if(cur.key==key){
                    return cur.value;
                }
                cur=cur.next;
            }
            return null;
        }
    

    6.V getOrDefault(Object key,V defaultValue):获取key对应的value,如果没有返回设置的默认值

    根据get方法来写
    如果找到则返回get方法的结果
    未找到则返回默认值

        public int getOrDefault(int key,int defaultValue){
            Integer ret=get(key);
            return ret!=null?ret:defaultValue;
        }
    

    7.V remove(Object key):移除对应元素

    根据哈希函数计算key所在的桶号找到对应链表
    如果链表的第一个就是要删除的,直接将下一个的地址放入对应桶中
    如果是后面的,设置一个prev来标记前一个结点,prev.next=cur.next
    cur.next==null

        public int remove(int key){
            int hash=hashFunc(key);
    
            ListNode cur=table[hash];
            int oldValue=0;
            //第一个就是要删除的
            if(key==cur.key){
                oldValue=cur.value;
                //直接将下一个的地址放在哈希桶中
                table[hash]=cur.next;
                cur.next==null;
            }
            //普遍情况
            //设置prev来标记前一个
            ListNode prev=cur;
            cur=cur.next;
            while(cur!=null){
                if(cur.key==key){
                    oldValue=cur.value;
                    prev.next=cur.next;
                    cur.next=null;
                }
                prev=cur;
                cur=cur.next;
            }
            size--;
            return oldValue;
        }
    

    8.boolean containsKey(Object key):判断是否包含key对应元素 O(1)

    得到key所对应的桶号
    利用之前写过的get(key)方法
    为空说明没找到返回false
    不为空找到,返回true

        public boolean containsKey(int key){
            int hash=hashFunc(key);
            return get(key)==null?false:true;
        }
    

    9.boolean containsValue(Object value) :判断是否包含value对应元素 O(N)

    因为桶中所有元素是根据key联系起来的,与value无关
    所以这里查找value只能采用全部遍历的方法

        public boolean containsValue(int value){
            //遍历桶中所有元素
            for(int i=0;i<table.length;i++){
                ListNode cur=table[i];
                while(cur!=null){
                    if(cur.value==value){
                        return true;
                    }
                    cur=cur.next;
                }
            }
            //遍历所有后没找到
            return false;
        }
    

    10.主方法:

        public static void main(String[] args) {
            HashBucket hb=new HashBucket(10);
    
            int[] array={1,7,6,4,5,9};
            for(int i=0;i<array.length;i++){
                hb.put(array[i],array[i]);
            }
    
            System.out.println(hb.size());
            hb.put(7,8);
            System.out.println(hb.size());
    
            System.out.println(hb.get(7));
    
            System.out.println(hb.getOrDefault(7,7));
    
            System.out.println(hb.getOrDefault(10,10));
    
            System.out.println(hb.containsKey(7));
    
            System.out.println(hb.containsValue(7));
    
            hb.remove(7);
            System.out.println(hb.containsKey(7));
        }
    }
    

    输出结果:
    在这里插入图片描述

    由于我们在查找key时,最多也就是遍历完一个链表,其中中每个链表又不会很长,所以时间复杂度为O(1)
    而在查找value时需要对所有元素都遍历一遍,时间复杂度为O(N)

    哈希桶什么情况下达到最优?

    空间利用率尽可能高:每个桶都将其利用上
    这种状态一旦出现,再继续插入元素,必然会发生冲突

    因此我们可以设置当哈希桶中的元素个数和桶的个数相同时,进行扩容,例如下图:
    在这里插入图片描述
    一般扩容都是按照两倍的方式来的

    代码实现:

        private void checkCapacity(){
            if(size>= table.length){
                int newCapacity=table.length*2;
                ListNode[] newTable=new ListNode[newCapacity];
    
                //逐个桶进行搬移---逐条链表进行搬移
                for(int i=0;i<table.length;i++){
                    ListNode cur=table[i];
                    while(cur!=null){
                        //将cur先从table[i]桶中移除---类似头删
                        table[i]=cur.next;
                        //将cur往newTable中插入
                        int bucketNo=cur.key%newTable.length;
                        newTable[bucketNo]=cur;
                        cur=table[i];
                    }
                }
                table=newTable;
            }
        }
    

    同时在put方法中添加第0步:检查是否需要扩容。

    展开全文
  • 文章目录解决哈希冲突两种常见的方法是:闭散列和开散列闭散列开散列/哈希桶代码实现哈希桶性能分析 解决哈希冲突两种常见的方法是:闭散列和开散列 闭散列 闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未...

    解决哈希冲突两种常见的方法是:闭散列和开散列

    闭散列

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

    1. 线性探测
    比如场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。
    线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
    插入通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素.

    在这里插入图片描述
    采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

    2. 二次探测
    线性探测的缺陷是产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找,因此二次探测为了避免该问题,找下一个空位置的方法为:H_i = (H_0 + i^2 )% m,
    或者:H_i = (H_0 - i^2 )% m。其中:i = 1,2,3…, H_0是通过散列函数Hash(x)对元素的关键码 key进行计算得到的位置,m是表的大小。 对于2.1中如果要插入44,产生冲突,使用解决后的情况为:
    在这里插入图片描述
    研究表明:当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容。
    因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷。

    开散列/哈希桶

    **开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,**具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
    在这里插入图片描述
    通过顺序表和链表实现(顺序表中存储的哈希函数的地址,除留余数法,顺序表的每个位置就是一个桶),开散列中每个桶中放的都是发生哈希冲突的元素。

    冲突严重时的解决办法

    1. 每个桶的背后是另一个哈希表
    2. 每个桶的背后是一棵搜索树

    代码实现哈希桶

    // key-value 模型
    public class HashBucket {
        private static class Node {
            private int key;
            private int value;
            Node next;
    
            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    
        private Node[] array;
        private int size; // 当前的数据个数
        private static final double LOAD_FACTOR = 0.75;
    
        public int put(int key, int value) {
            int index = key % array.length;
    // 在链表中查找 key 所在的结点
    // 如果找到了,更新
    // 所有结点都不是 key,插入一个新的结点
            for (Node cur = array[index]; cur != null; cur = cur.next) {
                if (key == cur.key) {
                    int oldValue = cur.value;
                    cur.value = value;
                    return oldValue;
                }
            }
            Node node = new Node(key, value);
            node.next = array[index];
            array[index] = node;
            size++;
            if (loadFactor() >= LOAD_FACTOR) {
                resize();
            }
            return -1;
        }
    
        private void resize() {
            Node[] newArray = new Node[array.length * 2];
            for (int i = 0; i < array.length; i++) {
                Node next;
                for (Node cur = array[i]; cur != null; cur = next) {
                    next = cur.next;
                    int index = cur.key % newArray.length;
                    cur.next = newArray[index];
                    newArray[index] = cur;
                }
            }
            array = newArray;
        }
    
        private double loadFactor() {
            return size * 1.0 / array.length;
        }
    
        public HashBucket() {
            array = new Node[8];
            size = 0;
        }
    
        public int get(int key) {
            int index = key % array.length;
            Node head = array[index];
            for (Node cur = head; cur != null; cur = cur.next) {
                if (key == cur.key) {
                    return cur.value;
                }
            }
            return -1;
        }
    }
    

    性能分析

    虽然哈希表一直在和冲突做斗争,但在实际使用过程中,我们认为哈希表的冲突率是不高的,冲突个数是可控的,也就是每个桶中的链表的长度是一个常数,所以我们认为哈希表的插入/删除/查找时间复杂度是O(1) 。

    展开全文
  • 闭散列 也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那如何寻找下一个空位置呢? 线性探测 比如 现在需要...
  • -采用闭散列处理哈希冲突问题,不能随便物理删除哈希表当中已有元素,比如如果删除4,44查找起来就会受影响,一次线性探测删除一个元素时候还需要对删除位置进行一个新的标志。 画一张图吧,上面例子里面当中的4,...
  • 闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置, 那么可以把key存放到冲突位置中的“下一个” 空位置中去。 那如何寻找下一个空位置呢? 类的成员变量 : ...
  • 产生原因 在顺序结构或树形结构的数据集合中,... 开散列中增加链表指针,看似比闭散列中多了一个内存开销,但是由于闭散列中存在二次探测,二次探测的负载因子在达到0.5就需要进行扩容,总和来看,开散列更加节省空间
  • 取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关键字的分布情况 使用场景:适合查找比较小且连续的情况 如下这题: 该题直接采用直接定址法,已知该题只包含...
  • 采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的 伪删除法 来删除一个元素...
  • 以上就是哈希的大致分布,如果对于闭散列和开散列还有什么疑问,可以去度娘一下,这里就不详细介绍了,下面请看代码的实现: 闭散列 #pragma once #include #include #include //typedef int ...
  • **unordered系列的关联式容器在前面博客:[unordered系列] 中讲到了,这里我就讲一下: 1)底层的结构——哈希结构和哈希冲突 2)哈希冲突的解决方法——闭散列和[开散列]
  • 哈希(一)闭散列

    千次阅读 2018-05-15 16:11:21
    哈希(一)闭散列法 哈希概念 在二叉树搜索中,我们总是要对数据进行排序然后在根据排序结果进行查找。然而对于某些场景来说,总是要进行多次比较才可以搜索到数据,这样复杂度较高,较为复杂。于是我们想出了...
  • 本文章主要介绍哈希的概念、关于处理哈希表中哈希冲突的闭散列方式以及代码实现其哈希表闭散列方式的插入查找删除操作!
  • 请设计一个整型散列表,散列函数为除留余数法,处理冲突时的探查方法为线性探查法,其中散列表的长度、除留余数法的模和关键码的个数由键盘输入,再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中...
  •  即不同关键字通过相同哈希函数计算出相同的哈希地址,对于哈希冲突的处理方法,通常有两种:闭散列法和开散列法,本文先介绍闭散列法,也叫开放地址法。当发生哈希冲突时,如果哈希表未被装满,说明在...
  • 线性探测-闭散列

    2021-05-27 11:40:31
    闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。 ~ 线性探测:从发生冲突的位置开始,依次向后探测,直到...
  • 闭散列 (开放定址法) 闭散列哈希冲突的解决 当新插入的元素和旧表元素发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。查找下一个空...
  • 通常应用于关键字长度不等时采用此法 注意:当哈希函数设计的越巧妙,越精准,则产生冲突的可能性就会减少很多,但是冲突是不可避免的 哈希冲突的解决 解决哈希冲突的常见方法有:开散列,闭散列闭散列:也叫...
  • 请设计一个整型散列表,散列函数为除留余数法,处理冲突时的探查方法为线性探查法,其中散列表的长度、除留余数法的模和关键码的个数由键盘输入,再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中...
  • 其中,我们最常用的有两种:开散列法、闭散列法。 开散列法 :每个下标对应的元素不是单纯的只放一个元素,而是存放一个链表,将相同余数的元素当做一个结点都放在链表上。(该方法见另一篇博客 开散列实现哈希表 )...
  • 哈希表(闭散列、拉链法--哈希桶)

    千次阅读 2017-02-20 11:03:57
    哈希表,也称散列表,是一种通过key值来直接访问在内存中的存储的数据结构。它通过一个关键值的函数(被称为散列函数)将所需的数据映射到表中的位置来访问数据。
  • 哈希表 - 闭散列

    2018-09-05 21:57:25
    闭散列主要就是需要注意一下“墓碑”的操作,其他的其实都简单。ASL的计算忘了,找了两道题都没算对,这才是我不写的真正原因…代码里是装13用的… #include&lt;bits/stdc++.h&gt; using namespace std; /...
  • 但是无法避免哈希冲突 4、哈希冲突解决 闭散列: **闭散列:**也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。...
  • 哈希表中解决哈希冲突的闭散列 线性探测方法 一个一个去找,找到对应空间位置插入即可 插入: 1、通过哈希函数计算出哈希位置,即元素应该在哪个位置插入 2、如果当前位置为空,则可以插入 3、如果当前位置不为空,...
  • 哈希表—闭散列

    2018-12-14 22:03:12
    闭散列 当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到表中 “下一个” 空位中去( 负载因子a不超过 0.7 ;如果超出必须考虑增容 ) 解决哈希冲突的方法 线性探测...
  • 闭散列法解决冲突 , 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 (1) 采用线性探查法寻找下一个空位 , 画出相应的散列表 , 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索...
  • 哈希表之闭散列

    2020-08-02 21:35:22
    闭散列(即开放地址法):当发生哈希冲突时,如果该哈希表还没有被填满,那么就把该元素放到哈希表的下一个空闲的位置。 代码实现思路: 哈希表结构的封装 首先我们能够知道哈希表是否冲突。我们使用状态标记来...
  • 闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到表中 “下一个” 空位中去 那如何寻找下一个空余位置? 线性探测 设关键码集合为{37, 25, ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,064
精华内容 2,025
关键字:

闭散列

友情链接: electronic-organ-design.zip