您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

算法笔记:哈希表、映射和集合

时间:2022-03-29 11:41:51  来源:  作者:测试开发小记

hash函数是根据关键字key计算出应该存储地址的位置,哈希函数把key转成哈希值来定位数据存储的位置,是基于哈希函数建立的一种查找表,Python 中的字典就是用哈希表来实现的。本文主要介绍哈希表、映射和集合这三种数据结构以及他们在python中的用法。

哈希表-Hash table

哈希表

哈希表(Hash table),也叫散列表,根据键(Key)访问在内存储存位置的数据,通过把键值映射到表中一个位置来访问记录,映射函数称为散列函数或者哈希函数,根据哈希函数建立的记录数据的表称为哈希表(散列表)。

比如键值为k,对应的值放在 f(k) 的存储位置上,这个对应关系 f 称为散列函数,通过它来建立的表称为散列表。

哈希碰撞

两个不同的key值得到相同的哈希值的情况称为哈希碰撞(Hash Collisions),也就是 f(k1) = f(k2)。哈希碰撞的解决方案有:开放寻址(Open Addressing)法、链地址法(Chaining)、再哈希法(Rehash)和建立一个公共溢出区。

  • 开放寻址法:产生冲突后继续寻找下一个空闲的空间(没有被占用的存储地址),Python使用的就是这种方法。
  • 链地址法:散列到同一位置的元素,不继续往下寻找,而是将所有关键字为同义词的记录存储在同一线性链表中,HashMap就采用了链地址法。
  • 再散列函数法:产生冲突后,就再来一次哈希计算,直到没有冲突。
  • 建立一个公共溢出区:也就是建两个表,一个作为基本表,另一个是存储和基本表发生冲突元素的溢出表。

哈希冲突的发生,往往会降低字典和集合操作的速度。因此,为了保证其高效性,字典和集合内的哈希表,通常会保证其至少留有 1/3 的剩余空间。随着元素的不停插入,当剩余空间小于 1/3 时,Python 会重新获取更大的内存空间,扩充哈希表。

python 字典

Python 中的字典就是典型的哈希表,是一系列由键(key)和值(value)配对组成的元素的集合,其中value可以是任何数据类型,且可以重复。Key不能重复并且必须是不可变(immutable)的。

在 Python3.7+版本中,字典是有序的, 3.6 之前是无序的。

创建字典

# 创建空字典
>>> mydict={}
>>> type(mydict)
<class 'dict'>
>>> mydict
{}
>>> mydict = {1:"Apple",2:"banana"}

# dict()方法创建字典
>>> mydict = dict({1:"apple",2:"banana"})
>>> mydict = dict([(1, 'apple'), (2, 'banana')])
>>> mydict
{1: 'apple', 2: 'banana'}

# fromkeys()方法
>>> seq=(1,2,3)
>>> mydict = dict.fromkeys(seq)
>>> mydict
{1: None, 2: None, 3: None}
>>> mydict = dict.fromkeys(seq,'apple')
>>> mydict
{1: 'apple', 2: 'apple', 3: 'apple'}

理论上来说,直接使用{}创建字典比dict()方法效率更高, {} 会直接调用底层C代码。

直接使用Dict[Key] = ‘Value’的形式新增元素,可以增加任何数据类型,比如可以嵌套字典,列表等。如果key已经存在,则进行更新。

>>> mydict={}
>>> mydict[2] = 'banana'
>>> mydict
{2: 'banana'}

访问元素

直接使用key访问元素值,也可以使用 get(key) 方法获取,如果键不存在,调用 get() 函数可以返回一个默认值

>>> mydict = {1:"apple",2:"banana"}
>>> mydict[2]
'banana'
>>> mydict.get(2)
'banana'
>>> mydict.get(3,'null')
'null'

setdefault()方法也可以用来获取元素值,和get()方法不同的是,如果查找的key不存在,它会设置一个默认值(default=None):

>>> mydict.setdefault(2)
'banana'
>>> mydict.setdefault(3)
>>> mydict
{1: 'apple', 2: 'banana', 3: None}

>>> mydict.setdefault(4,'orange')
'orange'
>>> mydict
{1: 'apple', 2: 'banana', 3: None, 4: 'orange'}

删除元素

del删除元素

>>> mydict = {1:"apple",2:"banana"}
>>> del mydict[2]
>>> mydict
{1: 'apple'}

pop方法:

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.pop(2)
'banana'
>>> mydict
{1: 'apple'}
>>>

popitem()用于随机删除任意键值对

清除字典元素

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.clear()
>>> mydict
{}

合并字典

