哈希表 - 集合(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)