首页 > 编程语言 >代码随想录算法训练营第六天|理解hash表

代码随想录算法训练营第六天|理解hash表

时间:2024-09-30 13:00:48浏览次数:10  
标签:std map set hash 哈希 随想录 第六天 key 红黑树

What is Hash Table?

引用自文章链接:https://programmercarl.com/哈希表理论基础.html#哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。直白来讲其实数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。

哈希函数

通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于 哈希表的大小了,也就是大于tableSize了,怎么办呢?

此时为了保证映射出来的索引数值都落在哈希表上,我们会在再次对数值做一个取模的操作,这样我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了,哈希表我们刚刚说过,就是一个数组。

如果学生的数量大于哈希表的大小怎么办,此时就算哈希函数计算的再均匀,也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞


解决方法:

拉链法:

刚刚小李和小王在索引1的位置发生了冲突,发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了

其实拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。

线性探测法:

使用线性探测法,一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置,放了小李,那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ,要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示:

常见的哈希结构:

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。

  • 数组
  • set (集合)
  • map(映射)
    在C++中,set 和 map 分别提供以下三种数据结构,其底层实现以及优劣如下表所示:
集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 O(log n) O(log n)
std::multiset 红黑树 有序 O(logn) O(logn)
std::unordered_set 哈希表 无序 O(1) O(1)

std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
std::multimap 红黑树 key有序 key可重复 key不可修改 O(log n) O(log n)
std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。

set

  • 当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
  • 虽然std::set和std::multiset 的底层实现基于红黑树而非哈希表,它们通过红黑树来索引和存储数据。不过给我们的使用方式,还是哈希法的使用方式,即依靠键(key)来访问值(value)。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。std::map也是一样的道理。

map

  • 那么再来看一下map ,在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。


建议用标准库中的。

总结:

总结一下,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法!

标签:std,map,set,hash,哈希,随想录,第六天,key,红黑树
From: https://www.cnblogs.com/VickyWu/p/18441634

相关文章

  • HashMap原理
    HashMap原理在很多地方都会利用到hash表来提高查找效率。在Java的Object类中有一个方法:publicnativeinthashCode();```根据这个方法的声明可知,该方法返回一个int类型的数值,并且是本地方法,因此在Object类中并没有给出具体的实现。为何Object类需要这样一个方法?它......
  • ConcurrentHashMap是怎么实现的?
    1.是什么    ConcurrentHashMap 是Java并发包(java.util.concurrent)中的一个线程安全的哈希表实现。与 HashMap 相比,ConcurrentHashMap 在并发环境下具有更高的性能,因为它允许多个线程并发地进行读写操作而不会导致数据不一致。以下是 ConcurrentHashMap 实现的一......
  • 代码随想录一刷day2
    T27移除元素   注意复习思路快慢指针:快指针:指向遍历的元素慢指针:指向需要替换的元素实现:slowIndex=0;通过遍历fastIndex,当target!=nums【fastIndex】,nums【slowIndex++】=nums【fastIndex】; T26理解快慢指针 nums[fast]!=nums[slow]时,交换两个的值且slow++;其他就f......
  • hash冲突解决
     解决方法:拉链法,又称为链地址法其基本思想是将所有具有相同哈希值的元素链接在一起,形成一个链表。 解决方法:开放地址--线性探测法https://www.cnblogs.com/-beyond/p/7726347.html关注点:1、hash冲突元素的插入2、已有元素的删除和同hash值元素的移动3、扩容 1、插入......
  • Redis渐进式rehash
    为什么要渐进式rehash?在Redis中,哈希表是实现快速键值对查找的关键数据结构,但随着数据的增加,哈希表可能会因为冲突过多或空间不足而需要扩容;相反,当数据大量删除后,哈希表也可能因为空间利用率过低而需要缩容。在扩容和缩容过程中,由于长度变化会导致key的索引变化,为了避免一次性r......
  • 代码随想录算法训练营第四天|24. 两两交换链表中的节点,19.删除链表的倒数第N个节点,面
    24.两两交换链表中的节点文章链接:https://programmercarl.com/0024.两两交换链表中的节点.html#思路视频讲解:https://www.bilibili.com/video/BV1YT411g7br代码链接:https://leetcode.cn/problems/swap-nodes-in-pairs/此题注意点:注意由于交换节点,head已经变换了位置,故最终......
  • 代码随想录算法训练营Day16 | 513.找树左下角的值、112.路径总和、113.路径总和Ⅱ、10
    目录513.找树左下角的值112.路径总和113.路径总和Ⅱ106.从中序与后序遍历序列构造二叉树105.从前序与中序遍历序列构造二叉树513.找树左下角的值题目513.找树左下角的值-力扣(LeetCode)给定一个二叉树的根节点root,请找出该二叉树的最底层最左边节点的值。假......
  • 代码随想录算法训练营Day03-链表 | LC203移除链表元素、LC707设计链表、LC206反转链表
    目录前言LeetCode203.移除链表元素思路完整代码LeetCode707.设计链表思路完整代码LeetCode206.反转链表思路完整代码今日总结前言拖延症犯了,哈哈,拖了一天LeetCode203.移除链表元素给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val......
  • 代码随想录算法训练营第三天|203.移除链表元素,707.设计链表,206.反转链表
    203.移除链表元素文章链接:https://programmercarl.com/0203.移除链表元素.html#算法公开课视频讲解:https://www.bilibili.com/video/BV18B4y1s7R9题目出处:https://leetcode.cn/problems/remove-linked-list-elements/卡哥在这里讲解了为什么要使用虚拟头节点,以及使用和不使......
  • 精通推荐算法31:行为序列建模之ETA — 基于SimHash实现检索索引在线化
    1 行为序列建模总体架构2SIM模型的不足和为什么需要ETA模型SIM实现了长周期行为序列的在线建模,其GSU检索单元居功至伟。但不论Hard-search还是Soft-search,都存在如下不足:GSU检索的目标与主模型不一致。Hard-search通过类目属性来筛选历史行为,但不同类目不代表相关度低,比......