哈希表 - 集合(set) 和 字典(dict)

集合

简介
set ：set对象是由hashable 对象所组成的无序集合，set对象的每一个元素要求可进行哈希运算，set 会对内部元素进行去重，每个元素在同一个set 中只会出现一次，由于set对象可变性，所以set 对象自身不可哈希。
frozenset ： frozenset 对象可以看成一个不可变set对象，是一个可哈希对象，可以最为frozenset、set 的元素或 dict 的 key 。
创建set对象
可哈希对象：在python常见的数据类型中，数值类型，字符串，元组，frozenset，bytes等属于可哈希对象。

# 直接创建
s1 = {1, 2, (1, 4), 'b', 0x23, "\x61"}  # 内部元素为可哈希对象
s2 = set()                                        # 空set，不可使用s = { } 

# set( iter ) # 可迭代对象
s3 = set(range(5))

集合常用方法
frozenset的创建方法和set相同, 其他 共同的方法如下

• len(s)：返回集合 s 中的元素数量（即 s 的基数）。
• x in s：检测 x 是否为 s 中的成员。
• x not in s：检测 x 是否非 s 中的成员。
  set方法
  对于可变的set 对象，可以对其进行增加(add)，删除(remoe、pop、discard、clear)等操作

  # 向集合增加一个元素
  s1 = set(range(5))
  s1.add(6)
  s1.add(4)        # 当元素在set中已经存在，添加后set会自动对其去重
  # 集合中删除元素
  s1.remove(6)  # 从集合中移除元素 6。如果 6 不存在于集合中则会引发KeyError。
  s1.discard(4)        # 如果元素 4 存在于集合中则将其移除，无返回值
  s1.pop()                # 从集合中移除并返回任意一个元素。如果集合为空则会引发KeyError。
  s1.clear()              # 从集合中移除所有元素

  集合运算

  1. isdisjoint(other)
     如果集合中没有与 other 共有的元素则返回 True。当且仅当两个集合的交集为空集合时，两者为不相交集合。
  2. issubset(other)
     set <= other
     检测是否集合中的每个元素都在 other 之中。
     set < other
     检测集合是否为 other 的真子集，即 set <= other and set != other。
  3. issuperset(other)
     set >= other
     检测是否 other 中的每个元素都在集合之中。
     set > other
     检测集合是否为 other 的真超集，即 set >= other and set != other。
  4. union(*others)
     set | other | ...
     返回一个新集合，其中包含来自原集合以及 others 指定的所有集合中的元素。
  5. intersection(*others)
     set & other & ...
     返回一个新集合，其中包含原集合以及 others 指定的所有集合中共有的元素。
  6. difference(*others)
     set - other - ...
     返回一个新集合，其中包含原集合中在 others 指定的其他集合中不存在的元素。
  7. symmetric_difference(other)
     set ^ other
     返回一个新集合，其中的元素或属于原集合或属于 other 指定的其他集合，但不能同时属于两者。
  8. copy()
     返回原集合的浅拷贝。

可以使用set运算直接进行运算，运算方式和数学中集合运算方式相同，例如：

s1 = set(range(10))
s2 = set(range(5,15))
# s1 ==> {0, 1, 2, 3,  4,  5,   6,   7,   8,   9}
# s2 ==> {5, 6, 7, 8,  9, 10, 11, 12, 13, 14}
# 交集
s3 = s1 & s2     #   {5, 6, 7, 8, 9}
# 并集
s3 = s1 | s2      #   {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
# 差集：从s1 中减去s2 中存在的元素
s5 = s1 - s2     #   {10, 11, 12, 13, 14}
# 子集: 
{1,2,4} <= {1,2,3,4}  # True
# 对称差集: 返回两个集合中不同的元素
s6 = s1 ^ s2     #  {0, 1, 2, 3, 4, 10, 11, 12, 13, 14}

frozenset 和 set 对象的比较是基于内部元素的比较，两个对象之间仍可以进行以上运算，但是运算结果是一个frozenset 对象，而不是set对象；

字典dict

字典可以将一个可哈希值映射到一个任意对象，可以通过映射关系快速查找对应数据；所以在dict中的每一项由一个key-value对组成(也称pairs) ，其中key 会作为字典快速查找的的一个关键数据，所以要求一个字典中键必须是唯一，并可哈希，若在赋值过程中出现相同的key值，后者将会覆盖之前的内容。
创建dict对象

1. class dict(**kwarg)
2. class dict(mapping, **kwarg)
3. class dict(iterable, **kwarg)

# key = value 键值对方式
d1 = dict( a=1,b=2,c=3 )       #   {'a':1, 'b':2, 'c':3}
# mapping 对象创建
d2 = dict(d1, d =4 )               # {'a':1, 'b':2, 'c':3, 'd':4}
# iterable对象,对象中每一个元素必须有两个值分别作为key 和 value
d3 = dicrt([(1,2),(3,4),(5,6)]) # {1:2, 3:4, 5:6}

