简洁网站设计,企业对企业的网站,如何选网站服务器,陕西省城乡建设厅的网站哈希表数据结构学习 哈希表基本概念哈希方法单值哈希与多值哈希哈希冲突1. 开放寻址法#xff08;Open Addressing#xff09;2. 链地址法#xff08;Chaining#xff09;3. 再哈希法#xff08;Rehashing#xff09;4. 建立公共溢出区#xff08;Overflow Area#xf… 哈希表数据结构学习 哈希表基本概念哈希方法单值哈希与多值哈希哈希冲突1. 开放寻址法Open Addressing2. 链地址法Chaining3. 再哈希法Rehashing4. 建立公共溢出区Overflow Area5. 扩展线性哈希法Extendible Hashing6. 线性分离法Cuckoo Hashing 空间扩容vector扩容负载因子以及增容 GPU上的哈希表 哈希表 这里不区分 hashmap 和 hash table个人理解一般hashmap指哈希表这种数据结构而hash table指通过这种数据结构建立所得的结果。 哈希表又称散列表它通过建立键 key 与值 value 之间的映射实现高效O(1) 的元素查询。 为什么哈希又叫散列——其实一个是音译一个是意译。 散列hash英文原意是“混杂”、“拼凑”、“重新表述”的意思。 在哈希表中进行增删查改的时间复杂度都是 O(1) 。 查找某个元素是否存在的过程中数组和链表都需要挨个循环比较而通过 哈希 计算可以大大减少比较次数。
基本概念
若键key或k其值value或v存放在f(k)对应的桶bucket中。映射关系f为哈希函数或散列函数所得的表成为哈希表或散列表。
哈希映射由一个桶数组组成其中每个桶可以包含一个或多个键值对。要在映射中插入新的对将向键应用哈希函数以生成哈希值。然后使用该哈希值选择其中一个桶。如果存储桶可用则该对存储在该存储桶中。
例如要插入键值对 (Alice, 408-555-0148) 对键,进行散列以获取其散列值 hash(Alice)4并选择位置 4 处的存储桶来存储值408-555-0148。稍后要检索与 Alice 关联的值可以使用相同的哈希函数 hash(Alice), 再次选择位置 4 处的存储桶并检索先前存储的值。
哈希方法
直接寻址法取关键字或关键字的某个线性函数值为散列地址。即hash(k)k或hash(k)akba,b为常数这种散列函数叫做自身函数。 在LeetCode中常用一维数组 数字分析法假设关键字是以r为基的数并且哈希表中可能出现的关键字都是事先知道的则可取关键字的若干数位组成哈希地址。平方取中法取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况取其中的哪几位也不一定合适而一个数平方后的中间几位数和数的每一位都相关由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。 折- 叠法将关键字分割成位数相同的几部分最后一部分的位数可以不同然后取这几部分的叠加和舍去进位作为哈希地址。除留余数法取关键字 key 对某个不大于哈希表长度的质数 p 取余数作为哈希地址即 hash(key) key % p。选择质数可以减少哈希冲突。位运算法通过对关键字进行位移、异或、与或等位运算来生成哈希值。这种方法速度快且实现简单尤其适合于二进制数据。混合哈希法等等
密码学中常见的哈希算法 MD5 (Message-Digest Algorithm 5) 特点MD5 是一种广泛使用的哈希函数它将任意长度的输入数据映射为 128 位的散列值通常表示为 32 位的十六进制数。 应用MD5 常用于数据完整性校验。但是由于存在碰撞攻击即不同的输入会生成相同的哈希值MD5 在加密应用中已被逐步淘汰。 SHA-2 (Secure Hash Algorithm 2) 特点SHA-2 是 SHA-1 的改进版具有更强的安全性。SHA-2 包括多个不同的变种如 SHA-224、SHA-256、SHA-384、SHA-512 等分别生成 224 位、256 位、384 位和 512 位的散列值。 应用SHA-2 广泛应用于数字签名、TLS/SSL 证书和区块链技术中。
单值哈希与多值哈希
讨论哈希表时的一个重要区别是是否允许重复键。
单值哈希表或哈希映射要求键是唯一的例如 std::unordered_map单键对单值。多值哈希表和哈希多映射允许重复键如 std::unordered_multimap单键对多值。
哈希冲突
如果表中桶的数量等于可能的键的数量则可以使用哈希桶和键之间的一对一关系其中每个键正好映射到表中的一个桶。
然而这在大多数情况下是不切实际的因为潜在键值对的数量事先不知道或者为每个键值对保留存储桶所需的存储将超过可用的存储容量。好比一个电话簿不可能写得下宇宙中每个可能的名字和其号码。
因此哈希函数通常是不完美的并可能导致哈希冲突Hash Collision其中两个不同的键映射到相同的哈希值 f ( k 1 ) f ( k 2 ) , k 1 ≠ k 2 f(k_1)f(k_2),k_1\neq k_2 f(k1)f(k2),k1k2。好的哈希函数寻求最小化冲突的可能性但在大多数情况下它们是不可避免的。 在哈希表中由于不同的关键字可能被映射到相同的哈希地址导致哈希冲突Hash Collision。为了解决哈希冲突可以采用以下几种常见的方法
1. 开放寻址法Open Addressing
当发生哈希冲突时开放地址法通过在哈希表中找到另一个空闲位置来存储冲突的关键字。常见的开放地址法有以下几种策略
线性探测法Linear Probing 当发生冲突时按顺序检查哈希表的下一个位置直到找到一个空闲位置。 优点 实现简单容易理解。 缺点 容易形成“聚集”现象导致性能下降。二次探测法Quadratic Probing 探测位置不是线性增长而是按二次函数增长即探测序列为 hash(key) 1², hash(key) 2², ...。 优点 减少了线性探测法中的聚集问题。 缺点 探测序列可能导致访问不到某些位置尤其是当哈希表大小不是质数时。双重哈希法Double Hashing 使用两个不同的哈希函数 h1(key) 和 h2(key)当发生冲突时探测序列为 h1(key) i * h2(key)。 优点 减少了冲突发生的概率更均匀地分布关键字。 缺点 实现相对复杂需要设计两个合适的哈希函数。
2. 链地址法Chaining
每个哈希表槽位对应一个链表当多个关键字被映射到同一槽位时将这些关键字存储在链表中。 优点
容易处理不同大小的哈希表。无需担心哈希表装载因子过大元素个数超出哈希表大小。 缺点 链表的使用增加了额外的内存开销。查找和删除操作的时间复杂度取决于链表的长度最坏情况下为O(n)。
3. 再哈希法Rehashing
当发生冲突时使用一个新的哈希函数重新计算哈希地址直到找到一个空闲的位置。 优点 可以减少冲突的发生提高哈希表的查找效率。 缺点 需要设计多个有效的哈希函数增加了实现复杂性。
4. 建立公共溢出区Overflow Area
将冲突的关键字存放在一个公共的溢出区中而不是在原哈希表中继续查找位置。 优点
简化了哈希表的查找逻辑尤其是当溢出区结构简单时。 缺点 溢出区可能导致查找效率低下尤其是在溢出区中的元素较多时。需要额外的内存来存储溢出区。
5. 扩展线性哈希法Extendible Hashing
基于二进制哈希值的扩展哈希表每次冲突会通过增加哈希表的位数来解决冲突。哈希表会随着数据的增加而动态扩展。 优点
动态扩展避免了固定哈希表大小的限制。分布均匀减少了冲突的概率。 缺点 实现较为复杂适合需要动态调整哈希表大小的场景。
6. 线性分离法Cuckoo Hashing
使用两个哈希函数和两个哈希表当插入时如果第一个位置已经被占用则将占用该位置的元素移动到另一个哈希表中循环此操作直到没有冲突或达到预设的最大尝试次数。 优点
查找时间复杂度为 O(1)因为每个元素最多只能在两个位置上找到。插入操作复杂度较低。 缺点 可能会出现无限循环需要重新哈希。需要更大的哈希表空间来避免频繁的冲突。
每种方法都有其适用的场景和局限性选择合适的哈希冲突解决方法取决于具体应用的需求、哈希表的大小以及允许的冲突处理开销。
空间扩容
由于哈希表能够直接访问查找元素的地址所以它的时间复杂度为常数的复杂度 O(1)。而每一个key到address的映射关系需要记录下来假设哈希表有 n 个元素那么就需要 n 条记录故空间复杂度为 O(n)。 关于复杂度记法 Ο读音big-oh表示上界小于等于。 Ω读音big omega、欧米伽表示下界大于等于。 Θ读音theta、西塔既是上界也是下界称为确界等于。 ο读音small-oh表示上界小于。 ω读音small omega表示下界大于。 Ο是渐进上界Ω是渐进下界。Θ需同时满足大Ο和Ω故称为确界。Ο极其有用因为它表示了最差性能。 vector扩容 先看以下vector是怎么扩容的。 vector容器不同于数组能够进行动态扩容其底层原理所谓动态扩容并不是在原空间之后接续新空间因为无法保证原空间之后尚有可配置的空间。而是以原大小的两倍另外配置一块较大空间然后将原内容拷贝过来并释放原空间。 push_back扩容机制当push_back一个元素时
如果发现size() capacity()那么会以两倍空间扩容然后将元素插入到finish迭代器的下一个元素注意会申请一个新的空间并将原有元素拷贝到新空间中然后释放原有空间 如果发现size() capacity()那么会插入到finish迭代器的下一个元素 不会出现size() capacity()
pop_back、earse、clear缩容机制 pop_back会减少一个size()但是不会改变capacity() finish迭代器前移一位 earse会减少一个size()但是不会改变capacity() finish迭代器前移一位 clear令size()为0但是不会改变capacity()将finish迭代器移动到start相同位置
对于resize(new_size) 如果new_size curr.size什么也不做 如果new_size curr.size 那么 curr.size new_sizecurr.capacity不变 如果new_size curr.size 那么 curr.size new_sizecurr.capacity new_size将容器capacity 扩大到能容纳new_size的大小改变容器的curr.size并且创建对象。
对于reserve(new_size) 如果new_size curr.size什么也不做 如果new_size curr.size什么也不做 如果new_size curr.sizecurr.size不变curr.capacitynew_size将容器capacity 扩大到能容纳new_size的大小在空间内不真正创建对象所以不改变curr.size
真正的释放内存
vectorint(v).swap(v); vector(v)通过拷贝构造函数创建了一个匿名对象这个匿名对象拥有v的全部数据但是没有空闲的空间也就是说这个匿名对象的容量和数据量是相等的。
此时通过 swap(v) 调用该匿名对象的swap()方法交换v与匿名对象的内容。
匿名对象在执行完代码之后会自动调用析构函数那么空间被释放最终结果就是原容器中的空位被释放。 负载因子以及增容
若哈希冲突出现的较为密集往往代表着此时数据过多而能够映射的地址过少而要想解决这个问题就需要通过 负载因子装填因子 的判断来进行增容
负载因子的大小 表中数据个数 / 表的容量长度
闭散列 对于闭散列来说因为其是一种线性的结构所以一旦负载因子过高就很容易出现哈希冲突的堆积所以当负载因子达到一定程度时就需要进行增容并且增容后为了保证映射关系还需要将数据重新映射到新位置。对应上述开放寻址法。 闭散列是一种预先分配存储空间的方法。在闭散列中存储空间被划分为若干个固定大小的桶每个桶中可以存储多个元素。当插入新元素时根据其哈希值确定其所属的桶并将元素添加到该桶中。如果发生哈希冲突则将元素添加到下一个可用的桶中。这种方法简单易行但可能会导致某些桶被过度使用而其他桶仍空闲。 开散列是一种动态调整存储空间的方法。在开散列中当某个桶已满时会根据一定规则分配一个新的桶。这种方法可以更好地利用存储空间但需要额外的空间来管理桶的分配。 在实际应用中可以根据具体情况选择不同的哈希策略。例如对于需要快速插入和查找的数据结构闭散列可能是一个更好的选择。而对于需要高效利用存储空间的数据结构开散列可能更为合适。 经过算法科学家的计算 负载因子应当严格的控制在 0.7-0.8 以下所以一旦负载因子到达这个范围就需要进行增容。
因为除留余数法等方法通常是按照表的容量来计算且当对一个质数取模时冲突的几率会大大的降低并且因为增容的区间一般是 1.5-2 倍所以算法科学家列出了一个增容质数表按照这样的规律增容冲突的几率会大大的降低。 这也是 STL 中 unordered_map/unordered_set 使用的增容方法。
开散列 因为哈希桶是开散列的链式结构发生了哈希冲突是直接在对应位置位置进行头插而桶的个数是固定的而插入的数据会不断增多随着数据的增多就可能会导致某一个桶过重使得效率过低。对应上述拉链法。 开散列中每个桶放的都是哈希冲突的元素。哈希桶下面挂着的是一个一个的节点一条链表如果该位置哈希冲突的元素过多时通常会将这条链表转为一颗红黑树。 GPU上的哈希表
精心设计的哈希函数通过最大化哈希任意两个键将导致不同哈希值的可能性来最小化冲突次数。这意味着对于任何给定的两个键它们对应的桶可能位于不同的内存位置。
因此大多数哈希表操作的内存访问模式实际上是随机的。为了理解哈希表的性能了解随机内存访问的性能非常重要。
下表比较了理论峰值带宽与在现代 GPUs 和 GPUs 上通过 GUPs benchmark 测量的随机 64 位读取的实现带宽带宽计算为访问大小乘以访问次数除以时间。 随机内存访问大约比理论峰值带宽慢 10 倍。这是因为内存子系统针对顺序访问进行了优化。更重要的是 NVIDIA GPU s 的随机访问吞吐量比现代 CPU s 的高一个数量级。这些结果表明性能最好的 CPU 哈希表可能比性能最好的 GPU 哈希表慢一个数量级。 显存允许的情况下那肯定优先考虑使用GPU哈希表了。 以下是一个CUDA的哈希表三方库 参考
maximizing-performance-with-massively-parallel-hash-maps-on-gpushello-algo/hash_mapC进阶哈希 先到这儿。