>>> mydict1 = {1:"apple",2:"banana"}
>>> mydict2 = {3:"orange"}
>>> mydict1.update(mydict2)
>>> mydict1
{1: 'apple', 2: 'banana', 3: 'orange'}
>>> 
# 或者
>>> {**mydict1,**mydict2}
{1: 'apple', 2: 'banana', 3: 'orange'}

获取字典key,value值

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.keys()
dict_keys([1, 2])
>>> 
>>> mydict.values()
dict_values(['apple', 'banana'])

items()方法返回(key, value)对:

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.items()
dict_items([(1, 'apple'), (2, 'banana')])
mydict = {1:"apple",2:"banana"}
for key,value in mydict.items():
	print(key)
	print(value)

python2中,has_key()可用于判断字典是否存在某个key:

>>> mydict = {1:"apple",2:"banana"}
>>> mydict.has_key(1)

python3删除了has_key()方法,可以使用 in 操作符来判断:

mydict = {1:"apple",2:"banana"}
if 1 in mydict:
	print(mydict(1))

# 或者
if 1 in mydict.keys():
	print(mydict(1))

字典排序

实际应用中,通常需要对字典进行排序,一般会根据键或值,进行升序或降序排序:

根据字典键升序排序

>>> mydict = {1:"apple",3:"banana",2:"orange"}
>>> sorted(mydict.items(), key=lambda x: x[0])
[(1, 'apple'), (2, 'orange'), (3, 'banana')]

根据字典值降序排序

>>> sorted(mydict.items(), key=lambda x: x[0], reverse=True)
[(3, 'banana'), (2, 'orange'), (1, 'apple')]
>>>

判断一个字典是否包含另一个字典

判断mydictA是否包含mydictB

>>> mydictA = {1:"apple",3:"banana",2:"orange"}
>>> mydictB = {1:"apple"}
>>> dict(mydictB, **mydictA) == mydictA
True

映射-Map

映射和哈希表类似,也是存储key-value对,通过键(Key)查找值(Value)。
JAVA 的HashMap() 和TreeMap()

  • map.set(key, value)
  • map.get(key)
  • map.has(key)
  • map.size()
  • map.clear()

python 映射函数

下面介绍一下python的map()函数用法:
map() 根据提供的函数对指定序列进行映射,返回映射函数返回值的新列表。一般结合lambda匿名函数一起使用:

>>> map(lambda x: x ** 2, [1, 2, 3, 4, 5])
[1, 4, 9, 16, 25]

两个list相加:

>>> list1 = [1, 2, 3]
>>> list2 = [4, 5, 6]  
>>> map(lambda x, y: x + y, list1, list2)
[5, 7, 9]

集合-Set

与列表(list)类似,但集合set没有重复元素,集合没有键和值的配对,是一系列无序的、唯一的元素组合。

字典和集合的内部结构都是一张哈希表,字典存储了哈希值(hash)、键和值这 3 个元素,而集合的哈希表内没有键和值的配对,只有单一的元素。和列表不一样,集合不支持索引操作。

java 的HashSet()和TreeSet()

  • set.add(value)
  • set.delete(value)
  • set.hash(value)

python集合

可以使用{ }创建集合:

>>> setA = {'apple', 'banana'}
# 或者 setA = set(["apple", "banana"])
>>> setB = {'apple', 'banana', 'orange'}

并集

>>> setA.union(setB)
set(['orange', 'apple', 'banana'])
>>> setA | setB
set(['orange', 'apple', 'banana'])

交集

>>> setA.intersection(setB)
set(['apple', 'banana'])
>>> setA & setB
set(['apple', 'banana'])
>>> 
>>> setB.intersection_update(setA)
>>> setB
{'banana', 'apple'}

isdisjoint() 方法可用于判断两个集合是否包含相同的元素,如果没有返回 True。

差集

>>> setB.difference(setA)
set(['orange'])
>>> setB-setA
set(['orange'])

子集判断

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana', 'orange'}
>>> setA.issubset(setB)
True
>>> setA.issuperset(setB)
False
>>> setB.issuperset(setA)
True

对称差集

两个集合中不重复的元素集合

>>> setA.symmetric_difference(setB)
set(['orange'])
>>> setA ^ setB
set(['orange'])
>>> 
>>> setA.symmetric_difference_update(setB)
>>> setA
{'orange'}

增加元素

>>> setA.add("orange")
>>> setA
set(['orange', 'apple', 'banana'])

删除元素

remove()删除不存在的元素会报KeyError错误,可以使用discard()方法避免KeyError错误。

>>> setA = {'apple', 'banana', 'orange'}
>>> setA.remove('orange')
>>> setA
{'banana', 'apple'}
>>> 
>>> setA.remove('pear')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'pear
>>> setA.discard('pear')

pop() 方法也可以用来删除元素,用于删除最后一个元素,但是,集合是无序的,所以不知道到底删除的是哪一个元素。

