python的dict 和set

一、dict
dict是python内置的字典，使用key-val存储，在其他语言中 也叫map,具有极快的查找速度，不会随着数据量的变大而变慢（list就会随着长度变长，耗时变长）
先看看dict的使用
1、用法
>>> d = {'李双双':'女','张cc':'男'}
>>> d
>>> {'张cc': '男', '李双双': '女'}
2、看了dict,那为什么dict的速度会那么快呢？

1）dict的底层实现
dict的底层实现是哈希表（hash tables）,通过关键值对(key-val) 而直接进行访问数据。它通过把 key 和value 映射到表中的一个位置来进行访问，这种结构查询快，更新也非常快。在对key进行 hash的时候，如果遇到相同的hash值，也就是哈希冲突，如何解决呢？一般的做法有两种，一种是链接法，一种是开发寻址法。python选择后者。
开放寻址法：所有的元素都存放在散列表里，当产生哈希冲突时，通过一个探测函数计算出下一个候选位置，如果下一个获选位置还是有冲突，那么不断通过探测函数往下找，直到找个一个空槽来存放待插入元素
2）list的底层实现
假设字典包含了1万个汉字，
我们要查某一个字，一个办法是把字典从第一页往后翻，直到找到我
们想要的字为止，这种方法就是在list中查找元素的方法，list越大，查
找越慢。

第二种方法是先在字典的索引表里（比如部首表）查这个字对应的页
码，然后直接翻到该页，找到这个字。无论找哪个字，这种查找速度
都非常快，不会随着字典大小的增加而变慢。
dict就是第二种实现方式
3、访问元素
>>> d['李双双']
>>> 女
4、增加元素
>>> d['王某某'] = '女'
>>> d
>>> {'张cc': '男', '李双双': '女', '王某某': '女'}
5、修改元素
>> d['李双双'] = '男'
>>> d
>>> {'张cc': '男', '李双双': '男', '王某某': '女'}
6、 判断dict的key是否存在

1）一是通过in判断key是否存在
>>> if('李双双' in d):
>>> print('存在')
>>> 存在

2. 通过dict提供的get方法，如果key不存在，可以返回None，或者自己指定的value

   print(d.get('李双双2'))
   None

   if(not d.get('李双双2')):
   print('不存在')
   不存在

   if(not d.get('李双双2',False)):
   print('不存在')
   不存在
   7、元素的删除 使用pop(key)

   d
   {'张cc': '男', '李双双': '男', '王某某': '女'}
   d.pop('王某某')
   '女'
   d
   {'张cc': '男', '李双双': '男'}

8、和list比较的优缺点
dict
a.查找和插入的速度比较快，不会随着key的增加而变慢
b.空间使用较多，需要占用较多的内存
list
a.查找和插入的速度会随着key的增加而变慢
b.空间使用少，浪费内存少

二.set
set 就类似于一组key的无序，不重复的集合
1、定义
使用set 要提供一个list作为输入集合,重复的值会被过滤掉

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

2、元素的添加

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

3、元素的删除

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

4、set的交集
 
>>> s
>>> {1, 2, 3}
>>> n = set([2,3,4])
>>> s&n
>>> {2, 3}

5、set的并集

>>> s | n
>>> {1, 2, 3, 4}

set的原理和dict一样，所以，同样不可以放入可变对象，因为无法判断两个可变对象是否相等，也就无法保证set内部“不会有重复元素”