Python字典(dictionary)是除串列之外python中最靈活的內置資料結構型別，串列是有序的物件結合，字典是無序的物件集合，兩者之間的區別在于：字典當中的元素是通過鍵來存取的，而不是通過偏移存取，
在串列中使用下標索引可以快速的得到對應的值，那么我們需要做的有兩件事情：
- 怎樣把鍵計算出一個唯一值
- 怎樣把這個唯一值均勻并且唯一的分布在長度固定的串列中
怎樣把鍵計算出一個唯一值
因為字典的鍵是不可變的，可hash的，因此我們可以用hash函式計算key對應的唯一hash值，
怎樣把這個唯一值均勻并且唯一的分布在長度固定的串列中
hash散列是可以把大資料集映射到定長資料集的演算法，因此我們可以對上述計算出來的hash值進行散列，很明顯散列之后會出現散列沖突，因此我們需要處理這種沖突一遍唯一值能夠均勻唯一的分布，這個時候就有兩種處理散列沖突的方法：拉鏈法和開地址法
拉鏈法
把具有相同散列地址的k,v對放在同一個單鏈表中，下面實作兩個函式
put函式：put(slots, key, value)，用來向字典中插入資料get函式：get(slots, key)，用來從字典中讀取資料，
還可以實作更多的函式，比如dict.keys()
#!/usr/bin/env python
# coding=utf-8
slots = []
slotsNum = 32
for _ in range(32):
slots.append([])
def put(slots, key, value):
i = hash(key) % slotsNum
pos = -1
for pos, (k, v) in enumerate(slots[i]):
if key == k:
break
else:
slots[i].append((key, value))
if pos >= 0 and pos < len(slots[i]):
slots[i][pos] = (key, value)
def get(slots, key):
i = hash(key) % slotsNum
for k, v in slots[i]:
if key == k:
return v
else:
raise KeyError(key) # 不存在時拋出例外
put(slots, 'a', 1)
print(get(slots, 'a'))
put(slots, 'b' ,2)
print(get(slots, 'b'))
put(slots, 'a', 3)
print(get(slots, 'a'))
下面將這兩個函式封裝成類
class Dict:
def __init__(self, num):
self.__solts__ = []
self.num = num
for _ in range(num):
self.__solts__.append([])
def put(self, key, value):
i = hash(key) % self.num
for p, (k, v) in enumerate(self.__solts__[i]):
if k == key:
break
else:
self.__solts__[i].append((key, value))
return
self.__solts__[i][p] = (key, value)
def get(self, key):
i = hash(key) % self.num
for k, v in self.__solts__[i]:
if k == key:
return v
raise KeyError(key)
# keys函式
def keys(self):
ret = []
for solt in self.__solts__:
for k, _ in solt:
ret.append(k)
return ret
封裝成類之后，使用方法和Python提供的dict就比較像了
開地址法
Python字典內部實作時處理散列沖突的方法就是開地址法，開地址法在后續補充
-
《Python原始碼剖析》的筆記-第五章 Python中的dict物件
-
【譯】Python字典實作
記得幫我點贊哦！
精心整理了計算機各個方向的從入門、進階、實戰的視頻課程和電子書，按照目錄合理分類，總能找到你需要的學習資料，還在等什么？快去關注下載吧！！！
念念不忘，必有回響，小伙伴們幫我點個贊吧，非常感謝，
我是職場亮哥，YY高級軟體工程師、四年作業經驗，拒絕咸魚爭當龍頭的斜杠程式員，
聽我說，進步多，程式人生一把梭
如果有幸能幫到你，請幫我點個【贊】，給個關注，如果能順帶評論給個鼓勵，將不勝感激，
職場亮哥文章串列：更多文章
本人所有文章、回答都與著作權保護平臺有合作，著作權歸職場亮哥所有，未經授權，轉載必究！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/139155.html
標籤：其他
上一篇：python提取視頻第一幀圖片
下一篇：Python之猜單詞游戲