>>> setA = {'apple', 'banana', 'orange'}
>>> setA.pop()
'banana'
>>> setA
{'orange', 'apple'}
>>>

清空集合

>>> setA = {'apple', 'banana'}
>>> setA.clear()
>>> setA
set()

冻结集合

冻结后集合不能添加或删除任何元素

>>> frozen_set = frozenset(['apple', 'banana'])
>>> frozen_set.add("orange")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'
>>>

集合排序

集合排序和列表、元组类似,使用 sorted(set) 方法排序:

>>> setA = {'apple', 'orange', 'banana'}
>>> sorted(setA)
['apple', 'banana', 'orange']

python集合运算

python集合支持以下运算:
1、in ,not in

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana', 'orange'}
>>> 'apple' in setA
True
>>>

2、==,!=

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana'}
>>> setA == setB
True
>>>

3、<=,<
setA <= setB:setA是setB的子集
setA < setB:setA是setB的真子集

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana'}
>>> setA <= setB
True
>>> setA < setB
False
>>> setB = {'apple', 'banana', 'orange'}
>>> setA < setB
True

4、>=,>
setA >= setB:setA是setB的超集
setA > setB:setA是setB的真超集

>>> setA = {'apple', 'banana'}
>>> setB = {'apple', 'banana'}
>>> setA >= setB
True
>>> setA > setB
False
>>> setA = {'apple', 'banana', 'orange'}
>>> setA > setB
True

前面提到过,还支持:

  • |:并集
  • &:交集
  • -:差集
  • ^:对称差集

python集合特点

python集合有以下特点:
1、集合不按特定顺序保存元素,是无序的,不支持索引操作,集合本质上是一个哈希表,可以将集合转换为list后进行索引操作,也可以使用in 关键字。

setA = {'apple', 'banana'}
for fru in setA:
    print(fru, end="n")

输出

banana
apple

2、python集合只能添加不可变(immutable)的实例,比如可以添加元组(tuple),字符串(string),不能添加列表(list),如果添加的元素为list,可以使用update方法,update方法用于新增多个元素。

