python之hash散列,常見的散列hash算法有哪些

本文目錄一覽：

• 1、流暢的Python
• 2、Python字典的底層實現
• 3、Python數據結構-哈希表（Hash Table）
• 4、Python哈希函數什麼情況下拋出異常

流暢的Python

第一章 Python數據模型

魔術方法(magic method)或者說雙下方法(dunder method)表示特殊方法。以雙下劃線開始和結束，比如 getitem

len()需要實現 len ()

[]和切片需要實現 getitem ()

可迭代或者反向迭代，至少需要實現 getitem ()

in需要實現 contains (),如果沒有實現，則至少需要實現 getitem (),因為它可以自己做迭代搜索

repr,它能把一個對象有字符串的形式表達出來，repr就是通過 repr 這個特殊方法來得到一個字符串的表達形式的。如果沒有實現 repr ，輸出實例時，得到的字符串就是Vector object at 0x10e100070之類的

注意 repr 和 str 的區別，後者是在str()函數中使用，或者是在用print函數打印的時候才被調用。

如果一個對象沒有 str 函數，而Python又需要調用它的時候，解釋器會用 repr 作為替代。

在if，while或者and or not運算符中，為了判定一個值x是真還是假，Python會調用bool(x),這個函數只能返回True或者False。

bool(x)，其實調用的是x. bool ()的結果，如果不存在 bool ,bool(x)會嘗試調用x. len ().若返回0，則bool會返回False，否則True。

第二章 序列構成的數組

序列類型概覽

1、容器序列

list、tuple、collections.deque這些序列都能存放不同類型的數據

2、扁平序列

str、bytes、bytearray、memoryview和array.array，這些序列只能容納一種類型。

注意：容器序列存放的是它們所包含任意類型的對象的引用，二扁平序列里存放的是值而不是引用。換句話說，扁平序列其實是一系列連續的內存空間，但是扁平序列只能存放字符、字節和數值這種基礎類型。

可變序列

list、bytearray、array.array、collections.deque和memoryview

不可變序列

tuple、str和bytes

列表推倒

symbols = ‘abc’

codes = []

for symbol in symbols:

codes.append(symbol)

codes = [symbol for symbol in symbols]

第一種就是正常的for循環，第二種就是列表推導

生成器表達式

雖然可以用列表推導來初始化元組、數組或者其他序列類型，但是生成器表達式更好。因為生成器表達式背後遵循了迭代器協議，可以逐個產出元素，而不是先建立一個完整的列表，然後再把這個列表傳遞到某個構造函數裡面。

和列表推導差不多，就是方括號改成圓括號

symbols = ‘abc’

array.array(‘i’, (symbol for symbol in symbols))

元組的應用：

1、當作記錄，因為它是不可更改的

2、元組拆包，可以得到裡面的數據 類似於 a, b = (first, second)

3、具名元組，從collections.namedtuple生成具名元組，除了繼承普通元組的屬性，具名元組還有一些自己專有的屬性。_fields類屬性，類方法_make(iterable)和實例方法_asdict()。

_fields類屬性：包含具名元組的各個字段名稱

_make(iterable)：通過_make()接受一個可迭代對象來生成這個類的一個實例

_asdict()：把具名元組以collections.ordereddict的形式返回。

切片：

s[a:b:c] s在a到b之間以c為間隔取值，c還可以是負，負值意味着取反。如s[::-1]意味着，將這個list倒置

給切片賦值：

l=list(range(5))

print(l) [0,1,2,3,4]

l[1:3]=[20,30]

print(l) [0,20,30,4]

l[1:3]=100 報錯，需要寫成[100]

對序列使用+和*

+是把兩個序列合併，在拼接過程中，兩個被操作對序列都不會被修改，Python會新建一個包含同類型數據對序列作為拼接結果。

是把序列複製幾份然後拼接起來。例如 l=[1,2] l 3=[1,2,1,2,1,2] *也會構建新的序列而不修改原有的對象。

序列的增量賦值

