主页 > 新闻中心 > 媒体通稿

哈希表C++哈希表详解(知识点+相关LeetCode题目)

目录

前言

一、什么是哈希表

二、哈希表的操作

2.1 操作时间复杂度

2.2 哈希表通用API

2.3 建立哈希表

2.3 哈希表常见结构介绍

Set(集合)

Map(映射)

unordered_map(哈希表)

三、哈希表的力扣经典题目

有效的字母异位词242

两个数组的交集 349

两数之和1

四数相加II 454

三数之和 15

四数之和 18


前言

本文将从哈希表的概念、复杂度、STL实现函数、哈希表相关经典题目展开叙述。

一、什么是哈希表

哈希表是散列表,就是通过关键码值而直接进行访问的一种数据结构

哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素

其内部由一个个key:value 样式的键值对组成。

哈希表中的key通过哈希函数得到内存地址,然后将key和value放到对应的内存地址,从而实现通过key获取Value的方式

哈希碰撞:2个不同的key通过哈希函数(hash function)得到了相同的内存地址,也就是是内存地址已经被一个占用了,解决方法是将其中之一变为链表结构,使用next指向。这样内存地址就不会重复,但是会影响查询

二、哈希表的操作

2.1 操作时间复杂度

1) 搜索:1.无哈希碰撞,直接用哈希函数通过Key定位到内存地址,复杂度O(1)                                               2.有哈希碰撞,因为存在内存地址需要通过链表查询,复杂度O(N)

2) 插入:通过key找到内存地址插入即可,复杂度 O(1)--自动插入

unorder_map InquireMap;
InquireMap[val] = 1;

3) 删除:通过key找到内存地址删除即可,复杂度 O(1)

2.2 哈希表通用API

  • begin():该函数返回一个指向哈希表开始位置的迭代器
  • end():返回一个指向哈希表结尾位置的下一个元素的迭代器
  • empty():判断哈希表是否为空,空则返回true,非空返回false
  • size():返回哈希表的大小
  • erase(): 删除某个位置的元素,或者删除某个位置开始到某个位置结束这一范围内的元素, 或者传入key值删除键值对
  • at():根据key查找哈希表中的元素
  • clear():清空哈希表中的元素
  • find():以key作为参数寻找哈希表中的元素,如果哈希表中存在该key值则返回该位置上的迭代器,否则返回哈希表最后一个元素下一位置上的迭代器
  • count(): 统计某个key值对应的元素个数 (注:因为unordered_map不允许重复元素,所以返回值为0或1)

2.3 建立哈希表

unordered_map correspond{
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000},
    };

2.3 哈希表常见结构介绍

总体结构上分为数组、set、map

数组也是一种意义上的哈希表

set的结构中每个元素都是一个值(类似于数组)

map的结构是一个 key:value 的数据结构

Set(集合)

1) set、multiset 基于红黑树(一种平衡二叉搜索树),所以(key)值都是有序的,但是不可以修改,一旦修改就会引起整棵树的错乱,所以只能删除和增加,两者唯一的区别是前者不可重复(key)值,后者可以重复

2)unordered_set 底层实现为哈希表,区别就是没有关键码这个说法,哈希表是无序的,所以查询效率要快些O(1)就可以实现。因为无序,所以值也不可以重复

小结:当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

这三种数据结构的具体优劣在这里引用一张表来直观体现

集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 O(log n) O(log n)
std::multiset 红黑树 有序 O(logn) O(logn)
std::unordered_set 哈希表 无序 O(1) O(1)

Map(映射)

1)map、multimap  基于红黑树(一种平衡二叉搜索树),key是有序的,和上面提到的set、multimap一样,key值可以添加、删除,但是不可以更改(map中,对key是有限制,对value没有限制的。所以说value值可以修改)两者唯一的区别是前者不可重复key值,后者可以重复

2)unordered_map 底层实现为哈希表(无序),因为无序,所以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)

unordered_map(哈希表)

这个数据结构更加常用,所以在这里特别讲一下它的性质

  • unordered_map底层存储的是键值对,可以通过key快速的索引到value unordered_map内部因为是数据是通过映射存入哈希桶内的,所以对unordered_map进行遍历得到的是一个无序的序列。
  • unordered_map通过key进行访问的速度比map快,但是遍历元素的迭代效率就要低于map了。unordered_map也实现了operator[ ] 可以通过key直接访问到value

三、哈希表的力扣经典题目

有效的字母异位词242

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26] = {0};//26个英文字符
        for(int i =0 ;i
×

扫一扫关注 集团官方微信