半岛,半岛体育,半岛体育app,半岛官网,半岛电竞,半岛真人,半岛棋牌,半岛体育官网注册,半岛体育官方app下载,半岛体育app下载,半岛体育怎么样,半岛体育官网,半岛体育登录入口,半岛体育官方网站目录1. 哈希概念2. 哈希冲突3. 哈希实现3.1 闭散列(哈希表)3.1.1 闭散列的细节3.1.2 优化后的闭散列3.2 扩散列(哈希桶)3.2.1 扩散列的细节4. 哈希表和哈希桶的比较5. 结尾语

　　1. 哈希概念 哈希其实在学排序时已经用过了，就是计数排序。计数排序也是用的一种映射关系。

　　我用的是绝对映射 ，所以开辟的数组空间 它的大小 必须 能映射到 最大的元素。

　　但是 对于哈希来讲，可以用决定映射嘛？当然不可以，如果是绝对映射会造成很大的空间浪费。所以 哈希 用的是 取模的方式来存 数据。

　　比如：存 100 ，它对10取模得 0，那它就存在第一个位置；存 52 ，它对10进行取模得 2，那它就存到 下标为 2的位置。

　　数据都能进行取模吗？假如我要求哈希表中存的是一个字符串，字符串不能进行取模运算，该怎么办？这就是数据可否哈希的问题，我们要把存进哈希表的数据，变为可哈希数据。如果我存的是 4，下一次我要存的是 14。由于 4的位置已经被占了，我存的 14 该存放到何处？要是直接存，就意味着前面存的 4 会被覆盖，造成数据丢失。这就是哈希冲突问题。

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

　　它相当于 如果我本来要存的位置，已经被占了，那么我就要在哈希表中找一个空位置存放。开散列：开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

　　这种办法是常用的，它相当于 哈希表 每个位置 都存的是一个哈希桶，如果发送哈希冲突，直接就放在哈希桶里就行了。

　　3. 哈希实现 哈希表其实就是一个数组，数组中存的是节点数据，发生哈希冲突后，采用的是往后找空位置的方法。

　　(4)22%6 == 4，插入到下标为4的位置，发现已经有数据了，所以向后找空位置。

　　(5)44%6 == 2，插入到下标为2的位置，发现已经有数据了，所以向后找空位置。

　　哈希桶其实就是一个数组，数组中存的是节点链表，发生哈希冲突后，是直接插入到节点链表中。

　　3.1 闭散列(哈希表)以上就是闭散列的实现。我们来一步一步的解析以上代码。

　　(1) 用枚举常量来 标记 哈希表中 每个位置的状态，状态有 空，不为空，被删除。

　　大家可能会对 被删除这个状态产生疑问，一个位置 不就是 有数据和没数据吗？主要是大家想 如果 直接物理上删除，把位置 状态设置为 空，那么 就会影响后面的数据。

　　直接将 5 的位置 设置为空，那么 15 这个数据 会受到影响。因为 对 哈希表大小取模后，等于 5 的 不一定只有 5，还有 15，25，35。如果 将 5位置直接设置 为 空，就相当于 后面的数据中 已经没有 15，25，35 了。具体我们往下看查找的实现。

　　如果为空，必然需要扩容，默认给 10 个大小即可。当有效数据个数 除以 数组大小 大于等于 0.7 时，需要扩容 其实 有效数据个数 除以 数组大小 被称为 载荷因子，当载荷因子 大于 0.7时，就说明需要扩容了。这是大佬们搞出来的，我们还需要知道，载荷因子 越大就说明 填入哈希表的元素越多，越可能发送哈希冲突。

　　扩容的操作，我是 创建了一个新的哈希表，然后把原表中的数据插入到新表中。这里还有一个坑，就是，可不可以 直接将旧表的数据拷贝到新表中，答案是 不行。

　　看图也懂了哈，扩容后的表 是需要重新插入数据，因为 位置 可能会发送改变。

　　扩容完了，就是插入了，如果当下的位置是 Delete 或者 Eempty 那么就可以直接插入；否则就需要向后面查找空的位置，进行插入。

　　比如： 不是所有的数据都可以取模，这个问题，并没有解决，上面实现是 直接取模。

　　所以还需要实现一个 将数据转为可哈希数据的仿函数。为什么是仿函数呢？因为 数据类型较多，情况不一，这里还用到了模板特化的知识，大家坐稳扶好。

　　所以有了仿函数之后，我们就不必担心，传过去的数据是否能够 被哈希了，靠仿函数去处理。具体怎么用，后面会给出完整代码。

　　大家可能对这俩词不陌生，也就是哈希表中，发生哈希冲突后，查找空位置时，是连续的查找空位置还是 平方次的跳跃的查找。

　　当然是二次查找更优秀一些，上面的程序用的是线性探索，也就是 那个i++，它就是连续的往后查找。为什么呢？因为 如果是线性探索，它会比较拥挤，连续位置太多，从而引发踩踏效应，也就导致，每次来的数据，都需要去找空位置。

　　哈希桶的节点是一个单向链表，它得有数据，是一个键值对，还得有 下一个节点的指针。

　　查找也简单呢，就是迭代往下查找，如果找到就返回，位置的指针，找不到就返回空。

　　桶中是单向链表，删除的话我需要维护链表的关系，所以需要记录删除数据的前一个数据要删除的节点如果是头节点，就不需要维护和前一个数据的关系，因为它就是第一个要删除的节点在中间或者最后，那就需要维护和前一个的关系

　　3.2.1 扩散列的细节 扩散列是有极端情况的，比如 我开辟的数组大小是 10 ，插入的数据是 10，20，30，40，50，60 ，这些数据都插入到了一个桶里面。

　　会发现，效率退化了，哈希的查找一般情况是O(1) ，但是这种情况下，退化成O(n)了。所以应该怎么办？大佬其实是给出解决方案的，就是一个桶中的元素超过了某一个量，那么就会将这个桶中的数据用红黑树组织起来，对于这个量jave和C++还不一样。

　　但是上面的哈希桶，我没有支持这种高级操作，我觉得只要了解这个事情就行了，至于实现，也是可以的，但是对于我们要学习哈希，没太大帮助。

　　4. 哈希表和哈希桶的比较 哈希桶处理溢出，需要增设链接指针，似乎增加了存储开销。

　　事实上： 由于哈希表必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a = 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

　　哈希表处理哈希冲突用的是抢占别的位置，可能会导致数据比较阻塞，也就是每进来一个数据都需要去抢占别人的位置。

　　哈希桶处理哈希冲突用的是在冲突位置，增加链节点的方法，但是有可能造成，单向链表太长从而影响效率，所以需要将单向链表变为红黑树管理起来。

　　5. 结尾语 学完哈希，能干什么？说实话哈希很重要，学数据结构，你说你不会哈希，那么就相当于你白学数据结构了，就是这么夸张哈，以后工作也会大量用到哈希的。所以大家加油。在我的下一篇文章中，会利用哈希桶去实现unordered_map和unordered_set，也算是用上了哈希。当然位图呀，布隆过滤器呀，海量处理数据等 都会用到哈希。

　　到此这篇关于C语言哈希表概念超详细讲解的文章就介绍到这了,更多相关C语言哈希表内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！