11.5-Set操作和高性能原理(hash)

很多时候，我们缺的不是能力，
而是如蜗牛般的毅力和坚持。
蜗牛，它虽然爬得很慢，
但它一直坚持前进～

hash：得到一个散列值；给一个门牌号；

不能hash: 没办法放到一个房间中；bytearray

1.集合set: 4个特点

1.集合（set）是一个可变的、无序的、不重复的、散列的元素的序列，相当于一个无序的字典。
2.基本功能是进行成员关系测试和删除重复元素。
3.可以使用大括号 { } 或者 set() 函数创建集合，注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典。

# 集合的定义
set1 = set()  # 特例：定义一个空的集合
set2 = {1,2,3}      |    

# set 与 dict 的区别；
s={1,2,3}  #set
s={} # 字典；   

s6={(1,2),3,'a'}
type(s6）  |    set

# 报错就是不可哈希；不报错就是可哈希；所以哈希是个神奇的东西！
hash(1)    |    1
hash((2,3,'   abc'))
-------------------------------
-2693498530996980930

2. set 的增、删、查、改；

2.1 增加一个元素
set1.add(5)  #增加单个元组：

2.2  set.update() 多元素合并；迭代list多元素添加到set中；
update(*other)合并其他元素到set中去， *other对象必须是可迭代对象；
set1.update([5,6,7,8])

2.3  删除某个值 remove()、discard(elem)、pop()、clear();
set1.remove(1)    #从set中移除一个元素，元素不存在，出KeyError,为什么是KeyError ?
set1.discard(1)    #从set中移除一个元素，元素不存在，什么都不做；
pop() ->item   #移除并返回随机的元素，为什么是任意元素？ 空集返回KeyError异常；
s2 = set([1,3,4,5])       #不要去猜测随机的元素，除非你懂哈希算法；
s2.pop()


clear()  #移除所有元素；

查：无法通过下标索引

改：不可变类型无法修改元素

总结：
1.set的无序是与hash有关的；计算和hash值太大了，找不到规路；
2.set 一定是去重复的结果；

set的元素

1. set元素要求必须可以hash；
2. 目前学过的不可hash的类型有list、set;
3. 元素不可以索引；
4. set可以迭代；

set操作——修改、查询

1. 修改：要么删除，或加入新的元素；
2. 查询：非线性结构，无法索引；
3. 可以迭代所有的元素；
4. 成员运算符： in/not in 判断元素是否在set中；

2. list与set性能测试比较——hash算法(散列算法)的优势：

计算hash会把 里面所有的元素遍历一遍；算门牌号码；
时间复杂度 O（1）
list、set、dict 不可hash；

hash算法优势原因_总结：(hash本质是一种计算公式)
1. 非线性结构set()、dict()效率非常高；大量的元素用在了缓存，不会因为你的元素多了，性能就下降了；
2. set中元素为一个Key，一个Key的hash值是唯一的，不可重复的；set找东西是因为这个唯一值相当于一个唯一编号；找东西特别快；
3.hash就是一种数学公式，计算速度特别快；算完后直接拿这个值；规模再大，也不影响hash的计算；（本质上：相当于利用索引来进行计算；hash是一个O(1）问题） 
4.hash算法有可能出现冲撞的情况, 编号重复就相当于同一个Key；
5.hash算法的优势：散列算法（有某种规路）—位的变化也可以引起hash的变化

lst1=list(range(100))
lst2=list(range(1000000))
%timeit (-1 in lst1)
%timeit (-1 in lst2)
----------------------------------------------------------------
1.56 µs ± 107 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
15.4 ms ± 1.06 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)


lst1=set(range(100))
lst2=set(range(1000000))
%timeit (-1 in lst1)
%timeit (-1 in lst2)
-----------------------------------------
65.4 ns ± 9.19 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
55 ns ± 2.22 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

hash散列算法（有某种规路）—位的变化也可以引起hash的变化
hash(0b1110)    |    14
hash(0b1111)    |    15

总结：
1.数据量越大，越适合使用set，而不是list;
2.set（散列值）是空间换的时间；

set和线性结构

1.线性结构的查询时间复杂度是O(n),即随数据规模的增大而增加；
2.set、dict等结构，内存使用的hash值作为key,时间复杂度可以做到O(1),查询时间与数据规模无关；
3.set（散列值）是空间换的时间；需要非常大的散列空间；

可hash:（不可变类型）

数值型：int,float,complex;
布尔型：True，False

字符串：string,bytes
tuple
None
以上都是不可变类型，成为可哈希类型，hashable;

&set的元素必须是可hash的；