基于Python实现Hash算法

来源：脚本之家时间：2022-03-18 18:58:23

1 前言

Simhash的算法简单的来说就是，从海量文本中快速搜索和已知simhash相差小于k位的simhash集合，这里每个文本都可以用一个simhash值来代表，一个simhash有64bit，相似的文本，64bit也相似，论文中k的经验值为3。该方法的缺点如优点一样明显，主要有两点，对于短文本，k值很敏感；另一个是由于算法是以空间换时间，系统内存吃不消。

2 一般hash算法

最简单的hash算法是用取余的方式，根据hash地址存放数据，这需要提供键值对（Key-value）Key是地址，value是存放的数据

2.1 算法逻辑

输入存放数据，并建立（Key-value）对象通过取余数的方式公式:哈希地址，d为数据，具有唯一性，n是样本总数把产生的哈希地址和对应数据存储到字典对象中

2.2 代码实现

# 1.需要记录的数据
records = [[1,50],[2,6],[3,47],[4,8],[5,9],[6,100]] # 数据键为日期，值为销售数量
# 2.定义存放的地址和数据
Sadress1 = {"192.168.1.1":1}
Sadress2 = {"192.168.1.2":2}
Sadress3 = {"192.168.1.3":4}
Sadress4 = {"192.168.1.4":6}

# 数据长度定义为
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 总结

这是最简单的Hash算法，还有MD5，SHAI，SHA2哈希地址冲突，问题主要考虑输入的唯一性取值方法在分布式计算中广泛应用

3 一致性hash算法

一致性Hash算法时为了防止单个节点宕机或者删除、新增，不会导致数据存储的混乱或者无法储存。一致性服务器要求对服务器地址通过哈希算法也进行映射方式确定输出地址，再加上对数据的哈希处理，一直哈希要实现两个算法过程。

3.1 算法逻辑

输入数据，建立Key-value对象利用Hash算法产生哈希地址，建立键值字典输入服务器地址，利用哈希算法产生哈希地址数据通过地址和服务器地址，放到对应的范围内输出

3.2 代码实现

import hashlib # 导入带shal（）哈希算法的函数库
class CHash(object):
    def __init__(self,nodes=None,v_num=2):# nodes节点存放节点地址，V-num一个节点对应,# 默认节点是为2
        self._v_num = v_num # 一个节点对应存放节点地址
        self._vNode_IP = {} #　用于虚拟节点的hash值与node的对应关系
        self._vNodeAdd = [] # 用于存放所有的虚拟节点的hash值，这里需要保持排序
        for node in nodes:
            self.addNode(node)
        print("\n虚拟节点哈希值升序排列：\n",self._vNodeAdd) # 对虚拟节点哈希地址进行从小到大排序

    # 1 建立虚拟节点环，顺序排列
    def addNode(self,node):
        for i in range(self._v_num):
            vNodeStr = "%s%s"%(node ,i) # 根据虚拟节点，为每个节点建立虚拟节点
            key = self._gen_key(vNodeStr) # 产生虚拟节点IP地址，服务器节点IP+i
            print("虚拟节点字符串",vNodeStr,"对应哈希值",key)
            self._vNode_IP[key] = node # 虚拟节点哈希地址为键，节点为IP地址为值
            self._vNodeAdd.append(key) # 对应虚拟节点哈希地址进行独立储存
            self._vNodeAdd.sort()
    # 2 删除退出节点地址及对应的虚拟地址
    def Del_Node(self,node): # 删除退出节点地址及对应的虚拟地址
        for i in range(self._v_num):
            vNodeStr = "%s%s"%(node,i)
            key = self._gen_key(vNodeStr)  # 产生虚拟节点的哈希地址
            del self._vNode_IP[key] # 通过哈希地址删除字典里面的虚拟节点信息
            self._vNodeAdd.remove(key) # 删除虚拟节点的哈希地址
    # 3 返回数据储存对应的服务器地址
    def dataNode(self,data):
        if self._vNodeAdd: # 虚拟节点的哈希地址列表不为空
            key = self._gen_key(data) # 产生业务数据对应的哈希地址
            print(data,"哈希地址",key)
            for node_key in self._vNodeAdd: # 获取虚拟节点的哈希地址
                if key <= node_key: # 业务数据的哈希地址<= 当前虚拟节点的哈希地址
                    return self._vNode_IP[node_key] # 返回当前虚拟节点哈希地址对应节点IP
            return self._vNodeAdd[self._vNodeAdd[0]] # 如果业务数据的哈希值超过所有节点的地址，则归入并返回第一个IP地址

        else:
            return None # 没有节点

    # 4 通过shal()产生哈希值
    @staticmethod # 装饰器
    def _gen_key(key_str):
        Hash_value = hashlib.sha1(key_str.encode("utf-8")).hexdigest()

        return Hash_value

# 测试
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正常情况下，存储数据时，归入的节点地址：")
print(data[0]+"存入的节点IP地址：",C_H.dataNode(data[0]))
print(data[1]+"存入的节点IP地址：",C_H.dataNode(data[1]))
print(data[2]+"存入的节点IP地址：",C_H.dataNode(data[2]))
# 192.168.2.1删除节点
print("\n192.168.1.2节点脱离分布式系统的情况：")
C_H.Del_Node("192.168.1.2") # 删除节点
print(data[0]+"存入的节点IP地址：",C_H.dataNode(data[0]))
print(data[1]+"存入的节点IP地址：",C_H.dataNode(data[1]))
print(data[2]+"存入的节点IP地址：",C_H.dataNode(data[2]))

虚拟节点字符串 192.168.1.10 对应哈希值 f53e4ef74ec8f55440f9caf382c5f63c4a39b4bc
虚拟节点字符串 192.168.1.11 对应哈希值 239b32be446b1288655b570c23ccb51633c03927
虚拟节点字符串 192.168.1.20 对应哈希值 c385b891af246719e1a60c715be2f375aeab0b5b
虚拟节点字符串 192.168.1.21 对应哈希值 0d12ca599dc0316beec6436bb3beb04e84fbe3e2
虚拟节点字符串 192.168.1.30 对应哈希值 265180387f1642217973f8cfda2ca6cc92d48e60
虚拟节点字符串 192.168.1.31 对应哈希值 d6dacbe137bec9a047737207a3a82036f8454362
虚拟节点字符串 192.168.1.40 对应哈希值 7497a9439524d6f044fc22a8723039e0c42bbac8
虚拟节点字符串 192.168.1.41 对应哈希值 89c78508a642956363ed40326fce4346d7889f88

虚拟节点哈希值升序排列：

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

正常情况下，存储数据时，归入的节点地址：

Mike 哈希地址 d6ac022931a66a2bcc244db91818ebec76ce5e18
Mike存入的节点IP地址： 192.168.1.3
Margge 哈希地址 ae5e1fda577bff360ed5da0b2804a1ff0b2a1675
Margge存入的节点IP地址： 192.168.1.2
Maria 哈希地址 3e182b1ea9376483a38614d916a0b666ef531b6d
Maria存入的节点IP地址： 192.168.1.4

192.168.1.2节点脱离分布式系统的情况：

Mike 哈希地址 d6ac022931a66a2bcc244db91818ebec76ce5e18
Mike存入的节点IP地址： 192.168.1.3
Margge 哈希地址 ae5e1fda577bff360ed5da0b2804a1ff0b2a1675
Margge存入的节点IP地址： 192.168.1.3
Maria 哈希地址 3e182b1ea9376483a38614d916a0b666ef531b6d
Maria存入的节点IP地址： 192.168.1.4