+=背後的特殊方法是 iadd ,但是如果一個類沒有實現這個方法，Python會退一步調用 add

第三章 字典和集合

字典推導

country_code = {country: code for code, country in dial_doces} dial_doces是一個元組的list

{code:country.upper() for country, code in country_code.items() if code66}

第一個是把國家作為鍵，第二個把code作為鍵

if key not in my_dict:

my_dict[key]=[]

my_dict[key].append(new_value)

可以直接寫成my_dict.setdefault(key,[]).append(new_value)

所有映射類型在處理找不到的鍵的時候，都會牽扯到 missing 方法，

集合

{1,2}這是集合

集合推導

from unicodedata import name

{chr(i) for i in range(32,256) if ‘SIGN’ in name(chr(i),”)}

a.union(b,c,d) 這裡a必須是set，b、c和d則可以是任何類型的可迭代對象

為了獲取dict[key]背後的值，python會調用hash(key)來計算key的散列值，然後去散列表裡面查找表元，若找到的表元是空的，則拋keyerror，若不是空的，則表元里會有一對found_key:found_value，這個時候Python會檢驗key == found_key是否為真，如果他們相等的話，會返回found_value。如果不等，說明出現了散列衝突。發生這種情況的原因是，散列表所做的只是把隨機的元素映射到只有幾位的數字上，而散列表本身的索引又只依賴於這個數字的一部分。為了解決散列衝突，算法會在散列值中另外取幾位，然後用特殊方法處理一下，把新得到的數字再當作索引來尋找表元。

dict的實現

1、支持hash()函數，並且通過 hash ()方法所得到的的散列值是不變的。

2、通過 eq ()來檢測相等性

3、若a == b，則 hash(a) == hash(b)

往字典添加新鍵可能會改變已有鍵的順序

無論何時往字典里添加新鍵，python解釋器都可能作出字典擴容的決定。擴容導致的結果就是需要新建一個更大的散列表，並把字典里已有的元素添加到新表。這個過程可能會發生散列衝突，導致新散列表次序發生變化。

由此可知，不要對字典同時進行迭代和修改。如果你想掃描並修改一個字典，最好分成兩步來解決，首先對字典迭代，以得出需要添加對內容，把這些內容放到一個新字典里，迭代結束之後再對原字典進行更新。

字符問題

字節序列-解碼-unicode

字符串-解碼-unicode

b = str.encode(‘utf8’) 字符串轉化成字節碼 是編碼

b.decode(‘utf8’) 把字節碼還原成字符串 是解碼

一等函數

一等函數滿足以下條件：

1、在運行時創建

2、能賦值給變量或數據結構中的元素

3、能作為參數傳給函數

4、能作為函數的返回結果

高階函數

接受函數為參數，或者把函數作為結果返回的函數時高階函數。

匿名函數

通過對比可以看出，匿名函數lambda x: x * x實際上就是：

def f(x):

return x * x

關鍵字lambda表示匿名函數，冒號前面的x表示函數參數。

可調用類型

任何python對象都可以表現的像函數。只需要實現實例方法 call

實現 call 方法的類是創建函數類對象的簡便方式

函數內省

可以用dir(len)查看所有的函數屬性

sorted(set(dir(func))-set(dir(obj))) 計算差集 然後排序 得到類的實例沒有 而函數有的屬性列表

==運算符比較兩個對象的值（對象中保存的數據），而is是比較對象的標識。

通常，我們關注的是值，而不是標識，因此python中==出現的頻率比is高。

a==b是語法糖，等同於a. eq (b) 裝飾器也是語法糖

Python字典的底層實現

字典是一種可變、無序容器數據結構。元素以鍵值對存在，鍵值唯一。它的特點搜索速度很快：數據量增加10000倍，搜索時間增加不到2倍；當數據量很大的時候，字典的搜索速度要比列錶快成百上千倍。

