python的内置類型(3)---字典和集合

文章目錄

• • • 1. 字典集合簡介
    • 2. 字典常用的内置函數
    • 3. 集合常用的内置函數
    • 4. 字典的排序
    • 5. 插入 查找 删除操作

1. 字典集合簡介

• 字典是一系列無序元素的組合，其長度大小可變，元素可以任意地删減和改變。這裡的元素，是一對鍵（key）和值（value）的配對。
• 相比于清單和元組，字典的性能更優，特别是對于查找、添加和删除操作，字典都能在常數時間複雜度内完成。
• 而集合和字典基本相同，唯一的差別，就是集合沒有鍵和值的配對，是一系列無序的、唯一的元素組合。

• 集合并不支援索引操作，因為集合本質上是一個哈希表，和清單不一樣

2. 字典常用的内置函數

方法	說明
dict代表字典對象
dict.clear()	清空字典
dict.pop(key)	移除鍵，同時傳回此鍵所對應的值(字典是無序的,随機移除,慎用)
dict.copy()	傳回字典D的副本,隻複制一層(淺拷貝)
dict.update(D2)	将字典 D2 合并到D中，如果鍵相同，則此鍵的值取D2的值作為新值
dict.get(key, default=None)	傳回鍵key所對應的值,如果沒有此鍵，則傳回default
dict.keys()	傳回可疊代的 dict_keys 集合對象
dict.values()	傳回可疊代的 dict_values 值對象
dict.items()	傳回可疊代的 dict_items 對象

3. 集合常用的内置函數

方法	說明
S表示集合對象
S.add(e)	在集合中添加一個新的元素e；如果元素已經存在，則不添加
S.remove(e)	從集合中删除一個元素，如果元素不存在于集合中，則會産生一個KeyError錯誤
S.discard(e)	從集合S中移除一個元素e,在元素e不存在時什麼都不做;
S.clear()	清空集合内的所有元素
S.copy()	将集合進行一次淺拷貝
S.pop()	從集合S中删除一個随機元素;如果此集合為空，則引發KeyError異常
S.update(s2)	等同于 S l= s2, 用 S與s2得到的全集更新變量S
S.difference(s2)	S - s2 補集運算，傳回存在于在S中，但不在s2中的所有元素的集合
S.difference_update(s2)	等同于 S -= s2
S.intersection(s2)	等同于 S & s2
S.intersection_update(s2)	等同于S &= s2
S.isdisjoint(s2)	如果S與s2交集為空傳回True,非空則傳回False
S.issubset(s2)	如果S與s2交集為非空傳回True,空則傳回False
S.issuperset(…)	如果S為s2的超集傳回True,否則傳回False
S.symmetric_difference(s2)	傳回對稱補集, 等同于 S ^ s2
S.symmetric_difference_update(s2)	等同于 S ^= s2, 用 S 與 s2 的對稱補集更新 S
S.union(s2)	生成 S 與 s2的全集, 等同于 S += S2

4. 字典的排序

可以參考我的另一篇文章:

python中sort排序與sorted排序(清單 字典排序)

5. 插入 查找 删除操作

• 插入操作

  每次向字典或集合插入一個元素時，Python會首先計算鍵的哈希值（hash(key)），再和 mask =PyDicMinSize - 1做與操作，計算這個元素應該插入哈希表的位置index = hash(key) & mask。如果哈希表中此位置是空的，那麼這個元素就會被插入其中。而如果此位置已被占用，Python便會比較兩個元素的哈希值和鍵是否相等。若兩者都相等，則表明這個元素已經存在，如果值不同，則更新值。若兩者中有一個不相等，這種情況我們通常稱為哈希沖突（hash collision），意思是兩個元素的鍵不相等，但是哈希值相等。這種情況下，Python便會繼續尋找表中空餘的位置，直到找到位置為止。

  值得一提的是，通常來說，遇到這種情況，最簡單的方式是線性尋找，即從這個位置開始，挨個往後尋找空位。當然，Python内部對此進行了優化讓這個步驟更加高效。

• 查找操作

  查找操作和前面的插入操作類似，Python會根據哈希值，找到其應該處于的位置；然後，比較哈希表這個位置中元素的哈希值和鍵，與需要查找的元素是否相等。如果相等，則直接傳回；如果不等，則繼續查找，直到找到空位或者抛出異常為止。

• 删除操作

  删除操作對于删除操作，Python會暫時對這個位置的元素，賦于一個特殊的值，等到重新調整哈希表的大小時，再将其删除。不難了解，哈希沖突的發生，往往會降低字典和集合操作的速度。是以，為了保證其高效性，字典和集合内的哈希表，通常會保證其至少留有1/3的剩餘空間。随着元素的不停插入，當剩餘空間小于1/3時，Python會重新擷取更大的記憶體空間，擴充哈希表。不過，這種情況下，表内所有的元素位置都會被重新排放。雖然哈希沖突和哈希表大小的調整，都會導緻速度減緩，但是這種情況發生的次數極少。是以，平均情況下，這仍能保證插入、查找和删除的時間複雜度為O(1)。