基于Python如何實(shí)現(xiàn)Hash算法

本篇內(nèi)容主要講解“基于Python如何實(shí)現(xiàn)Hash算法”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“基于Python如何實(shí)現(xiàn)Hash算法”吧!

1 前言

Simhash的算法簡(jiǎn)單的來(lái)說(shuō)就是，從海量文本中快速搜索和已知simhash相差小于k位的simhash集合，這里每個(gè)文本都可以用一個(gè)simhash值來(lái)代表，一個(gè)simhash有64bit，相似的文本，64bit也相似，論文中k的經(jīng)驗(yàn)值為3。該方法的缺點(diǎn)如優(yōu)點(diǎn)一樣明顯，主要有兩點(diǎn)，對(duì)于短文本，k值很敏感；另一個(gè)是由于算法是以空間換時(shí)間，系統(tǒng)內(nèi)存吃不消。

2 一般hash算法

最簡(jiǎn)單的hash算法是用取余的方式，根據(jù)hash地址存放數(shù)據(jù)，這需要提供鍵值對(duì)（Key-value）Key是地址，value是存放的數(shù)據(jù)

2.1 算法邏輯

• 輸入存放數(shù)據(jù)，并建立（Key-value）對(duì)象

• 通過(guò)取余數(shù)的方式 公式H = d H=d%nH=d H:哈希地址，d為數(shù)據(jù)，具有唯一性，n是樣本總數(shù)

• 把產(chǎn)生的哈希地址和對(duì)應(yīng)數(shù)據(jù)存儲(chǔ)到字典對(duì)象中

2.2 代碼實(shí)現(xiàn)

# 1.需要記錄的數(shù)據(jù)
records = [[1,50],[2,6],[3,47],[4,8],[5,9],[6,100]] # 數(shù)據(jù)鍵為日期，值為銷(xiāo)售數(shù)量
# 2.定義存放的地址和數(shù)據(jù)
Sadress1 = {'192.168.1.1':1}
Sadress2 = {'192.168.1.2':2}
Sadress3 = {'192.168.1.3':4}
Sadress4 = {'192.168.1.4':6}

# 數(shù)據(jù)長(zhǎng)度定義為
n = 20

# 判斷哈希值，分段為0-1-2-4-6
for one in records:
    if one[0] % n <= Sadress1['192.168.1.1']: 
        Sadress1[one[0]]=one[1]
    elif one[0] % n <= Sadress2['192.168.1.2']:
        Sadress2[one[0]] = one[1]
    elif one[0] % n <= Sadress3['192.168.1.3']:
        Sadress3[one[0]] = one[1]
    elif one[0] % n <= Sadress4['192.168.1.4']:
        Sadress4[one[0]] = one[1]

print(Sadress1)
print(Sadress2)
print(Sadress3)
print(Sadress4)

2.3 總結(jié)

• 這是最簡(jiǎn)單的Hash算法，還有MD5，SHAI，SHA2

• 哈希地址沖突，問(wèn)題主要考慮輸入的唯一性取值方法

• 在分布式計(jì)算中廣泛應(yīng)用

3 一致性hash算法

一致性Hash算法時(shí)為了防止單個(gè)節(jié)點(diǎn)宕機(jī)或者刪除、新增，不會(huì)導(dǎo)致數(shù)據(jù)存儲(chǔ)的混亂或者無(wú)法儲(chǔ)存。一致性服務(wù)器要求對(duì)服務(wù)器地址通過(guò)哈希算法也進(jìn)行映射方式確定輸出地址，再加上對(duì)數(shù)據(jù)的哈希處理，一直哈希要實(shí)現(xiàn)兩個(gè)算法過(guò)程。

3.1 算法邏輯

• 輸入數(shù)據(jù)，建立Key-value對(duì)象

• 利用Hash算法產(chǎn)生哈希地址，建立鍵值字典

• 輸入服務(wù)器地址，利用哈希算法產(chǎn)生哈希地址

• 數(shù)據(jù)通過(guò)地址和服務(wù)器地址，放到對(duì)應(yīng)的范圍內(nèi)

• 輸出

3.2 代碼實(shí)現(xiàn)