字典中方法

• len(d)：返回字典 d 中 的项数(长度)
• d[key]：返回 d 中以 key 为键的项。如果映射中不存在 key 则会引发KeyError；如果dict的子类中重新定义了__massing__()方法，d[key]将会以__missing__()的return值作为d[key] 的内容

# 该类实现了collections.defaultdict() 类相同的方法 
class MyDict(dict):
    def __init__(self, seq=list):
        super().__init__
        self.seq = seq

    def __missing__(self, key):
        return self.setdefault(key,self.seq())

mydic = MyDict(set)

for i in "abc":
    mydic[i].add(1)

mydic["c"]          # {1}
mydic               # {'a': {1}, 'b': {1}, 'c': {1}}

• d[key] = value：将 d[key] 设为 value。
• del d[key]：将 d[key] 从 d 中移除。如果映射中不存在 key 则会引发KeyError。
• key in d：如果 d 中存在键 key 则返回 True，否则返回 False。
• iter(d)：返回以字典的键为元素的迭代器。
• clear()：移除字典中的所有元素。
• copy()：对字典进行浅拷贝。
• dict.fromkeys(iterable[, value])：使用来自 iterable 的键创建一个新字典，并将键值设为 value。fromkeys() 属于类方法，会返回一个新字典。 value 默认为 None。

  # 批量造 key, 用列表，字符串，
  # .fromkeys(iter, value)
  d8 = dict.fromkeys(range(4), 100)
  d8       #  {0: 100, 1: 100, 2: 100, 3: 100}

• get(key[, default])：如果 key 存在于字典中则返回 key 的值，否则返回 default。如果 default 未给出则默认为 None，因
  而此方法绝不会引发KeyError。

  d = {'a':1, 'b':2, 'c':3, 'd':4}
  d["k"]                                          # 找不到"k",将会报错
  d.get("k", -1)  # .get(key, default)    # 找不到会返回设定的默认值-1
  d.setdefault("k", 10)                   # 若"k" 存在，返回k的值，若不存在"k"不存在将会执行赋值操作d["k"] = 10，并返回 10

• setdefault(key[, default]):如果字典存在键 key ，返回它的值。如果不存在，插入值为 default 的键 key ，并返回 default 。 default
  默认为 None。

  d = {'a':1, 'b':2, 'c':3, 'd':4}
  d.setdefault("k",100) # setdefault(k, default=None)  
  d                                                # {'a':1, 'b':2, 'c':3, 'd':4,'k':100}

• items()：返回由字典项 ((键, 值) 对) 组成的一个新视图。参见视图对象文档。
• keys()：返回由字典键组成的一个新视图。参见视图对象文档。
• pop(key[, default])：如果 key 存在于字典中则将其移除并返回其值，否则返回 default。如果 default 未给出且 key 不存
  在于字典中，则会引发KeyError。
• popitem()：从字典中移除并返回一个 (键, 值) 对。键值对会按 LIFO (后进先出) 的顺序被返回。
• popitem()：适用于对字典进行消耗性的迭代，这在集合算法中经常被使用。如果字典为空，调用popitem() 将引发KeyError。
  在 3.7 版更改: 现在会确保采用 LIFO 顺序。在之前的版本中， * popitem() 会返回一个任意的键/值
  对。

update([other])：使用来自 other 的键/值对更新字典，覆盖原有的键。返回 None。

• update() 接受另一个字典对象，或者一个包含键/值对（以长度为2的元组或其他可迭代对象表示）的可迭代对象。如果给出了关键字参数，则会以其所指定的键/值对更新字典: d.update(red=1,blue=2)。
• values()：返回由字典值组成的一个新视图。参见视图对象文档。
  两个字典的比较当且仅当具有相同的 (键, 值) 对时才会相等。顺序比较 (’<’, ’<=’, ’>=’, ’>’) 会引发TypeError。
  字典会保留插入时的顺序。请注意对键的更新不会影响顺序。删除并再次添加的键将被插入到末尾。
  字典的遍历
  当字典进行遍历时候，遍历字典的dict.keys(), dict.values() 和dict.items() 时，所返回的对象是视图对象。该对象提供字典条目的一个动态视图，这意味着当字典改变时，视图也会相应改变，当字典发生值修改时，字典将会立即反应，但当字典的长度发生修改时候，将会立即停止遍历，并返回错误信息，但之前做的遍历修改已经保存。

d = {'a':1, 'b':2, 'c':3, 'd':4}
for key in d.keys():
    d.pop(key)                   #  改变字典长度，将会报错

# 解决方案
d = {'a':1, 'b':2, 'c':3, 'd':4}
for key in list(d.keys()):   # 此时将dict视图对象提前遍历生成列表，再对列表进行遍历，不是对视图对象的遍历，将不会报错
    d.pop(key)