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

集合

簡(jiǎn)介
set ：set對(duì)象是由hashable 對(duì)象所組成的無(wú)序集合，set對(duì)象的每一個(gè)元素要求可進(jìn)行哈希運(yùn)算，set 會(huì)對(duì)內(nèi)部元素進(jìn)行去重，每個(gè)元素在同一個(gè)set 中只會(huì)出現(xiàn)一次，由于set對(duì)象可變性，所以set 對(duì)象自身不可哈希。
frozenset ： frozenset 對(duì)象可以看成一個(gè)不可變set對(duì)象，是一個(gè)可哈希對(duì)象，可以最為frozenset、set 的元素或 dict 的 key 。
創(chuàng)建set對(duì)象
可哈希對(duì)象：在python常見(jiàn)的數(shù)據(jù)類型中，數(shù)值類型，字符串，元組，frozenset，bytes等屬于可哈希對(duì)象。

# 直接創(chuàng)建
s1 = {1, 2, (1, 4), 'b', 0x23, "\x61"}  # 內(nèi)部元素為可哈希對(duì)象
s2 = set()                                        # 空set，不可使用s = { } 

# set( iter ) # 可迭代對(duì)象
s3 = set(range(5))

集合常用方法
frozenset的創(chuàng)建方法和set相同, 其他 共同的方法如下

• len(s)：返回集合 s 中的元素?cái)?shù)量（即 s 的基數(shù)）。
• x in s：檢測(cè) x 是否為 s 中的成員。
• x not in s：檢測(cè) x 是否非 s 中的成員。
  set方法
  對(duì)于可變的set 對(duì)象，可以對(duì)其進(jìn)行增加(add)，刪除(remoe、pop、discard、clear)等操作

  # 向集合增加一個(gè)元素
  s1 = set(range(5))
  s1.add(6)
  s1.add(4)        # 當(dāng)元素在set中已經(jīng)存在，添加后set會(huì)自動(dòng)對(duì)其去重
  # 集合中刪除元素
  s1.remove(6)  # 從集合中移除元素 6。如果 6 不存在于集合中則會(huì)引發(fā)KeyError。
  s1.discard(4)        # 如果元素 4 存在于集合中則將其移除，無(wú)返回值
  s1.pop()                # 從集合中移除并返回任意一個(gè)元素。如果集合為空則會(huì)引發(fā)KeyError。
  s1.clear()              # 從集合中移除所有元素

  集合運(yùn)算

  1. isdisjoint(other)
     如果集合中沒(méi)有與 other 共有的元素則返回 True。當(dāng)且僅當(dāng)兩個(gè)集合的交集為空集合時(shí)，兩者為不相交集合。
  2. issubset(other)
     set <= other
     檢測(cè)是否集合中的每個(gè)元素都在 other 之中。
     set < other
     檢測(cè)集合是否為 other 的真子集，即 set <= other and set != other。
  3. issuperset(other)
     set >= other
     檢測(cè)是否 other 中的每個(gè)元素都在集合之中。
     set > other
     檢測(cè)集合是否為 other 的真超集，即 set >= other and set != other。
  4. union(*others)
     set | other | ...
     返回一個(gè)新集合，其中包含來(lái)自原集合以及 others 指定的所有集合中的元素。
  5. intersection(*others)
     set & other & ...
     返回一個(gè)新集合，其中包含原集合以及 others 指定的所有集合中共有的元素。
  6. difference(*others)
     set - other - ...
     返回一個(gè)新集合，其中包含原集合中在 others 指定的其他集合中不存在的元素。
  7. symmetric_difference(other)
     set ^ other
     返回一個(gè)新集合，其中的元素或?qū)儆谠匣驅(qū)儆?other 指定的其他集合，但不能同時(shí)屬于兩者。
  8. copy()
     返回原集合的淺拷貝。

可以使用set運(yùn)算直接進(jìn)行運(yùn)算，運(yùn)算方式和數(shù)學(xué)中集合運(yùn)算方式相同，例如：

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
# 對(duì)稱差集: 返回兩個(gè)集合中不同的元素
s6 = s1 ^ s2     #  {0, 1, 2, 3, 4, 10, 11, 12, 13, 14}

frozenset 和 set 對(duì)象的比較是基于內(nèi)部元素的比較，兩個(gè)對(duì)象之間仍可以進(jìn)行以上運(yùn)算，但是運(yùn)算結(jié)果是一個(gè)frozenset 對(duì)象，而不是set對(duì)象；

字典dict

字典可以將一個(gè)可哈希值映射到一個(gè)任意對(duì)象，可以通過(guò)映射關(guān)系快速查找對(duì)應(yīng)數(shù)據(jù)；所以在dict中的每一項(xiàng)由一個(gè)key-value對(duì)組成(也稱pairs) ，其中key 會(huì)作為字典快速查找的的一個(gè)關(guān)鍵數(shù)據(jù)，所以要求一個(gè)字典中鍵必須是唯一，并可哈希，若在賦值過(guò)程中出現(xiàn)相同的key值，后者將會(huì)覆蓋之前的內(nèi)容。
創(chuàng)建dict對(duì)象

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

# key = value 鍵值對(duì)方式
d1 = dict( a=1,b=2,c=3 )       #   {'a':1, 'b':2, 'c':3}
# mapping 對(duì)象創(chuàng)建
d2 = dict(d1, d =4 )               # {'a':1, 'b':2, 'c':3, 'd':4}
# iterable對(duì)象,對(duì)象中每一個(gè)元素必須有兩個(gè)值分別作為key 和 value
d3 = dicrt([(1,2),(3,4),(5,6)]) # {1:2, 3:4, 5:6}