import hashlib # 導(dǎo)入帶shal（）哈希算法的函數(shù)庫(kù)
class CHash(object):
    def __init__(self,nodes=None,v_num=2):# nodes節(jié)點(diǎn)存放節(jié)點(diǎn)地址，V-num一個(gè)節(jié)點(diǎn)對(duì)應(yīng),# 默認(rèn)節(jié)點(diǎn)是為2
        self._v_num = v_num # 一個(gè)節(jié)點(diǎn)對(duì)應(yīng)存放節(jié)點(diǎn)地址
        self._vNode_IP = {} #　用于虛擬節(jié)點(diǎn)的hash值與node的對(duì)應(yīng)關(guān)系
        self._vNodeAdd = [] # 用于存放所有的虛擬節(jié)點(diǎn)的hash值，這里需要保持排序
        for node in nodes:
            self.addNode(node)
        print('\n虛擬節(jié)點(diǎn)哈希值升序排列：\n',self._vNodeAdd) # 對(duì)虛擬節(jié)點(diǎn)哈希地址進(jìn)行從小到大排序

    # 1 建立虛擬節(jié)點(diǎn)環(huán)，順序排列
    def addNode(self,node):
        for i in range(self._v_num):
            vNodeStr = '%s%s'%(node ,i) # 根據(jù)虛擬節(jié)點(diǎn)，為每個(gè)節(jié)點(diǎn)建立虛擬節(jié)點(diǎn)
            key = self._gen_key(vNodeStr) # 產(chǎn)生虛擬節(jié)點(diǎn)IP地址，服務(wù)器節(jié)點(diǎn)IP+i
            print('虛擬節(jié)點(diǎn)字符串',vNodeStr,'對(duì)應(yīng)哈希值',key)
            self._vNode_IP[key] = node # 虛擬節(jié)點(diǎn)哈希地址為鍵，節(jié)點(diǎn)為IP地址為值
            self._vNodeAdd.append(key) # 對(duì)應(yīng)虛擬節(jié)點(diǎn)哈希地址進(jìn)行獨(dú)立儲(chǔ)存
            self._vNodeAdd.sort()
    # 2 刪除退出節(jié)點(diǎn)地址及對(duì)應(yīng)的虛擬地址
    def Del_Node(self,node): # 刪除退出節(jié)點(diǎn)地址及對(duì)應(yīng)的虛擬地址
        for i in range(self._v_num):
            vNodeStr = '%s%s'%(node,i)
            key = self._gen_key(vNodeStr)  # 產(chǎn)生虛擬節(jié)點(diǎn)的哈希地址
            del self._vNode_IP[key] # 通過(guò)哈希地址刪除字典里面的虛擬節(jié)點(diǎn)信息
            self._vNodeAdd.remove(key) # 刪除虛擬節(jié)點(diǎn)的哈希地址
    # 3 返回?cái)?shù)據(jù)儲(chǔ)存對(duì)應(yīng)的服務(wù)器地址
    def dataNode(self,data):
        if self._vNodeAdd: # 虛擬節(jié)點(diǎn)的哈希地址列表不為空
            key = self._gen_key(data) # 產(chǎn)生業(yè)務(wù)數(shù)據(jù)對(duì)應(yīng)的哈希地址
            print(data,'哈希地址',key)
            for node_key in self._vNodeAdd: # 獲取虛擬節(jié)點(diǎn)的哈希地址
                if key <= node_key: # 業(yè)務(wù)數(shù)據(jù)的哈希地址<= 當(dāng)前虛擬節(jié)點(diǎn)的哈希地址
                    return self._vNode_IP[node_key] # 返回當(dāng)前虛擬節(jié)點(diǎn)哈希地址對(duì)應(yīng)節(jié)點(diǎn)IP
            return self._vNodeAdd[self._vNodeAdd[0]] # 如果業(yè)務(wù)數(shù)據(jù)的哈希值超過(guò)所有節(jié)點(diǎn)的地址，則歸入并返回第一個(gè)IP地址

        else:
            return None # 沒(méi)有節(jié)點(diǎn)

    # 4 通過(guò)shal()產(chǎn)生哈希值
    @staticmethod # 裝飾器
    def _gen_key(key_str):
        Hash_value = hashlib.sha1(key_str.encode('utf-8')).hexdigest()

        return Hash_value

