从零开始学Python-Day12-dict和set

Python零基础 木人张 7个月前 (03-18) 88次浏览 0个评论 扫描二维码
文章目录[隐藏]

字典,dictionary,简称dict,用key-value储存,方便查找。
假设这样一个问题,需要查询单个学生的成绩,如果用list来做,需要用到两个list:

花名册 = ['张三','李四','王五']
成绩 = [100,90,80]

如果要查询张三的成绩,需要现在list花名册中找到张三所在的位置,然后到list成绩中,查询对应位置的数值,这种方法的话,如果list很长,查询时间也会相应变长,因为相当于做了两次查询。
如果用字典来做,只需要查询一次:

>>> 成绩单 = {'张三':100,'李四':90,'王五':80,}
>>> 成绩单['张三']
100

但你会说,如果字典内容很多,查询也不快啊,这里就要说到字典的特性了,哈希表。

要理解dict的有关内容需要你理解哈希表(map)的相关基础知识,这个其实是《算法与数据结构》里面的内容。

1.list和tuple其实是用链表顺序存储的,也就是前一个元素中存储了下一个元素的位置,这样只要找到第一个元素的位置就可以顺藤摸瓜找到所有元素的位置,所以list的名字其实就是个指针,指向list的第一个元素的位置。list的插入和删除等可以直接用链表的方式进行,比如我要在第1个元素和第2个元素中间插入一个元素,那么直接在链表的最后面(我们假设这个list只有两个元素,那么也就是在第3个元素的位置上)插入这个元素,然后把第一个元素指针指向这个元素(第3个位置),然后再把新插入的元素的指针指向原来的第2个元素,这样插入操作就完成了。读取这个list的时候,先用list的名字(就是个指针,指向第1个元素的位置)找到第一个元素,然后用第1一个元素的指针找到第2个元素(位置3),然后用第2个元素的指针找到第3个元素(位置2),以此类推。所以list的顺序和内存中的实际顺序其实不一定完全对应。这种存储方式不会浪费内存,但查找起来特别费时间,因为要按照链表一个一个找下去,如果你的list特别大的话,那么要等好久才会找到结果。

2.dict则为了快速查找使用了一种特别的方法,哈希表。哈希表采用哈希函数从key计算得到一个数字(哈希函数有个特点:对于不同的key,有很大的概率得到的哈希值也不同),然后直接把value存储到这个数字所对应的地址上,比如key=’ABC’,value=10,经过哈希函数得到key对应的哈希值为123,那么就申请一个有1000个地址(从0到999)的内存,然后把10存放在地址为123的地方。类似的,对于key=’BCD’,value=20,得到key的哈希值为234,那么就把20存放在地址为234的地方。对于这样的表查找起来是非常方便的。只要给出key,计算得到哈希值,然后直接到对应的地址去找value就可以了。无论有几个元素,都可以直接找到value,无需遍历整个表。不过虽然dict查找速度快,但内存浪费严重,你看我们只存储了两个元素,都要申请一个长度为1000的内存。

3.现在你知道为啥key要用不可变对象了吧?因为不可变对象是常量,每次的哈希值算出来都是固定的,这样就不会出错。比如key=’ABC’,value=10,存储地址为123,假设我突发奇想,把key改成’BCD’,那么当查找’BCD’的value的时候就会去234的地址找,但那里啥也没有,这就乱套了。

3.你看我们上面有一句话:对于不同的key,有很大的概率得到的哈希值也不同。那么有很小的概率不同的key可以得到相同的哈希值了?没错,比如对于我们的例子来说,哈希值只有3位,那么只要元素个数超过1000,就一定会有至少两个key的哈希值相同(鸽笼原理),这种情况叫“冲突”,设计哈希表的时候要采取办法减少冲突,实在冲突了也要想办法补救。不过这是编译器的事情,况且对于初学者的我们来说碰到的冲突的概率基本等于零,就不用操心了。

把数据放入字典的方法,除了最开始的初始化,还可以指定key放入:

>>> 成绩单['赵六']=60
>>> 成绩单
{'张三': 100, '李四': 90, '王五': 80, '赵六': 60}

一个key只能对应一个value,value值以最后一次被放入的为准,后面的值会把前面的值冲掉;如果查询的key不在字典中就会直接报错:

>>> 成绩单['李四']=60
>>> 成绩单
{'张三': 100, '李四': 60, '王五': 80, '赵六': 60}
>>> 成绩单['木人张']
Traceback (most recent call last):
  File "<pyshell#79>", line 1, in <module>
    成绩单['木人张']
KeyError: '木人张'

为了避免出现上面查询的key不在字典内的情况,有两种方法:
1、用in判断key是否在字典内:

>>> '木人张' in 成绩单
False

2、字典的get用法,如果key不存在就返回None,或者指定的内容(None是一个空值,在交互环境不会显示结果):

>>> 成绩单.get('木人张',-1)
-1
>>> 成绩单.get('木人张')
>>> 

要删除一个key,用pop(key)方法,对应的value也会从dict中删除:

>>> 成绩单.pop('张三')
100
>>> 成绩单
{'李四': 60, '王五': 80, '赵六': 60}

和list比较,dict有以下几个特点:
查找和插入的速度极快,不会随着key的增加而变慢;
需要占用大量的内存,内存浪费多。
而list相反:
查找和插入的时间随着元素的增加而增加;
占用空间小,浪费内存很少。
所以,dict是用空间来换取时间的一种方法。
dict可以用在需要高速查找的很多地方,在Python代码中几乎无处不在,正确使用dict非常重要,需要牢记的第一条就是dict的key必须是不可变对象。
要保证hash的正确性,作为key的对象就不能变。在Python中,字符串、整数等都是不可变的,因此,可以放心地作为key。而list是可变的,就不能作为key:

>>> t=[1,2,3,4]
>>> d[t]= 'list'
Traceback (most recent call last):
  File "<pyshell#87>", line 1, in <module>
    d[t]= 'list'
NameError: name 'd' is not defined

set

set和dict类似,是一组单纯key的集合,但不存储value。由于key不能重复,所以,在set中,没有重复的key。
要创建一个set,需要提供一个list作为输入集合:

>>> s = set([1, 2, 3])
>>> s
{1, 2, 3}

注意,传入的参数[1, 2, 3]是一个list,而显示的{1, 2, 3}只是告诉你这个set内部有1,2,3这3个元素,显示的顺序也不表示set是有序的。。
重复元素在set中自动被过滤:

>>> s = set([1, 1, 2, 2, 3, 3])
>>> s
{1, 2, 3}

通过add(key)方法可以添加元素到set中,可以重复添加,但不会有效果:

>>> s.add(4)
>>> s
{1, 2, 3, 4}
>>> s.add(4)
>>> s
{1, 2, 3, 4}

通过remove(key)方法可以删除元素:

>>> s.remove(4)
>>> s
{1, 2, 3}

set可以看成数学意义上的无序和无重复元素的集合,因此,两个set可以做数学意义上的交集、并集等操作:

>>> s1 = set([1, 2, 3])
>>> s2 = set([2, 3, 4])
>>> s1 & s2
{2, 3}
>>> s1 | s2
{1, 2, 3, 4}

set和dict的唯一区别仅在于没有存储对应的value,但是,set的原理和dict一样,所以,同样不可以放入可变对象,因为无法判断两个可变对象是否相等,也就无法保证set内部“不会有重复元素”。


木人张,版权所有丨如未注明 , 均为原创,禁止转载。
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址