基于Python实现Hash算法

目录
  • 1 前言
  • 2 一般hash算法
    • 2.1 算法逻辑
    • 2.2 代码实现
    • 2.3 总结
  • 3 一致性hash算法
    • 3.1 算法逻辑
    • 3.2 代码实现
    • 3.3 总结

1 前言

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

2 一般hash算法

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

2.1 算法逻辑

  • 输入存放数据,并建立(Key-value)对象
  • 通过取余数的方式 公式H = d H=d%nH=d H:哈希地址,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

3.3 总结

  • 应用广泛,很好的解决了服务器宕机,节点删除等问题
  • IP地址指向不同的服务器访问地址,为不同的服务器上的数据库存取提供了便利

到此这篇关于基于Python实现Hash算法的文章就介绍到这了,更多相关Python实现Hash算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • python 密码学示例——理解哈希(Hash)算法

    Hash 是密码学安全性的基石,它引入了单向函数(one-way function)和指纹(fingerprint)的概念.即: 对于任意输入,都可以产生相同的.唯一的输出值 输出值中不包含输入值的任何线索 一.保密性(confidentiality)与完整性(integrity) 简单来说,信息的保密性确保除授权人员以外的任何人都无法读取该消息,信息的完整性则确保除授权人员以外的任何人都无法修改该消息. 很多时候一段加密的消息无法被他人读取和理解(保密性),并不意味着该密文不会在传播过程中被截

  • Python中使用hashlib模块处理算法的教程

    Python的hashlib提供了常见的摘要算法,如MD5,SHA1等等. 什么是摘要算法呢?摘要算法又称哈希算法.散列算法.它通过一个函数,把任意长度的数据转换为一个长度固定的数据串(通常用16进制的字符串表示). 举个例子,你写了一篇文章,内容是一个字符串'how to use python hashlib - by Michael',并附上这篇文章的摘要是'2d73d4f15c0db7f5ecb321b6a65e5d6d'.如果有人篡改了你的文章,并发表为'how to use pytho

  • 盘点Python加密解密模块hashlib的7种加密算法(推荐)

    前言 在程序中我们经常可以看到有很多的加密算法,比如说MD5 sha1等,今天我们就来了解下这下加密算法的吧,在了解之前我们需要知道一个模块嘛就是hashlib,他就是目前Python一个提供字符加密的模块,它加密的字符类型为二进制编码,所以直接加密字符串会报错. import hashlib string='任性的90后boy' #使用encode进行转换 sha1 = hashlib.sha1() sha1.update(string.encode('utf-8')) res = sha1.

  • Python3 hashlib密码散列算法原理详解

    1.hashlib密码散列 hashlib模块定义了一个API来访问不同的密码散列算法.要使用一个特定的散列算法,可以用适当的构造器函数或new()来创建一个散列对象.不论使用哪个具体的算法,这些对象都使用相同的API. 1.1 散列算法 由于hashlib有OpenSSL提供"底层支持",所以OpenSSL库提供的所有算法都可用,包括: md5 sha1 sha224 sha256 sha384 sha512 有些算法在所有平台上都可用,而有些则依赖于底层库.这两种算法分别由algo

  • python实现Simhash算法

    1.simhash步骤 simhash包含分词.hash.加权.合并.降维五大步骤 simhash代码如下: import jieba import jieba.analyse import numpy as np class SimHash(object):     def simHash(self, content):         seg = jieba.cut(content)         # jieba.analyse.set_stop_words('stopword.txt')

  • Python hashlib常见摘要算法详解

    这篇文章主要介绍了Python hashlib常见摘要算法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Python的hashlib提供了常见的摘要算法,如MD5,SHA1等等 计算出一个字符串的MD5值: import hashlib md5 = hashlib.md5() md5.update('how to use md5 in python hashlib?'.encode("utf8")) #需要指定转码 否则报错 u

  • python实现simhash算法实例

    Simhash的算法简单的来说就是,从海量文本中快速搜索和已知simhash相差小于k位的simhash集合,这里每个文本都可以用一个simhash值来代表,一个simhash有64bit,相似的文本,64bit也相似,论文中k的经验值为3.该方法的缺点如优点一样明显,主要有两点,对于短文本,k值很敏感:另一个是由于算法是以空间换时间,系统内存吃不消. 复制代码 代码如下: #!/usr/bin/python# coding=utf-8class simhash: #构造函数    def __

  • 基于Python实现Hash算法

    目录 1 前言 2 一般hash算法 2.1 算法逻辑 2.2 代码实现 2.3 总结 3 一致性hash算法 3.1 算法逻辑 3.2 代码实现 3.3 总结 1 前言 Simhash的算法简单的来说就是,从海量文本中快速搜索和已知simhash相差小于k位的simhash集合,这里每个文本都可以用一个simhash值来代表,一个simhash有64bit,相似的文本,64bit也相似,论文中k的经验值为3.该方法的缺点如优点一样明显,主要有两点,对于短文本,k值很敏感:另一个是由于算法是以空

  • 基于python实现雪花算法过程详解

    这篇文章主要介绍了基于python实现雪花算法过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Snowflake是Twitter提出来的一个算法,其目的是生成一个64bit的整数: 1bit:一般是符号位,不做处理 41bit:用来记录时间戳,这里可以记录69年,如果设置好起始时间比如今年是2018年,那么可以用到2089年,到时候怎么办?要是这个系统能用69年,我相信这个系统早都重构了好多次了. 10bit:10bit用来记录机器ID

  • 基于Python实现DIT-FFT算法

    目录 自己写函数实现FFT 使用python的第三方库进行FFT 自己写函数实现FFT 使用递归方法 from math import log, ceil, cos, sin, pi import matplotlib.pyplot as plt import numpy as np # 这两行代码解决 plt 中文显示的问题 plt.rcParams['font.sans-serif'] = ['SimHei'] plt.rcParams['axes.unicode_minus'] = Fal

  • 基于python的Paxos算法实现

    理解一个算法最快,最深刻的做法,我觉着可能是自己手动实现,虽然项目中不用自己实现,有已经封装好的算法库,供我们调用,我觉着还是有必要自己亲自实践一下. 这里首先说明一下,python这种动态语言,对不熟悉的人可能看着比较别扭,不像java那样参数类型是固定的,所以看着会有些蛋疼.这里环境用的是python2.7. class Message: # command MSG_ACCEPTOR_AGREE = 0 # 追随者约定 MSG_ACCEPTOR_ACCEPT = 1 # 追随者接受 MSG_

  • 基于Python实现迪杰斯特拉和弗洛伊德算法

    图搜索之基于Python的迪杰斯特拉算法和弗洛伊德算法,供大家参考,具体内容如下 Djstela算法 #encoding=UTF-8 MAX=9 ''' Created on 2016年9月28日 @author: sx ''' b=999 G=[[0,1,5,b,b,b,b,b,b],\ [1,0,3,7,5,b,b,b,b],\ [5,3,0,b,1,7,b,b,b],\ [b,7,b,0,2,b,3,b,b],\ [b,5,1,2,0,3,6,9,b],\ [b,b,7,b,3,0,b,5

  • 基于 Python 实践感知器分类算法

    Perceptron是用于二进制分类任务的线性机器学习算法.它可以被认为是人工神经网络的第一种和最简单的类型之一.绝对不是"深度"学习,而是重要的组成部分.与逻辑回归相似,它可以快速学习两类分类任务在特征空间中的线性分离,尽管与逻辑回归不同,它使用随机梯度下降优化算法学习并且不预测校准概率. 在本教程中,您将发现Perceptron分类机器学习算法.完成本教程后,您将知道: Perceptron分类器是一种线性算法,可以应用于二进制分类任务. 如何使用带有Scikit-Learn的Pe

  • 基于Python代码实现Apriori 关联规则算法

    目录 一.关联规则概述 二.应用场景举例 1.股票涨跌预测 2.视频.音乐.图书等推荐 3.打车路线预测(考虑时空) 4.风控策略自动化挖掘 三.3个最重要的概念 1.支持度 2.置信度 3.提升度 4. 频繁项集 四.Python算法介绍 五.挖掘实例 一.关联规则概述 1993年,Agrawal等人在首先提出关联规则概念,迄今已经差不多30年了,在各种算法层出不穷的今天,这算得上是老古董了,比很多人的年纪还大,往往是数据挖掘的入门算法,但深入研究的不多,尤其在风控领域,有着极其重要的应用潜力

  • python基于双向链表实现LFU算法

    本文实例为大家分享了python实现LFU算法的具体代码,供大家参考,具体内容如下 在第一节中实现了双向链表DoubleLinkedList类,上一节中基于双向链表实现了LRU算法,本节课我们继续基于双向链表实现LFU(Least frequently used 最不经常使用)算法. 一.重写Node节点类 构建LFUNode类 继承自第一节中的Node类,添加freq属性用来表示节点使用频率 class LFUNode(Node):     def __init__(self, key, va

  • 基于一致性hash算法(consistent hashing)的使用详解

    1 基本场景 比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache : hash(object)%N 一切都运行正常,再考虑如下的两种情况: 1 一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m 从 c

  • 基于一致性hash算法 C++语言的实现详解

    一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择. 首先来谈一下一致性hash算法中用于存储结点的数据结构.通过了解一致性hash的原理,我们知道结点可以想象为是存储在一个环形的数据结构上(如下图),结点A.B.C.D按hash值在环形分布上是有序的,也就是说结点可以按hash值存储在一个有序的队列里.如下图所示,当一个hash值为-2^20的请求点P查找路由结点时,一致性hash算法会按hash值的顺时针方向路由到第一个结点

随机推荐