哈希算法又稱散列函數算法，是一種查找算法。就是把一些復雜的數據通過某種映射關系。映射成更容易查找的方式，但這種映射關系可能會發生多個關鍵字映射到同一地址的現象，我們稱之為沖突。在這種情況下，我們需要對關鍵字進行二次或更多次處理。出這種情況外，哈希算法可以實現在常數時間內存儲和查找這些關鍵字。

一、常見數據查找算法簡介

常見的數據查找算法：

順序查找：是最簡單的查找方法。需要對數據集中的逐個匹配。所以效率相對較低，不太適合大量數據的查找問題。

二分法查找：效率很高，但是要求數據必須有序。面對數據排序通常需要更多的時間。

深度優先和廣度優先算法：對于大量的數據查找問題，效率并不高。這個我們后面專門講解。

阿希查找算法：查找速度快，查詢插入，刪除操作簡單等原因獲得廣泛的應用。

二、什么是哈希

哈希查找的原理：根據數量預先設一個長度為M的數組。使用一個哈希函數F并以數據的關鍵字作為自變量得到唯一的返回值，返回值的范圍是0~M-1。這樣就可以利用哈希函數F將數據元素映射到一個數組的某一位下標，并把數據存放在對應位置，查找時利用哈希函數F計算，該數據應存放在哪里，在相應的存儲位置取出查找的數據。

這里就有一個問題：

關鍵字的取值在一個很大的范圍，數據在通過哈希函數進行映射時。很難找到一個哈希函數，使得這些關鍵字都能映射到唯一的值。就會出現多個關鍵字映射到同一個值的現象，這種現象我們稱之為沖突。

哈西算法沖突的解決方案有很多：鏈地址法，二次再散列法。線性探測再散列建立一個公共溢出區

注意：鏈地址法本質是數組+鏈表的數據結構

鏈地址法存儲數據過程：

首先建立一個數組哈希存儲所有鏈表的頭指針。由數組的關鍵字key通過對應的哈希函數計算出哈希地址。找到相應的桶號之后，建立新的節點存儲該數據。并把節點放到桶內的鏈表的最后面或者最前面。

鏈地址法查找數據：由數據關鍵字通過哈希。函數計算關鍵字對應的哈希地址之后順序比較同類不節點。是否與所查到的關鍵字一樣，直到找到數據為止，如果全部節點都不和關鍵字一樣，則書名哈系表里沒有該數據。解決了哈希函數的沖突。

用鏈地址法構造的散列表插入和刪除節點操作易于實現，所以構造鏈表的時間開銷很低。但是指針需要開辟額外的地址空間，當數據量很大時會擴大哈希表規模，內存空間要求較大。

三、實例：兩個數字的和

1.問題描述

要求在給定的一些數字中找出兩個數，使得它們的和為嗯，前提是這些數據中保證有答案，并且只有一個答案。例如給3、4、5、7、10。從中選出兩個數字使它們的和為11，可以選擇4和7。

2.雙指針辦法解決

def twosum(nums,target):

res = [] #存放結果編號

newnumber = nums [:] #將數據深拷貝一份

newnumber.sort() #對拷貝結果排序

left = 0 #定義左指針

right = len(newnumber) -1 # 定義右指針

while left < right:

if newnumber[left] + newnumber[right] ==target: #在原始數組中第一個元組尋找原始下標

for i in range(0,len(nums)):

if nums[i] == newnumber[left]:

res.append(i) #將下標結果接入集

break

for i in range(len(nums) - 1 , -1 , -1):#向回找，尋找第二個元組

if nums[i] == newnumber[right]:

res.append(i)

break

res.sort()

break

elif newnumber[left] +newnumber[right] < target:

left = left +1

else :

right = right -1

return (res[0] + 1 ,res[1] + 1 )

s =twosum([3,4,5,7,10],11)

print('下標是：',s)

雙指針解決方案：

第一步：對數據進行排序

第二步：移動指針尋找答案

第三步：發現答案去原始數據中查找這兩個元素的位置

顯然第一步和第三步很浪費時間，我們使用哈希算法，規避排序問題，直接查找數據和下標的對應關系。

3.哈希算法求解

def twosum(nums,target):

'''

這個函數只能解決兩個數字和，且答案有且僅有一個的情況

'''

dict = {}

for i in range(len(nums)):

m = nums[i]

if target - m in dict:#判定target - m 是否在字典中

return (dict[target-m]+1,i +1) #存在返回連個數的下標

dict[m] = i #若不存在則記錄鍵值對的值

s =twosum([3,4,5,7,10],11)

print('下標是：',s)

字典使用dict[key] = value 來記錄鍵值對的關系

四、總結

使用哈希算法解決查找問題，不僅效率高，而且代碼更少更容易理解，我們使用哈希算法解決查找問題將事半功倍，

這個示例問題是一個經典問題，還有后續一些問題，三個數、四個數求和問題。

總結

以上是生活随笔為你收集整理的python按hash分组_Python算法系列-哈希算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。