- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
。
实现语言:C++ 。
散列表 ,英文名称为Hash Table,又称 哈希表 、杂凑表等.
线性表和树表的查找是通过 比较关键字 的方法,查找的效率取决于关键字的比较次数.
而散列表是 根据关键字直接访问 的数据结构。散列表通过散列函数将关键字 映射 到存储地址,建立了关键字和存储地址之间的一种直接映射关系.
例如:关键字集key = (17, 24, 48, 25),散列函数H(key) = key % 5,散列函数将关键字映射到存储地址下标,将关键字存储到散列表的对应位置.
理想情况下,散列表查找的时间复杂度是O(1)。但是,散列函数可能会把两个或两个以上的关键字映射到同一地址,发生“ 冲突 ” , 发生冲突的不同关键字称为“ 同义词 ”,也就是具有相同函数值的关键字.
接上例,如果13也要存入散列表,就会和48产生冲突:
所以,使用散列表需要解决好两个问题:构造合适的散列函数,以及制定一个好的解决冲突的方案.
在构造散列函数时需要考虑诸多因素:执行速度、关键字长度、散列表大小、关键字的分布情况、查找频率等.
根据元素集合的特性构造,我们对散列函数有以下要求:
常见的构造方法有:直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机数法.
以关键码key的某个线性函数值作为散列地址 。
Hash(key) = a * key + b (a,b为常数) 。
优点是线性关系,不会产生冲突。但是要占用连续的地址空间,空间效率低下.
适合查找表较小且连续的情况.
例如:使用直接定址法存储序列 {100, 300, 500, 700, 800, 900},选择散列函数 Hash(key) = key / 100 (a=1/100, b=0) 。
此方法是最常用的散列函数构造方法 。
Hash(key) = key mod p (p是一个整数) 。
关键:如何选取合适的p?
技巧:设表长为m,取p≤m,且p为 质数 。
例:{15, 23, 27, 38, 53, 61, 70},散列函数 Hash(key) = key mod 7 。
如果关键字是位数较多的数字(比如手机号),且这些数字部分存在相同规律,则可以采用抽取剩余不同规律部分作为散列地址.
比如手机号前三位是接入号,中间四位是 HLR 识别号,只有后四位才是真正的用户号。也就是说,如果手机号作为关键字,那么极有可能前 7 位是相同的,此时我们选择后四位作为散列地址就是不错的选择。同时,对于抽取出来的数字,还可以再进行反转、右环位移、左环位移等操作,目的就是为了提供一个能够尽量合理地将关键字分配到散列表的各个位置的散列函数.
数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀,就可以考虑用这个方法.
以关键字平方的中间位数作为散列地址.
比如假设关键字是 4321,那么它的平方就是 18671041,抽取中间的 3 位就可以是 671,也可以是 710,用做散列地址.
适合于不知道关键字的分布,而位数又不是很大的情况.
折叠法是将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够时可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址.
比如假设关键字是 9876543210,散列表表长为三位.
有时可能这还不能够保证分布均匀,那么也可以尝试从一端到另一端来回折叠后对齐相加,比如将 987 和 321 反转,再与 654 和 0 相加,变成 789+654+123+0=1566,此时散列地址为 566.
折叠法事先不需要知道关键字的分布,适合关键字位数较多的情况.
选择一个随机数,取关键字的随机函数值作为它的散列地址:
hash(key) = random(key) 。
当关键字的长度不等时采用这个方法构造散列函数是比较适合的.
基本思想: 有冲突时就去寻找 下一个 空的散列地址,只要散列表足够大,空的散列地址总能找到,并将数据元素存入.
常用的开放定址法有线性探测法、二次探测法、伪随机探测法等.
3.1.1 线性探测法 。
Hi = (Hash(key) + di) mod m,(1 ≤ i ≤ m) 。
其中,m为散列表长度, di = i (i为1,2,...,m-1 线性序列) 。
例:关键码集为{47, 7, 29, 11, 16, 92, 22, 8, 3},散列表长度为m=11,散列函数为Hash(key)=key mod 11,使用线性探测法处理冲突,存入过程如下:
3.1.2 二次探测法 。
增量序列di为1 2 ,-1 2 ,2 2 ,-2 2 ,...,q 2 二次序列 。
同样是上边的例子,使用二次探测法处理冲突,存入过程如下:
注意: 二次探测法是跳跃式探测,效率较高,但是会出现命名有有空间却探测不到的情况,因而存储失败,而线性探测只要有空间就一定能探测到.
3.1.3 伪随机探测法 。
增量序列di为伪随机数 。
其存入原理和上边两种方法一致,这里不多做介绍.
基本思想: 将相同散列地址的记录(即同义词)链成一单链表.
m个散列地址就是m个单链表 ,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构.
例如:关键字为{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79},散列函数为Hash(key) = key mod 13,使用链地址法存储如下所示:
链地址法建立散列表的步骤:
优点:
就是同时构造多个不同的哈希函数:
H i = Hash i (key) i= 1,2,3 ... k; 。
当H 1 = Hash 1 (key) 发生冲突时,再用H 2 = Hash 2 (key) 进行计算,直到冲突不再产生,这种方法不易产生聚集,但是增加了计算时间.
将哈希表分为公共表和溢出表,当溢出发生时,将所有溢出数据统一存放到溢出区.
给定查找值k,查找过程如图所示:
散列表的查找效率分析 。
一般我们使用 平均查找长度ASL 来衡量查找效率,散列表ASL的值取决于: 散列函数、处理冲突的方法、散列表的装填因子α (α = 表中填入的记录数 / 哈希表的长度,α越大,表中记录数越多,发生冲突的可能性就越大,查找对比次数就越多).
线性探测法:ASL ≈ 1 / 2 * (1 + 1 / (1 - α)) 。
拉链法:ASL ≈ 1 + α / 2 。
随机探测法:ASL ≈ -1 / α * ln(1 - α) 。
例: 对于关键字集{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79},n=12,散列函数为:H(key) = key mod 13,散列表表长为m = 16,设每个记录的查找概率相等。则使用不同查找算法的平均查找效率如下:
线性探测法:ASL ≈ 1 / 2 * (1 + 1 / (1 - 0.75)) = 2.5 (装填因子α = n / m = 0.75) 。
拉链法:ASL ≈ 1 + 0.75 / 2 = 1.375 。
随机探测法:ASL ≈ -1 / α * ln(1 - α) = 1.85 。
对比无序表查找和有序表折半查找:
无序表:ASL = (n +1) / 2 = 6.5 。
有序表折半查找:ASL = lg 2 (n + 1) - 1 = 2.7 。
总结以下几点:
#include <iostream> #include <cstring> using namespace std; #define m 15 // 哈希表的表长 #define NULLKEY 0 // 单元为空的标记 int HT[m], HC[m]; // 哈希函数 int H(int key) { return key % 13; } // 线性探测 int LineDetect(int HT[], int H0, int key, int& cnt) { int Hi; for (int i = 0; i < m; i++) { cnt++; Hi = (H0 + i) % m; // 按照线性探测法计算下一个哈希地址Hi if (HT[Hi] == NULLKEY || HT[Hi] == key) return Hi; // 若单元Hi为空,则所查元素不存在 } return -1; } // 二次探测 int SecondDetect(int HT[], int H0, int key, int& cnt) { int Hi; for (int i = 1; i <= m / 2; ++i) { int i1 = 1 * i; int i2 = -i1; cnt++; Hi = (H0 + i1) % m; // 按照二次探测法去计算下一个哈希地址 if (HT[Hi] == NULLKEY || HT[Hi] == key) // 若单元Hi为空或者查找成功 return Hi; cnt++; Hi = (H0 + i2) % m; // 按照二次探测法去计算下一个哈希地址 if (Hi < 0) Hi += m; if (HT[Hi] == NULLKEY || HT[Hi] == key) // 若单元Hi为空或者查找成功 return Hi; } return -1; } // 哈希表中查找关键字key void SearchHash(int HT[], int key) { int H0 = H(key); // 计算哈希地址 int Hi, cnt = 1; if (HT[H0] == NULLKEY) cout << "查找失败" << endl; else if (HT[H0] == key) cout << "查找成功。" << "在第" << H0 + 1 << "位置。" << "比较次数:" << cnt << endl; else { Hi = LineDetect(HT, H0, key, cnt); // Hi = SecondDetect(HT, H0, key, cnt); if (HT[Hi] == key) cout << "查找成功。" << "在第" << H0 + 1 << "位置。" << "比较次数:" << cnt << endl; else cout << "查找失败。比较次数:" << cnt << endl; } } // 插入元素 bool InsertHash(int HT[], int key) { int H0 = H(key); // 根据哈希函数H(key)计算哈希地址 int Hi, cnt = 1; if (HT[H0] == NULLKEY) { HC[H0] = 1; // 统计比较次数 HT[H0] = key; // 放入H0中 return 0; } else { Hi = LineDetect(HT, H0, key, cnt); // Hi = SecondDetect(HT, H0, key, cnt); if (Hi != -1 && HT[Hi] == NULLKEY) { HC[Hi] = cnt; // 统计比较次数 HT[Hi] = key; // 放入H0中 return 1; } } return 0; } void print(int HT[]) { for (int i = 0; i < m; i++) cout << HT[i] << "\t"; cout << endl; } int main() { int x; memset(HT, 0, sizeof(HT)); memset(HC, 0, sizeof(HC)); print(HT); cout << "输出12个关键字,存入哈希表中:" << endl; for (int i = 0; i < 12; i++) { cin >> x; if (!InsertHash(HT, x)) { cout << "创建哈希表失败!" << endl; return 0; } } cout << "输出哈希表:" << endl; print(HT); print(HC); cout << "输入要查找的关键字" << endl; cin >> x; SearchHash(HT, x); return 0; } // 测试数据1:14 36 42 38 40 15 19 12 51 68 34 25 // 测试数据2:14 36 42 38 40 15 19 12 51 68 34 18
1. 数据结构与算法基础(青岛大学王卓) 。
2. 数据结构—— 构造散列函数的六种方法【直接定址法-数字分析法-平方取中法-折叠法-除留余数法-随机数法】 。
3. 哈希冲突常用解决方法 。
4. 书籍:算法训练营 。
最后此篇关于【数据结构与算法学习】散列表(HashTable,哈希表)的文章就讲到这里了,如果你想了解更多关于【数据结构与算法学习】散列表(HashTable,哈希表)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我有一个响应移动的应用程序。 监听器似乎在一个 Action 中被调用多次,即如果我将应用程序从监视器的一部分拖到另一部分。 发生这种情况时,我将一些数据存储到哈希表中。每次存储数据时,我都需要存储到
我想对 SAS 哈希表中存储桶的定义进行一些说明。问题正是关于 hashexp 参数。 根据 SAS DOC,hashexp 是: hash对象的内表大小,其中hash表的大小为2n。 HASHEXP
我有许多以整数为键的哈希表,我希望能够在我的 Freemarker 模板中迭代它们,但是,似乎没有任何效果。 我尝试了 Freemarker iterating over hashmap keys 中
C# 中的你好我有两个哈希表对象,其键/值对相同我想检查两个哈希表键/值对是否相等.. 我尝试了 hashtable 的 equal 方法但没有成功 我应该用 foreach 检查所有项目吗? 谢谢
我不太熟悉 HashTable 和使用 HashTable 动态制作 RadioButtons。我可以使用 HashTable 制作 RadioButtons,但无法获取 RadioButtons i
我想知道是否可以这样: Hashtable myhash =new Hashtable(); 其中 String 是一个单词,整数[]是一个包含两个位置的数组,第一个位置是行号,第二个位置是该单词出现
我很好奇为什么会发生错误: scala> import collection.JavaConverters._ import collection.JavaConverters._ scala> va
我在 Hashtable> 中编码了一些对象属性,其中: Integer是主要的关键Hashtable (代表对象编号) 每个 Hashtable分别代表属性name (String)和属性(prop
我说 .Net Hashtable 不同步而 Java Hashtable 同步对吗?并且同时一个Java HashMap 不同步并且有更好的性能? 我正在重写一个在 C# 中大量使用 HashMap
我有一个来自 .Net 的对象,它有一个 SyncHashTable 类型的属性,在没有抛出异常的情况下无法查看。 在线复现: [HashTable]::Synchronized(@{}) 多线更容易
如何获取给定外部哈希表键的内部HashTable的整数值 HashMap map; Hashtable> h = new Has
有谁知道如何在不使用基于 .NET 的 XMLSerializer 的情况下将哈希表转换为 XML 字符串然后再转换回哈希表。当代码在 IE 内部运行并且浏览器的保护模式打开时,XMLSerializ
我在理解这两者之间的区别时遇到了一些困难..这两者都是指向指针的指针吗?另外,它们分别适合在什么情况下使用? 最佳答案 struct node *hash1[MAXSIZE]; struct node
这个问题已经有答案了: Why does java.util.Properties implement Map and not Map (5 个回答) 已关闭 5 年前。 正如标题所述:我想找到为什么
首先,大家好。我已经中途了Python Programming for Finance - Creating targets for machine learning labels ,我有一个 csv
这是我的路线构建器。在这里,我尝试将文件中的数据插入主题。稍后,我将传递我的主要方法并使用 Camel 上下文运行它。我尝试了几个代码,但没有一个对我有帮助。我正在研究 Apache kafka -
当负载因子接近 1 以确保最小的内存浪费时,哪种 hashmap 冲突处理方案更好? 我个人认为答案是使用线性探测进行开放寻址,因为在发生冲突时它不需要任何额外的存储空间。它是否正确? 最佳答案 回答
它们是什么以及它们如何工作? 它们在哪里使用? 我什么时候应该(不)使用它们? 我一遍又一遍地听到这个词,但我不知道它的确切含义。 我听说他们允许关联数组,方法是通过散列函数发送数组键,该函数将其转换
当我们在哈希表中插入/查找键时,教科书说是O(1)时间。但是,怎么可能有O(1)查找时间呢?如果哈希表将 key 存储在向量中,则将花费O(N);如果在二叉树中,则将花费O(logN)。我只是无法使用
这不是针对特定解决方案的特定问题;但这是对以下事实的回应:我找不到有关如何为哈希表和类似任务选择良好的哈希函数的良好堆栈溢出问题。 所以!让我们谈谈散列函数,以及如何选择一种。需要为自己的特定任务选择
我是一名优秀的程序员,十分优秀!