# 測(cè)試
C_H = CHash(['192.168.1.1','192.168.1.2','192.168.1.3','192.168.1.4'])
data =['Mike','Margge','Maria']
print('\n正常情況下，存儲(chǔ)數(shù)據(jù)時(shí)，歸入的節(jié)點(diǎn)地址：')
print(data[0]+'存入的節(jié)點(diǎn)IP地址：',C_H.dataNode(data[0]))
print(data[1]+'存入的節(jié)點(diǎn)IP地址：',C_H.dataNode(data[1]))
print(data[2]+'存入的節(jié)點(diǎn)IP地址：',C_H.dataNode(data[2]))
# 192.168.2.1刪除節(jié)點(diǎn)
print('\n192.168.1.2節(jié)點(diǎn)脫離分布式系統(tǒng)的情況：')
C_H.Del_Node('192.168.1.2') # 刪除節(jié)點(diǎn)
print(data[0]+'存入的節(jié)點(diǎn)IP地址：',C_H.dataNode(data[0]))
print(data[1]+'存入的節(jié)點(diǎn)IP地址：',C_H.dataNode(data[1]))
print(data[2]+'存入的節(jié)點(diǎn)IP地址：',C_H.dataNode(data[2]))

虛擬節(jié)點(diǎn)字符串 192.168.1.10 對(duì)應(yīng)哈希值 f53e4ef74ec8f55440f9caf382c5f63c4a39b4bc
虛擬節(jié)點(diǎn)字符串 192.168.1.11 對(duì)應(yīng)哈希值 239b32be446b1288655b570c23ccb51633c03927
虛擬節(jié)點(diǎn)字符串 192.168.1.20 對(duì)應(yīng)哈希值 c385b891af246719e1a60c715be2f375aeab0b5b
虛擬節(jié)點(diǎn)字符串 192.168.1.21 對(duì)應(yīng)哈希值 0d12ca599dc0316beec6436bb3beb04e84fbe3e2
虛擬節(jié)點(diǎn)字符串 192.168.1.30 對(duì)應(yīng)哈希值 265180387f1642217973f8cfda2ca6cc92d48e60
虛擬節(jié)點(diǎn)字符串 192.168.1.31 對(duì)應(yīng)哈希值 d6dacbe137bec9a047737207a3a82036f8454362
虛擬節(jié)點(diǎn)字符串 192.168.1.40 對(duì)應(yīng)哈希值 7497a9439524d6f044fc22a8723039e0c42bbac8
虛擬節(jié)點(diǎn)字符串 192.168.1.41 對(duì)應(yīng)哈希值 89c78508a642956363ed40326fce4346d7889f88

虛擬節(jié)點(diǎn)哈希值升序排列：

 ['0d12ca599dc0316beec6436bb3beb04e84fbe3e2', '239b32be446b1288655b570c23ccb51633c03927', '265180387f1642217973f8cfda2ca6cc92d48e60', '7497a9439524d6f044fc22a8723039e0c42bbac8', '89c78508a642956363ed40326fce4346d7889f88', 'c385b891af246719e1a60c715be2f375aeab0b5b', 'd6dacbe137bec9a047737207a3a82036f8454362', 'f53e4ef74ec8f55440f9caf382c5f63c4a39b4bc']

正常情況下，存儲(chǔ)數(shù)據(jù)時(shí)，歸入的節(jié)點(diǎn)地址：

Mike 哈希地址 d6ac022931a66a2bcc244db91818ebec76ce5e18
Mike存入的節(jié)點(diǎn)IP地址： 192.168.1.3
Margge 哈希地址 ae5e1fda577bff360ed5da0b2804a1ff0b2a1675
Margge存入的節(jié)點(diǎn)IP地址： 192.168.1.2
Maria 哈希地址 3e182b1ea9376483a38614d916a0b666ef531b6d
Maria存入的節(jié)點(diǎn)IP地址： 192.168.1.4

192.168.1.2節(jié)點(diǎn)脫離分布式系統(tǒng)的情況：

Mike 哈希地址 d6ac022931a66a2bcc244db91818ebec76ce5e18
Mike存入的節(jié)點(diǎn)IP地址： 192.168.1.3
Margge 哈希地址 ae5e1fda577bff360ed5da0b2804a1ff0b2a1675
Margge存入的節(jié)點(diǎn)IP地址： 192.168.1.3
Maria 哈希地址 3e182b1ea9376483a38614d916a0b666ef531b6d
Maria存入的節(jié)點(diǎn)IP地址： 192.168.1.4

到此，相信大家對(duì)“基于Python如何實(shí)現(xiàn)Hash算法”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！