在Python中，字典是通過散列表（哈希表）實現的。字典也叫哈希數組或關聯數組，所以其本質是數組（如下圖），每個 bucket 有兩部分：一個是鍵對象的引用，一個是值對象的引用。所有 bucket 結構和大小一致，我們可以通過偏移量來讀取指定 bucket。

定義一個字典 dic = {}，假設其哈希數組長度為8。

Python會根據哈希數組的擁擠程度對其擴容。“擴容”指的是:創造更大的數組，這時候會對已經存在的鍵值對重新進行哈希取余運算保存到其它位置；一般接近 2/3 時，數組就會擴容。擴容後，偏移量的數字個數增加，如數組長度擴容到16時，可以用最右邊4位數字作為偏移量。

計算鍵對象 name 的哈希值，然後比較哈希數組對應索引內的bucket是否為空，為空返回 None ，否則計算這個bucket的鍵對象的哈希值，然後與 name 哈希值比較，相等則返回 值對象 ，否則繼續左移計算哈希值。

注意：

1.鍵必須為可哈希的，如數字、元組、字符串；自定義對象需要滿足支持hash、支持通過 __eq__() 方法檢測相等性、若 a == b 為真，則 hash(a) == hash(b) 也為真。

2.字典的內存開銷很大，以空間換時間。

3.鍵查詢速度很快，列表查詢是按順序一個個遍歷，字典則是一步到位。

4.往字典裡面添加新鍵可能導致擴容，導致哈希數組中鍵的次序變化。因此，不要在遍歷字典的同時進行字典的修改。

Python數據結構-哈希表（Hash Table）

哈希表（Hash Table） ：通過鍵 key 和一個映射函數 Hash(key) 計算出對應的值 value，把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。

哈希函數（Hash Function） ：將哈希表中元素的關鍵鍵值映射為元素存儲位置的函數。

哈希衝突（Hash Collision） ：不同的關鍵字通過同一個哈希函數可能得到同一哈希地址。

哈希表的兩個核心問題是： 「哈希函數的構建」 和 「哈希衝突的解決方法」 。

常用的哈希函數方法有：直接定址法、除留餘數法、平方取中法、基數轉換法、數字分析法、摺疊法、隨機數法、乘積法、點積法等。

常用的哈希衝突的解決方法有兩種：開放地址法和鏈地址法。

給你一個整數數組 nums 和兩個整數 k 和 t 。請你判斷是否存在 兩個不同下標 i 和 j，使得 abs(nums[i] – nums[j]) = t ，同時又滿足 abs(i – j) = k 。

如果存在則返回 true，不存在返回 false。

給定兩個數組 nums1 和 nums2 ，返回 它們的交集 。輸出結果中的每個元素一定是 唯一 的。我們可以 不考慮輸出結果的順序 。

給你兩個整數數組 nums1 和 nums2 ，請你以數組形式返回兩數組的交集。返回結果中每個元素出現的次數，應與元素在兩個數組中都出現的次數一致（如果出現次數不一致，則考慮取較小值）。可以不考慮輸出結果的順序。

請你判斷一個 9 x 9 的數獨是否有效。只需要 根據以下規則 ，驗證已經填入的數字是否有效即可。

數字 1-9 在每一行只能出現一次。

數字 1-9 在每一列只能出現一次。

數字 1-9 在每一個以粗實線分隔的 3×3 宮內只能出現一次。（請參考示例圖）

力扣217

力扣389

力扣496

內容參考：

Python哈希函數什麼情況下拋出異常

拋出異常是停止運行這個函數中的代碼。

哈希算法將一個不定長的輸入，通過散列函數變換成一個定長的輸出，即散列值。是一種信息摘要算法。對象的hash值比原對象擁有更低的內存複雜度。

它不同於加密。哈希是將目標文本轉換成具有相同長度的，不可逆的雜湊字符串，而加密則是將文本轉換為具有相同長度的，可逆的密文。哈希算法是不可逆的，只能由輸入產生輸出，不能由輸出產生輸入。而加密則是可逆的。即可以從輸入產生輸出，也可以反過來從輸出推出輸入。