python利用拉鏈法實(shí)現(xiàn)字典方法示例
前言
字典也叫散列表,最大的特點(diǎn)是通過key來查找其對(duì)應(yīng)的值其時(shí)間復(fù)雜度是O(1)，下面這篇文章就來給大家介紹介紹python利用拉鏈法實(shí)現(xiàn)字典的方法。
在Python中怎樣用列表實(shí)現(xiàn)字典?
用列表實(shí)現(xiàn)字典最大的問題就是解決hash沖突,如果在列表中通過計(jì)算不同的key得到相同的相同了位置,這時(shí)候應(yīng)該怎么辦？
最簡(jiǎn)單的辦法就是使用拉鏈法.
拉鏈法:就是在一個(gè)列表中每個(gè)位置再添加一個(gè)列表,這樣就算是有hash沖突也能夠存儲(chǔ)進(jìn)去,當(dāng)選取的hash函數(shù)足夠好,
num的數(shù)足夠大,就能夠保證列表中的每一個(gè)列表里面只有一個(gè)元素。根據(jù)key計(jì)算的元素所在的位置,然后來取值就能達(dá)
到O(1)的時(shí)間。
方法示例
class MyDict:
def __init__(self, num=100): # 指定列表大小
self._num = num
self._lst = []
for _ in range(self._num):
self._lst.append([])
def update(self, key, value): # 添加 key-value
key_index = hash(key) % self._num
for i, (k, v) in enumerate(self._lst[key_index]):
if key == k:
self._lst[key_index][i] = [key, value]
break
else:
self._lst[key_index].append([key, value])
def get(self, key): # 根據(jù)指定的 key 彈出值
key_index = hash(key) % self._num
for k, v in self._lst[key_index]:
if k == key:
return v
else:
raise KeyError('No such {} key'.format(key))
def pop(self, key): # 根據(jù) key 彈出元素 并且刪除
key_index = hash(key) % self._num
for i, (k, v) in enumerate(self._lst[key_index]):
if k == key:
result = v
self._lst.pop(i)
return result
else:
raise KeyError('No such {} key'.format(key))
def __getitem__(self, key): # 可以通過下標(biāo)來取值
key_index = hash(key) % self._num
for k, v in self._lst[key_index]:
if k == key:
return v
else:
raise KeyError('No such {} key'.format(key))
def keys(self): # 取得所有的key
for index in range(self._num):
for k, v in self._lst[index]:
yield k
def values(self): # 取得所有的 value
for index in range(self._num):
for k, v in self._lst[index]:
yield v
def items(self): # 取得所有的條目
for index in range(self._num):
for item in self._lst[index]:
yield item
通過key查到的時(shí)間，可見下圖
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。
相關(guān)文章
實(shí)例講解python中的序列化知識(shí)點(diǎn)
本篇文章通過代碼實(shí)例給大家詳細(xì)分享了關(guān)于python中的序列化知識(shí)點(diǎn)內(nèi)容，有興趣的朋友們可以學(xué)習(xí)下。2018-10-10
Python中NumPy的ufuncs函數(shù)實(shí)例
這篇文章主要介紹了Python中NumPy的ufuncs函數(shù)實(shí)例,NumPy是一個(gè)開源的Python科學(xué)計(jì)算庫(kù),使用NumPy，就可以很自然地使用數(shù)組和矩陣,本文主要介紹Python Numpy ufuncs通用函數(shù),需要的朋友可以參考下2023-07-07
對(duì)Python 檢查文件名是否規(guī)范的實(shí)例詳解
今天小編就為大家分享一篇對(duì)Python 檢查文件名是否規(guī)范的實(shí)例詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-06-06
使用Python發(fā)送Post請(qǐng)求以及解析響應(yīng)結(jié)果
發(fā)送post的請(qǐng)求參考例子很簡(jiǎn)單,實(shí)際遇到的情況卻是很復(fù)雜的,下面這篇文章主要給大家介紹了關(guān)于如何使用Python發(fā)送Post請(qǐng)求以及解析響應(yīng)結(jié)果的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-06-06
Python的pdfplumber庫(kù)將pdf轉(zhuǎn)為圖片的實(shí)現(xiàn)
本文主要介紹了Python的pdfplumber庫(kù)將pdf轉(zhuǎn)為圖片的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
django項(xiàng)目登錄中使用圖片驗(yàn)證碼的實(shí)現(xiàn)方法
這篇文章主要介紹了django項(xiàng)目登錄中使用圖片驗(yàn)證碼的實(shí)現(xiàn)代碼，代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-08-08
opencv+playwright滑動(dòng)驗(yàn)證碼的實(shí)現(xiàn)
滑動(dòng)驗(yàn)證碼是常見的驗(yàn)證碼之一,本文主要介紹了opencv+playwright滑動(dòng)驗(yàn)證碼的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2023-11-11
使用pyqt5搭建yolo3目標(biāo)識(shí)別界面的方法
這篇文章主要介紹了使用pyqt5搭建yolo3目標(biāo)識(shí)別界面的方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
淺談python的輸入輸出，注釋，基本數(shù)據(jù)類型
這篇文章主要介紹了python的輸入輸出，注釋，基本數(shù)據(jù)類型，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04
咳咳，又是一款新的小游戲，就是大家熟悉的王者~本文將利用python來實(shí)現(xiàn)高（di）配版的王者的小游戲，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-03-03