精华内容
下载资源
问答
  • 数据结构之哈希算法

    千次阅读 2019-01-22 13:53:11
    此文是数据结构和算法美学习笔记 哈希算法就是将任意长度的二进制值映射为固定长度的二进制串,这个映射的规则就是哈希算法,原始数据映射之后得到的二进制哈希值。 一般哈希算法的要求: 不能通过哈希值反向推导...

    此文是数据结构和算法之美学习笔记

    哈希算法就是将任意长度的二进制值映射为固定长度的二进制串,这个映射的规则就是哈希算法,原始数据映射之后得到的二进制哈希值。

    一般哈希算法的要求:

    • 不能通过哈希值反向推导出原始数据(哈希算法也叫单向哈希算法)
    • 对输入的数据非常敏感,哪怕原始数据只是修改了一个bit,最后得到的哈希值也大不形同
    • 对不同的原始数据,哈希值相同的概率要非常小,散列冲突的概率要很小。
    • 哈希算法的执行效率要尽量的高效,即使较长的文本也能很快的计算出哈希值

    哈希算法的应用非常多最常见的有安全加密,唯一标识,数据校验,散列函数,负载均衡,数据分片,分布式存储。

    安全加密

    常用于加密的哈希算法是
    MD5(Message-Digest-Algorihm 消息摘要算法)
    SHA(Secure Hash Algorihm 安全散列算法)
    DES(Data Encryption Standard 数据加密标准)
    AES(Advanced Encryption Standard 高级加密标准)

    为什么哈希算法无法做到零冲突?

    有一个数学理论:鸽巢原理(也叫抽屉原理)就是说如果有10个鸽巢,有11个格子,那么肯定有一个鸽巢中有两个鸽子。

    哈希算法产生的哈希值的长度也是有限的,比如MD5的哈希值固定是128位的二进制串,最多能表示2128个数据。而我们需要表示的哈希数是无穷的,当数据大于2128的时候,就必然会出现哈希值相同的情况。

    不过由于2128这个数组已经很大了,出现散列冲突的概率要小于1/2128,相对来说很难破解。

    没有绝对的安全加密,越复杂越难破解的加密算法,需要的计算时间也越长,就想SHA-256比SHA-1要更加复杂也就更安全,相应的计算时间就会更长。

    唯一标识

    比如在海量的图库中怎么搜索一张图片是否存在?

    (1)使用图片名字肯定不行,因为可能有的图片名字不一样但是都是一样的图片
    (2)对比图片的二进制码,这种办法可行,但是比较笨,因为图片很多都很大几MB都是常事,转化成二进制后会很大,对比起来也非常耗时
    (3)可以给每一张图片取一个唯一标识,比如可以从二进制码的开头取100字节,中间取100字节,结尾再取100字节,把这300字节放到一块通过哈希算法比如MD5得到一个哈希字符串,用这个作为图片的唯一标识来判断库中是否有该图片

    当我们向库中插入一个图片的时候,先去散列表中查找唯一标识,如果不存在就说明这个图片不在图库中,如果存在就拿出这个图片和将要插入的图片做全量对比,看是否完全一样。如果一样说明已经存在,如果不一样说明两张图片虽然唯一标识一样但不是相同的图片。

    数据校验

    比如BT下载,一个电影可能会被分割成很多块(比如100块)分别下载,等所有文件都下载完成之后在组装成一个完整的电影文件。

    由于网络传输是不安全的,下载的文件快可能会被宿主几区恶意修改或者下载过程出现了错误导致下载的文件是不完整的。如果下载完不能检测是否出错,就会导致最后合并完的电影无法观看甚至中毒。

    一种校验的思路就是,把这100个快分别取哈希值并且保存在种子文件中,由于哈希算法对原始数据非常敏感,只要文件中有一点点改变最后的哈希值就完全不同,当文件块下载完成后,我们可以通过同样的哈希算法对下载好的文件快一一求哈希值跟种子文件中的哈希值对比。如果不一样说明文件快不完整或者被篡改了,需要重新下载。

    散列函数

    散列表中的散列函数也需要哈希算法,不过相对于其他的应用,它对哈希算法的要求不高,即使出现散列冲突,也可以通过开放寻址法和链表法来解决

    散列函数对哈希算法的要求主要散列后的值能否平均分布,散列函数是否执行很快。

    如何防止数据库中信息被脱库

    可以通过哈希算法,对用户密码进行加密之后在存储不过最好选择相对安全的加密算法比如SHA(MD5据说被破解了)
    不过如果用户的密码设置的很简单比如000000,,13456等简单的数组,黑客可以通过字典攻击很容易的猜中
    针对字典攻击可以引入一个盐(salt)跟用户的密码组合在一起增加其复杂度然后在通过哈希算法加密。比如原始密码是123456,可以在其头部或者尾部加上个字符串bxt变成bxt123456或者123456bxt也可以在中间加。

    区块链现很火,其实其底层也是通过哈希算法

    区块链是一块块的区块组成,每个区块分成区块头和区块体,区块头保存着自己区块体和上一个区块头的哈希值。

    因为这种链式关系和哈希值的唯一性,只要区块链上的任意一个区块被修改过,后面的所有的区块保存的哈希值就不对了。

    区块链使用的是SHA256这种哈希算法,计算哈希值是很耗时的,如果要篡改一个区块,就必须重新计算该区块后面的所有的区块的哈希值,短时间内几乎做不到。

    负载均衡

    负载均衡算法有很多,比如轮训,随机,加权轮询等等。怎么才能实现一个会话粘滞(同一个客户端上,在一次会话中的所有请求都路由到同一个服务器上)的负载均衡呢

    最直接的做法就是维护一张映射表,内容是客户端的IP地址或者会话ID,于服务器编号的映射关系。客户端发出的每次请求都要先在映射表中查找应该路由到哪台服务器,然后在请求对应的服务器。

    不过当客户端很多的时候,映射表会很大,浪费空间。客户端的上线下线服务器的扩容都会导致映射失效,维护成本很大。

    我们可以通过哈希算法,把客户端IP地址或者会话ID计算哈希值,把得到的哈希值跟服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器的编号。

    数据分片

    1、如何统计某个关键词出现的次数

    如果我们有1T的数据,里面记录了用户搜索的关键词,怎么快速的统计出每个关键词被搜索的次数。

    先对数据进行分片,然后采用多台机器处理,提高处理速度。

    为了提高处理速度,我们使用n台机器并行处理,从搜索日志中一次读取出每个搜索关键词,通过哈希函数计算哈希值,然后n取模,得到的值就是应该分配到的机器编号

    这样哈希值相同的关键字就会被分配到同一台机器上,每个机器分别计算出关键词的次数,最后合并起来就是最后结果。

    2、如何快速判断图片是否存在图库中

    假如又一亿张图片,一台机器是无法装下的,这时候就可以给数据分片,然后多机处理。准备n台机器,每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片,计算唯一标识,然后与机器个数,取模,得到的值就是对应分配的机器标号,然后将这个图片唯一标识和图片路径发往对应的机器构建散列表。

    查找的时候,通过同样的哈希算法计算图片的唯一标识,然后机器个数n取模,得到的值就是对应机器的编号,然后去该机器中寻找。

    分布式存储

    如今的互联网的数据都是海量的,只能分布式的存储在不同的机器上,怎么决定放在哪个机器上呢,跟数据分片一样,通过哈希算法对数据取哈希值,然后对机器取模,值就是对应机器的编号。

    问题:当数据增多,原来的机器无法存储的时候,就需要加机器了。但是这个时候不仅仅是加机器这么简单。

    因为比如原来有10台机器,原来的值是通过10来取模的,当加了一台机器之后,就是按11取模了,最后分配到的机器是不一样的。因此所有的数据都要从新计算哈希值,然后从新搬移到正确的机器上,相当于缓存中的数据全部失效,假如以前是直接请求缓存,现在就是直接去请求数据库,数据库就会被压垮、

    怎么解决这个问题呢,可以使用一致性哈希算法

    什么是一致性哈希算法,假如我们有k台机器数据的哈希值的范围是[0,max],我们把整个范围划分成m个小区间(m远大于k),每个机器负责m/k个小区间。当有新的机器加入的时候,就把某几个小区间的数据从原来的机器中搬移到新的机器中,这样既不用重新哈希搬移数据,也保持了哥哥机器上数据的均衡。

    注意取模的时候不是根据机台的个数k而是跟m取。当然取到的数也许不是机台的编号,这时候就按照顺时针来寻找,把数据放到第一个找到的机器上。

    当然这样做也有可能某台机器上存储的东西太多,不够均匀,怎么办呢,可以引入虚拟结点的概念,每台机器分成m/k份,这样相当于这m个结点上都有一台小机器了,取模之后就可以直接放到这些小机器上了。这样就解决了不均匀的问题了。

    展开全文
  • 算法与数据结构之美—哈希算法哈希算法应用安全加密唯一标识数据校验散列函数负载均衡数据分片1、如何统计“搜素关键词”的出现次数2、如何快速判断图片是否再图库中分布式存储一致性哈希算法 哈希算法 哈希算法地...

    哈希算法

    哈希算法地原理就是将任意长度地二进制值串映射为固定长度地二进制值串,映射规则就是哈希算法;

    哈希算法需要满足地要求:

    • 从哈希值不能反向推导出原始数据;
    • 对于输入数据敏感,哪怕只改变了一个bit,最后得到的哈希值也不大相同;
    • 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
    • 哈希算法的执行效率要高效,针对于长文本,也能进行快速哈希计算;

    应用

    安全加密

    常用于加密的哈希算法是MD5(MD5:Message-Digest Algorithm,消息摘要算法)和SHA(Secure Hash Algorithm,安全散列算法),除此之外还有很多其它加密算法,比如DESData Encryption Standard,数据加密标准)、AESAdvanced Encryption Standard,高级加密标准;

    对于安全加密来说,很难根据哈希值反向推导出原始数据和散列冲突的概率要很小,这两点特性很重要;

    像MD5,有2^128个不同的哈希值,所以散列冲突的概率是很小的;

    唯一标识

    在海量的图片中,搜索一张图片是否存在,不可能仅仅只靠图片的名称等信息来比对;那就可以通过哈希算法给每张图片

    取一个唯一标识,例如:对于一张图片,可以从图片的二进制码串分别在开头 中间 结尾各取100个字节,将300个字节放在一起,采用哈希算法生成一个哈希字符串,用来作为图片的唯一标识;

    可以把图片的唯一标识和相应的图像文件在图库中的路径信息,都存储在散列表中,极大的提高了查找的效率。

    数据校验

    BT下载的原理是基于P2P的,从很多机器上并行下载一个几个G的大文件,这个文件会被划分为许多文件块,下载完之后在组成一个完整的文件即可。

    但是网络传输不安全也不稳定,如何确定自己下载的文件块是否经过恶意修改的呢?

    可以采用哈希算法进行数据校验,对划分为许多块的文件分别取哈希值,哈希值对数据很敏感,只要文件块的内容篡改一点,得到的哈希值就会完全不同;在对于下载好的文件计算哈希值,在与种子文件中保存的哈希值进行比对,如果不同则说明数据已被篡改,需要重新下载。

    散列函数

    散列函数是设计一个散列表的关键,直接决定了散列冲突的概率和散列表的性能
    ,散列函数的设计追求简单高效;

    负载均衡

    我们如何在对于同一个客户端,在一次会话中的所有请求都路由到同一个服务器中;
    最简单的方法就是维护一张映射表,保存客户端IP地址与服务器编号之间的映射关系;

    弊端:

    • 客户端很多,映射表很大,占内存;
    • 客户端的上线、下线、服务器扩容、缩容都会导致映射的失效,维护映射表的成本就会变大;

    借助哈希算法,对于客户端IP地址或者会话ID计算哈希值,将取出的哈希值与服务器列表大小进行取模运算,最终得到的值就是被路由到的服务器编号;这样就可以把同一个IP过来的所有请求,都路由到同一个后端服务器上;

    数据分片

    1、如何统计“搜素关键词”的出现次数

    日志文件中包含许多搜索关键词,没法放到一台机器的内存中。同时,一台计算机处理时间会很长;

    为此可以先进行数据分片,然后采用多台机器处理,提高处理速度;思路:
    采用n台机器并行处理,从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数来计算哈希值,然后再跟n取模,得到的值就是应该被分配到的机器编号;

    那么哈希值相同的搜索关键词就会被分配到同一台机器上,每个机器会分别计算出关键词出现的次数,然后合并起来就是最终得到的结果。

    2、如何快速判断图片是否再图库中

    对于海量的图库,同样可以先对数据进行分片,采用多机处理。准备n台机器,让每台机器只维护某一部分图片对应的散列表。我们从图库中读取一个图片,计算出唯一标识,然后与机器个数n求余取模,得到的值就是机器编号,将这个图片的唯一标识和图片路径发往对应的机器构建散列表;

    当判断一张图片是否再图库中时,采用同样的哈希算法,计算出唯一标识,在与机器个数n取模,假设得到的值为k,那就去编号为k的机器构建的散列表中查找;

    分布式存储

    面对海量的数据,为了提升对于数据的读写能力,一般都采用分布式的方式来存储数据,分布式缓存;

    那么如何决定将哪个数据放到哪台机器上?
    我们可以借助前面数据分片的方式,通过哈希算法对数据取哈希值,然后在对机器个数取模,最终得到应该缓存的机器编号;

    随着数据量的增大,原来的10台机器已经无法承受了,就需要进行扩容,但不仅仅是简单增加机器就可以的,原先是与10取模计算编号,现在是与11取模进行编号计算;

    如果所有的数据都要重新计算哈希值,然后再重新将数据搬移到正确的机器中;这个时候数据库中的所有数据一下子都失效了,就会穿透缓存,直接去请求数据库,就会发生雪崩效应,压垮数据库;

    可以采用一致性哈希算法:
    假设我们有k个机器,数据哈希值的范围是[0,MAX],我们将整个范围划分成m个小区间,每个机器负责m/k个小区间,当有新的机器加入的时候,我们就将某几个小区间的数据,从原来的数据中搬移到新的机器中,这样既不用全部重新哈希、搬移数据,也保持了各个机器数据数量的均衡;

    一致性哈希算法

    三言两语说不完,回头我在补充!

    展开全文
  • 数据结构和算法美 - 21 哈希算法的定义:将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 常用哈希算法:比如 MD5、SHA ...

    数据结构和算法之美 - 21

    数据结构和算法之美 - 22 (哈希算法的三种应用:负载均衡、数据分片、分布式存储)

    哈希算法的定义:将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。

    常用哈希算法:比如 MD5、SHA 等

    哈希算法几点要求:

    • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法);
    • 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同;
    • 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
    • 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值。

    常见的哈希算法的应用:

    1. 安全加密、(依赖特性:不能反向推到,冲突概率小)
    2. 唯一标识、(对大数据做信息摘要,通过一个较短的二进制编码来表示很大的数据。)
    3. 数据校验、(依赖特性:对于输入数据非常敏感)
    4. 散列函数、
    5. 负载均衡、
    6. 数据分片、
    7. 分布式存储

    数据校验的场景:哈希算法有一个特点,对数据很敏感。只要文件块的内容有一丁点儿的改变,最后计算出的哈希值就会完全不同。所以,当文件块下载完成之后,我们可以通过相同的哈希算法,对下载好的文件块逐一求哈希值,然后跟种子文件中保存的哈希值比对。如果不同,说明这个文件块不完整或者被篡改了,需要再重新从其他宿主机器上下载这个文件块。

    负载均衡的场景:同一个客户端上,在一次会话中的所有请求都路由到同一个服务器上。通过哈希算法,对客户端 IP 地址或者会话 ID 计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。优点:无需消耗内存维护客户端和服务器对应的映射表,取模的运算可以很好地兼容服务器扩容和缩容。

    数据分片的场景:统计大数据量搜索关键词的次数,同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数,最后合并起来就是最终的结果。

    分布式存储的场景:海量的数据存储在多台机器上。通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是应该存储的缓存机器编号。缺点:机器进行扩容,前面的取模运算就需要重新计算,因此所有的数据都要重新计算哈希值,然后重新搬移到正确的机器上。这样就相当于,缓存中的数据一下子就都失效了,可能造成 雪崩效应,压垮数据库。爲了解決这个对于扩容造成问题,提出了 一致性哈希算法 : 假设我们有 k 个机器,数据的哈希值的范围是[0, MAX]。我们将整个范围划分成 m 个小区间(m 远大于 k),每个机器负责 m/k 个小区间。当有新机器加入的时候,就将某几个小区间的数据,从原来的机器中搬移到新的机器中。这样,既不用全部重新哈希、搬移数据,也保持了各个机器上数据数量的均衡。

     

     

    展开全文
  • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同; 散列冲突的概率要很小,对于不同的原始数据,哈希值相同.....

    哈希算法的定义和原理

    将任意长度的二进制串映射为固定长度的二进制串。

    这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制串就是哈希值。

    设计一个优秀的哈希算法需要满足:

    • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法);
    • 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同;
    • 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
    • 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值。

     

    MD5哈希算法

    MD5的哈希值是128位的bit长度,为了方便转换成了16进制编码。

    可以看出无论哈希值文本有多长多短,通过MD5哈希之后,得到的哈希值的长度都是一样的,

    而且得到的哈希值看起来像一堆随机数完全没有规律。

    MD5(" 今天我来讲哈希算法 ") = bb4767201ad42c74e650c1b6c03d78fa
    MD5("jiajia") = cd611a31ea969b908932d44d126d195b

     

    哈希算法的应用

    安全加密

    加密算法

    最常用于加密的哈希算法是MD5(MD5 Message-Digest Algorithm,MD5 消息摘要算法)和SHA(Secure Hash Algorithm,安全散列算法)。

    对用于加密的哈希算法来说,有两点格外重要:

    • 很难根据哈希值反向推导出原始数据,
    • 散列冲突的概率要很小。

    实际上,不管是什么哈希算法,我们只能尽量减

    少碰撞冲突的概率,理论上是没办法做到完全不冲突的。

    鸽巢理论

    这里就基于组合数学中一个非常基础的理论,鸽巢原理(也叫抽屉原理)。

    这个原理本身很简单,它是说如果有 10 个鸽巢,有 11 只鸽子那肯定有 1 个鸽巢中的鸽子数量多于 1 个。

    换句话说就是,肯定有 2 只鸽子在 1 个鸽巢内。

    我们知道,哈希算法产生的哈希值的长度是固定且有限的。

    哈希值是固定的 128 位二进制串,能表示的数据是有限的最多能表示 2^128 个数据。

    基于鸽巢原理,如果我们对 2^128+1 个数据求哈希值,就必然会存在哈希值相同的情况。

     

    唯一标识

    在图库中搜索图片

    如果要在海量的图库中,搜索一张图是否存在,我们不能单纯地用图片的元信息(比如图片名称)来比对。

    因为有可能存在名称相同但图片内容不同,或者名称不同图片内容相同的情况。

    我们可以给每一个图片取一个唯一标识,或者说信息摘要。

    比如,我们可以从图片的二进制码串开头取 100 个字节,从中间取 100 个字节,从最后再取 100 个字节。

    然后将这 300 个字节放到一块,通过哈希算法(比如 MD5)得到一个哈希字符串,用它作为图片的唯一标识。

    通过这个唯一标识来判定图片是否在图库中,这样就可以减少很多工作量

    性能提升

    如果还想继续提高效率,我们可以把每个图片的唯一标识和相应的图片文件在图库中的路径信息,都存储在散列表中。

    当要查看某个图片是不是在图库中的时候,我们先通过哈希算法对这个图片取唯一标识,然后在散列表中查找是否存在这个唯一标识。

     

    数据校验

    P2P文件快校验

    BT 下载的原理是基于 P2P 协议的。

    我们从多个机器上并行下载一个 2GB 的电影,这个电影文件可能会被分割成很多文件块(比如可以分成100 块,每块大约 20MB)。

    等所有的文件块都下载完成之后,再组装成一个完整的电影文件就行了。

    网络传输是不安全的,下载的文件块有可能是被宿主机器恶意修改过的,又或者下载过程中出现了错误,所以下载的文件块可能不是完整的。

    解决方法

    我们通过哈希算法,对 100 个文件块分别取哈希值并且保存在种子文件中。

    当文件块下载完成之后,我们可以通过相同的哈希算法,对下载好的文件块逐一求哈希值,然后跟种子文件中保存的哈希值比对。

    如果不同,说明这个文件块不完整或者被篡改了,需要再重新从其他宿主机器上下载这个文件块。

     

    散列函数

    散列函数是一种哈希算法

    实际上,散列函数也是哈希算法的一种应用。

    散列函数是设计一个散列表的关键。

    它直接决定了散列冲突的概率和散列表的性能。

    不过,相对哈希算法的其他应用,散列函数对于散列算法冲突的要求要低很多。

    即便出现个别散列冲突,只要不是过于严重,我们都可以通过开放寻址法或者链表法解决。

    散列函数追求平均分布

    不仅如此,散列函数对于散列算法计算得到的值,是否能反向解密也并不关心。

    散列函数中用到的散列算法,更加关注散列后的值是否能平均分布。

    也就是一组数据是否能均匀地散列在各个槽中。

    除此之外,散列函数执行的快慢,也会影响散列表的性能,

    所以,散列函数用的散列算法一般都比较简单,比较追求效率。

     

    负载均衡

    我们需要在同一个客户端上,在一次会话中的所有请求都路由到同一个服务器上。

    最直接的方法就是,维护一张映射关系表,这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。

    客户端发出的每次请求,都要先在映射表中查找应该路由到的服务器编号,然后再请求编号对应的服务器。

    这种方法简单直观,但也有几个弊端:

    • 如果客户端很多,映射表可能会很大,比较浪费内存空间;
    • 客户端下线、上线,服务器扩容、缩容都会导致映射失效,这样维护映射表的成本就会很大;

    如果借助哈希算法,这些问题都可以非常完美地解决。

    我们可以通过哈希算法,对客户端 IP 地址或者会话 ID 计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。

    这样,我们就可以把同一个 IP 过来的所有请求,都路由到同一个后端服务器上。

     

    数据分片

    统计“搜索关键词”出现的次数

    假如我们有 1T 的日志文件,这里面记录了用户的搜索关键词,

    我们想要快速统计出每个关键词被搜索的次数。

    我们可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度。

    为了提高处理的速度,我们用 n 台机器并行处理。

    我们从搜索记录的日志文件中,依次读出每个搜索关键词,

    并且通过哈希函数计算哈希值,然后再跟 n 取模,最终得到的值,就是应该被分配到的机器编号。

    这样,哈希值相同的搜索关键词就被分配到了同一个机器上。

    也就是说,同一个搜索关键词会被分配到同一个机器上。

    每个机器会分别计算关键词出现的次数,最后合并起来就是最终的结果。

    快速判断图片是否在图库中

    假设现在我们的图库中有 1 亿张图片,在单台机器上构建散列表是行不通的。

    我们同样可以对数据进行分片,然后采用多机处理。

    我们准备 n 台机器,让每台机器只维护某一部分图片对应的散列表。

    我们每次从图库中读取一个图片,计算唯一标识,

    然后与机器个数 n 求余取模,得到的值就对应要分配的机器编号,

    然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。

    当我们要判断一个图片是否在图库中的时候,我们通过同样的哈希算法,

    计算这个图片的唯一标识,然后与机器个数 n 求余取模。

    假设得到的值是 k,那就去编号 k 的机器构建的散列表中查找。

     

    分布式存储

    我们有海量的数据需要缓存,所以一个缓存机器肯定是不够的。

    我们需要将数据分布在多台机器上通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是应该存储的缓存机器编号

    如果数据增多,原来的 10 个机器已经无法承受,我们需要扩容,假如扩到 11 个机器。

    原来的数据是通过与 10 来取模的,比如 13 这个数据,存储在编号为 3 这台机器上。

    新加了一台机器后,我们对数据按照 11 取模,原来 13 这个数据被分配到了 2 号这台机器上。

    因此,所有的数据都要重新计算哈希值,然后重新搬移到正确的机器上。

    所有的数据请求都会穿透缓存,直接去请求数据库,可能会发生雪崩效应,压垮数据库。

    我们需要一种方法,使得在新加入一个机器后,并不需要做大量的数据搬移。

    这时候,一致性哈希算法就要登场了。

    一致性哈希算法

    假设我们有 k 个机器,数据的哈希值的范围是 [0, MAX]。

    我们将整个范围划分成 m 个小区间(m 远大于 k),每个机器负责 m/k 个小区间。

    当有新机器加入的时候,我们就将某几个小区间的数据,从原来的机器中搬移到新的机器中。

    这样既不用全部重新哈希、搬移数据,也保持了各个机器上数据数量的均衡。

     

    转载于:https://www.cnblogs.com/errornull/p/9952646.html

    展开全文
  • Hashing哈希方程字典(Dictionaries)直接访问表Hashing With Chaining开放寻址法(Open Addressing)Probing使用开放寻址搜索开放寻址哈希函数Linear ProbingDouble Hashingh2的选择:Chaining 与Open Addressing使用...
  • 哈希算法历史悠久,业界著名的哈希算法也有很多,比如MD5、SHA等。那么在实际的开发中,我们该如何用哈希算法解决问题。 二、什么是哈希算法 将任意长度的二进制值映射为固定长度的二进制值串,这个映...
  • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同; 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的...
  • 1、从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 2、对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同; 3、散列冲突的概率要很小,对于不同的原始数据,哈希...
  • 哈希表:是一种key-value存储数据结构 使用哈希表的两个步骤:  1.无序数组:将键值key转化为对应的索引(f(key)),根据索引来寻找对应的值(value)  2.解决哈希冲突:当key值不同,但f(key)相同 哈希函数...
  • 哈希算法的定义:将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 一个优秀的哈希算法需要满足的以下几点要求: 从哈希值不...
  • 数据结构之哈希算法

    千次阅读 2013-09-11 19:37:02
    对于char* str,常用的哈希算法(信息加密)有如下: BKDRHash: 1)hash = hash * seed + (*str++) 2)hash初始值为0 · 3)seed: 31 、131 、1313、 13131 、131313 etc.. ELFHash: 1) SDBMHash: 1)hash = ...
  • 数据结构与算法美 - 22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用? 上一节,我讲了哈希算法的四个应用,它们分别是:安全加密、数据校验、唯一标识、散列函数。今天,我们再来看剩余三种应用:负载...
  • 哈希算法是将不同长度二进制串转换为固定长度二进制串的算法,在加密,唯一性校验,数据分片等方面都有应用 该叫散列函数还是哈希函数 看到哈希函数时心中总是会泛起疑问,哈希算法需要单独列出,那散列函数又是...
  • 什么是哈希算法? 我们前面几节讲到“散列表”“散列函数”,这里又讲到“哈希算法”,你是不是有点一头雾水?实际上,不管是“散列”还是“哈希”,这都是中文翻译的差别,英文其实就是“Hash”。所以,我们常听到...
  • 哈希算法不是仅仅应用于我们常用结构哈希表中,哈希算法是一个更加广泛的概念。将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值...
  • 哈希算法的定义和原理很简单,就是把任意二进制串值映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始的数据映射之后得到的二进制值串就是哈希值。 哈希算法满足的几点要求: 从哈希值不能反向...
  • 数据结构算法之哈希

    千次阅读 多人点赞 2020-05-22 19:24:29
    数据结构算法之哈希表 该系列为博主自己学习记录数据结构算法的实现。 本篇文章主要介绍哈希表(Hash Table,又称散列表)的原理、部分源码、以及练习实现。 目录数据结构算法之哈希表一、哈希表原理(一)、...
  • 哈希算法 (1)什么是哈希算法?...从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法); 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同; 散列冲...
  • 通过哈希算法对客户端IP或会话ID计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。这样,就可以把同一个IP过来的请求都路由到同一个后端服务器上。 二、数据...
  • 哈希算法的应用—负载均衡 实现一个会话粘滞(session sticky)的负载均衡的算法即在同一个客户端上一次会话的所有请求都能路由到同一个服务器上。 最简单的办法就是维护一张映射表,映射表中记录会话ID或者客户端IP...
  • 开篇说明:本文内容大部分出自于极客时间中的《数据结构算法之美》专栏,Mark下来,作为个人笔记,方便日后复习。 在上一篇博客中,讲解了散列表的用法,如果你对散列表还不是很了解,可以点击此链接进行查看:...
  • 文章目录java数据结构算法之哈希表哈希表(散列)哈希表的基本介绍google 公司的一个上机题:代码实现 java数据结构算法之哈希表 哈希表(散列) 看一个实际需求, google 公司的一个上机题: 有一个公司,当有新的...
  • 文章目录1....  一句话:将任意长度的二进制值串映射成固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 1.2 如何设计优秀的哈希算法 单...
  • 上一节,我讲了哈希算法的四个应⽤,它们分别是:安全加密、数据校验、唯⼀标识、散列函数。今天,我们再来看剩余三种应用: 负载均衡、数据分片、分布式存储 你可能已经发现,这三个应用都跟分布式系统有关。没错...
  • JAVA数据结构与算法之哈希算法 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数...
  • 数据结构之哈希表-JAVA代码实现原文地址,点击访问 哈希表(散列表) key value 形式的数据结构,其基础是一个数组。哈希表在特定元素的插入,删除和查询时都能够达到O(1)常数的时间复杂度,除非发生hash碰撞 ...
  • 数据结构之哈希表HashTable实例讲解

    千次阅读 2018-06-06 14:56:25
    哈希表 是一种以关联方式存储数据的数据结构,在哈希表中,数据以数组格式存储,其中每个数据值都有自己唯一的索引。如果我们知道所需数据的索引,那么数据的访问就会变得非常快。 所以关键是 找到索引, 而检索 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 910
精华内容 364
关键字:

数据结构之哈希算法

数据结构 订阅