>>> a=(1,2)
>>> setA.add(a)
>>> setA
{(1, 2), 'bapple', 'anana'}
>>> 
>>> b=[1,2]
>>> setA.add(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> setA.update(b)
>>> setA
{(1, 2), 1, 2, 'bapple', 'anana'}
>>>

复杂度分析

相比于数组,列表和元组,哈希表和集合的性能更优,特别是对于查找、添加和删除操作,字典都能在常数时间复杂度内完成。对于查找,数组的时间复杂度为 O(n),如果使用二分查找,也需要 O(logn) 的时间复杂度,但需要对数组进行排序,至少需要O(nlogn) 的时间复杂度。

算法笔记:哈希表、映射和集合

http://www.bigocheatsheet.com/

--THE END--



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
近年来,在材料科学、人工智能芯片等前沿领域,深度学习受到广泛的研究和应用。具体来说,深度学习通过学习样本数据的内在规律和表示层次实现机器像人一样具有分析和学习的能力,因...【详细内容】
2022-03-30  Tags: 算法  点击:(2)  评论:(0)  加入收藏
hash函数是根据关键字key计算出应该存储地址的位置,哈希函数把key转成哈希值来定位数据存储的位置,是基于哈希函数建立的一种查找表,Python 中的字典就是用哈希表来实现的。本...【详细内容】
2022-03-29  Tags: 算法  点击:(3)  评论:(0)  加入收藏
回归算法 一、理解线性回归模型 首先讲回归模型,回归模型研究的是因变量(目标)和自变量(预测器)之间的关系,因变量可以是连续也可以离散,如果是离散的就是分类问题。思考房价预测模...【详细内容】
2022-03-28  Tags: 算法  点击:(1)  评论:(0)  加入收藏
桶排序算法就是把数据平分到每一个桶中,然后对桶中的数据进行排序,再按桶的顺序依次倒出数据,桶排序算法很好理解。桶排序算法也是以空间换时间的算法。举例说明一下桶排序算法...【详细内容】
2022-03-24  Tags: 算法  点击:(9)  评论:(0)  加入收藏
递归三要素:1、明确递归终止条件;2、给出递归终止时的处理办法;3、提取重复的逻辑,缩小问题的规模。1、1+2+3+&hellip;+nimport java.util.Scanner; public class Recursion {...【详细内容】
2022-03-18  Tags: 算法  点击:(17)  评论:(0)  加入收藏
“我的”——“设置”——“通用设置”——“管理个性化内容推荐”——“个性化内容推荐”。...【详细内容】
2022-03-17  Tags: 算法  点击:(14)  评论:(0)  加入收藏
大数据的时代,几乎每个手机用户都遇到过被个性化算法“支配”的情况:点赞一个视频,APP会源源不断推送近似视频;搜索过一件商品,从此打开购物平台都是同类型商品;想抢个优惠券,还可...【详细内容】
2022-03-17  Tags: 算法  点击:(13)  评论:(0)  加入收藏
3月16日消息,据经济日报报道,据不完全统计,截至3月15日,抖音、今日头条、微信、淘宝、百度、大众点评、微博、小红书等App均已上线算法关闭键,允许用户在后台一键关闭“个性化推...【详细内容】
2022-03-17  Tags: 算法  点击:(22)  评论:(0)  加入收藏
先介绍一款小巧的hash工具,就是下图这个,可以计算文件的md5值,SHA1值和CRC32值。不到100kb,功能也很简单,就是对文件进行校验,检查是否被篡改过。 对于网上下载linux操作系统和win...【详细内容】
2022-03-15  Tags: 算法  点击:(16)  评论:(0)  加入收藏
10种经典排序算法包括冒泡排序、选择排序、快速排序、归并排序、堆排序、插入排序、希尔排序、计数排序、桶排序、基数排序等。当然,还有一些其他的排序算法,大家可以继续去...【详细内容】
2022-03-11  Tags: 算法  点击:(24)  评论:(0)  加入收藏
▌简易百科推荐
一、为什么讲策略模式策略模式,应该是工作中比较常用的设计模式,调用方自己选择用哪一种策略完成对数据的操作,也就是“一个类的行为或其算法可以在运行时更改”我个人的理解...【详细内容】
2022-03-30  大数据架构师  博客园  Tags:枚举策略   点击:(0)  评论:(0)  加入收藏
hash函数是根据关键字key计算出应该存储地址的位置,哈希函数把key转成哈希值来定位数据存储的位置,是基于哈希函数建立的一种查找表,Python 中的字典就是用哈希表来实现的。本...【详细内容】
2022-03-29  测试开发小记    Tags:算法   点击:(3)  评论:(0)  加入收藏
桶排序算法就是把数据平分到每一个桶中,然后对桶中的数据进行排序,再按桶的顺序依次倒出数据,桶排序算法很好理解。桶排序算法也是以空间换时间的算法。举例说明一下桶排序算法...【详细内容】
2022-03-24  理性职场说    Tags:桶排序   点击:(9)  评论:(0)  加入收藏
正则表达式(Regular expression)可用来检查文本中是否包含指定模式的字符串,通常是按行来处理(POSIX标准),因为.操作符通常不匹配换行符,如果要匹配多行怎么处理呢?本文介绍正则表达...【详细内容】
2022-03-22  测试开发小记    Tags:正则表达式   点击:(17)  评论:(0)  加入收藏
AVL(Adelson-Velsky and Landis Tree) 树是一种自平衡二叉树, 也是最早发明的一种自动平衡二叉树。原因是由于BST(二叉搜索树)在用有序列表不断插入时会退化成链表而大大影...【详细内容】
2022-03-15  程序驱动世界    Tags:AVL树   点击:(15)  评论:(0)  加入收藏
前言:本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记。内容主要是关于十大经典排...【详细内容】
2022-03-04  IT界彭于晏  博客园  Tags:排序算法   点击:(24)  评论:(0)  加入收藏
作者:小伍哥来源:小伍哥聊风控 大家好,我是小伍哥,今天给大家分享的是一个基于密度的欺诈检测算法,思想非常牛逼,大家可以试试,先给出论文地址和代码论文地址:http://pengcui.thumed...【详细内容】
2022-03-03  CDA数据分析师    Tags:欺诈检测算法   点击:(18)  评论:(0)  加入收藏
正则表达式,十分古老而又强大。熟悉掌握并使用,可以在编程时节省很多时间和精力,开发效率得到极大的提升。比如下面这十个正则表达式,是日常前JS开发中经常用到的,且都验证过,可直...【详细内容】
2022-02-25  修丹道的程序猿    Tags:正则表达式   点击:(29)  评论:(0)  加入收藏
新的算法很难产生,2022 年可能也不例外。然而,仍有一些机器学习算法和 Python 库将在未来更受欢迎。这些算法之所以与众不同,是因为它们包含了一些在其它算法中并不普遍的优点...【详细内容】
2022-02-20  InfoQ    Tags:机器学习   点击:(7)  评论:(0)  加入收藏
之前说过,二分法算法是一种非常常见的算法。这里大概说说算法的内容。具体算法如果有兴趣,去百度、维基百科,搜搜就都能找到。我就不做搬运工了。这里就我个人的理解,不严谨的说...【详细内容】
2022-02-14  北美程序员的自我修养  今日头条  Tags:算法   点击:(34)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条