字典中方法

• len(d)：返回字典 d 中 的項(xiàng)數(shù)(長(zhǎng)度)
• d[key]：返回 d 中以 key 為鍵的項(xiàng)。如果映射中不存在 key 則會(huì)引發(fā)KeyError；如果dict的子類中重新定義了__massing__()方法，d[key]將會(huì)以__missing__()的return值作為d[key] 的內(nèi)容

# 該類實(shí)現(xiàn)了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] 設(shè)為 value。
• del d[key]：將 d[key] 從 d 中移除。如果映射中不存在 key 則會(huì)引發(fā)KeyError。
• key in d：如果 d 中存在鍵 key 則返回 True，否則返回 False。
• iter(d)：返回以字典的鍵為元素的迭代器。
• clear()：移除字典中的所有元素。
• copy()：對(duì)字典進(jìn)行淺拷貝。
• dict.fromkeys(iterable[, value])：使用來(lái)自 iterable 的鍵創(chuàng)建一個(gè)新字典，并將鍵值設(shè)為 value。fromkeys() 屬于類方法，會(huì)返回一個(gè)新字典。 value 默認(rèn)為 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 未給出則默認(rèn)為 None，因
  而此方法絕不會(huì)引發(fā)KeyError。

  d = {'a':1, 'b':2, 'c':3, 'd':4}
  d["k"]                                          # 找不到"k",將會(huì)報(bào)錯(cuò)
  d.get("k", -1)  # .get(key, default)    # 找不到會(huì)返回設(shè)定的默認(rèn)值-1
  d.setdefault("k", 10)                   # 若"k" 存在，返回k的值，若不存在"k"不存在將會(huì)執(zhí)行賦值操作d["k"] = 10，并返回 10

• setdefault(key[, default]):如果字典存在鍵 key ，返回它的值。如果不存在，插入值為 default 的鍵 key ，并返回 default 。 default
  默認(rèn)為 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()：返回由字典項(xiàng) ((鍵, 值) 對(duì)) 組成的一個(gè)新視圖。參見(jiàn)視圖對(duì)象文檔。
• keys()：返回由字典鍵組成的一個(gè)新視圖。參見(jiàn)視圖對(duì)象文檔。
• pop(key[, default])：如果 key 存在于字典中則將其移除并返回其值，否則返回 default。如果 default 未給出且 key 不存
  在于字典中，則會(huì)引發(fā)KeyError。
• popitem()：從字典中移除并返回一個(gè) (鍵, 值) 對(duì)。鍵值對(duì)會(huì)按 LIFO (后進(jìn)先出) 的順序被返回。
• popitem()：適用于對(duì)字典進(jìn)行消耗性的迭代，這在集合算法中經(jīng)常被使用。如果字典為空，調(diào)用popitem() 將引發(fā)KeyError。
  在 3.7 版更改: 現(xiàn)在會(huì)確保采用 LIFO 順序。在之前的版本中， * popitem() 會(huì)返回一個(gè)任意的鍵/值
  對(duì)。

update([other])：使用來(lái)自 other 的鍵/值對(duì)更新字典，覆蓋原有的鍵。返回 None。

• update() 接受另一個(gè)字典對(duì)象，或者一個(gè)包含鍵/值對(duì)（以長(zhǎng)度為2的元組或其他可迭代對(duì)象表示）的可迭代對(duì)象。如果給出了關(guān)鍵字參數(shù)，則會(huì)以其所指定的鍵/值對(duì)更新字典: d.update(red=1,blue=2)。
• values()：返回由字典值組成的一個(gè)新視圖。參見(jiàn)視圖對(duì)象文檔。
  兩個(gè)字典的比較當(dāng)且僅當(dāng)具有相同的 (鍵, 值) 對(duì)時(shí)才會(huì)相等。順序比較 (’<’, ’<=’, ’>=’, ’>’) 會(huì)引發(fā)TypeError。
  字典會(huì)保留插入時(shí)的順序。請(qǐng)注意對(duì)鍵的更新不會(huì)影響順序。刪除并再次添加的鍵將被插入到末尾。
  字典的遍歷
  當(dāng)字典進(jìn)行遍歷時(shí)候，遍歷字典的dict.keys(), dict.values() 和dict.items() 時(shí)，所返回的對(duì)象是視圖對(duì)象。該對(duì)象提供字典條目的一個(gè)動(dòng)態(tài)視圖，這意味著當(dāng)字典改變時(shí)，視圖也會(huì)相應(yīng)改變，當(dāng)字典發(fā)生值修改時(shí)，字典將會(huì)立即反應(yīng)，但當(dāng)字典的長(zhǎng)度發(fā)生修改時(shí)候，將會(huì)立即停止遍歷，并返回錯(cuò)誤信息，但之前做的遍歷修改已經(jīng)保存。

d = {'a':1, 'b':2, 'c':3, 'd':4}
for key in d.keys():
    d.pop(key)                   #  改變字典長(zhǎng)度，將會(huì)報(bào)錯(cuò)

# 解決方案
d = {'a':1, 'b':2, 'c':3, 'd':4}
for key in list(d.keys()):   # 此時(shí)將dict視圖對(duì)象提前遍歷生成列表，再對(duì)列表進(jìn)行遍歷，不是對(duì)視圖對(duì)象的遍歷，將不會(huì)報(bào)錯(cuò)
    d.pop(key)