- 浏览: 190035 次
- 性别:
- 来自: 上海
文章分类
最新评论
什么是Hash
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
Hash主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,Hash就是找到一种数据内容和数据存放地址之间的映射关系。
一致性哈希算法应用与分析
一致性哈希算法主要使用在分布式数据存储系统中,按照一定的策略将数据尽可能均匀分布到所有的存储节点上去,使得系统具有良好的负载均衡性能和扩展性。感觉一致性哈希与数据结构中的“循环队列”还是有一点联系的。
1.简单哈希算法
哈希(hash)计箅是常见的数据分布技术,其通过求模运算来计算哈希值,然后据此将数据映射到存储空间中。由于只是采用了简单的求模运算.使得简单哈希计算存在很多不足:
1)增删市点时,更新效率低。当系统中存储节点数量发生增加或减少时,映射公式将发生变化为hash(object)%(N±1)(余数式哈希),这将使得所有obiect的映射位置发生变化,整个系统数据对象的映射位置都需要重新进行计算,系统无法对外界访问进行正常响应,将导致系统处于崩溃状态。
2)平衡性差,未考虑节点性能差异。由于硬件性能的提升,新添加的节点具有更好的承载能力,如何对算法进行改进,使节点性能可以得到较好利用。
3)单调性不足。衡量数据分布技术的一项重要指标是单调性,单调性是指如果已经有一些内容通过哈希计算分派到了相应的缓冲中,当又有新的缓冲加入到系统中时,哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。
2.一致性哈希算法的工作原理
2.1 数据保存
一致性哈希,是对简单哈希算法进行了修正,它的原理分为两步。
首先,对“存储节点”的哈希值进行计算,其将存储空间抽象为一个环。如下图中的1、2、3三个节点就可以理解为三个可以存储数据的“存储节点”。其次,对要存储的数据也进行同样的哈希计算,按顺时针方向将其映射到离其最近的节点上去。
2.2 节点失效情况
当有存储节点出现故障离线时,按照映射方法,受影响的仅仅为从环上故障节点开始逆时针方向至前一个节点之间区间的数据对象。而这些对象本身就是映射到故障节点之上的。
例如在存储节点4出现故障时,只会影响那些数据的哈希值在存储节点3到存储节点4哈希值之间的数据节点,影响不会进一步扩大。
2.3增加存储节点时
当有节点增加时,比如,在存储节点2和存储节点3之间重新添加一个存储节点5。受影响的也仅仅是存储节点5逆时针遍历直到存储节点2之间的数据对象,将这些重新映射到5上即可,因此,当有节点出现变动时,不会使得整个存储空间上的数据都进行重新映射。解决了简单哈希算法增删节点,重新映射所有数据带来的效
率低下的问题。
3.虚拟节点的概念
一致性哈希算法具有随机性。当存储节点数量较少时节点在环上分布不够均匀。为解决这个问题,提出了基于虚拟节点的改进算法,其核心思路是引入虚拟节点。
每个虚拟节点都有一个对应的物理节点,而每个物理节点可以对应若干个虚拟节点。
在2.1的图中有存储节点1、2、3、4可以看出分布不均匀。假定四个存储节点型号相同,可以说节点4的负载量最小的,节点3最大。为了负载均衡,可以由物理存储节点来引入了虚拟节点4''',如下图所示。可以将虚拟节点理解为一个“符号标记”,按照2.1中的规则将数据的保存在存储节点上,只是应在虚拟节点保存的数据实际保存在对应的物理节点4上。这样就在一定程度上解决了负载均衡。
http://www.cnblogs.com/xudong-bupt/p/3185194.html
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
Hash主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,Hash就是找到一种数据内容和数据存放地址之间的映射关系。
一致性哈希算法应用与分析
一致性哈希算法主要使用在分布式数据存储系统中,按照一定的策略将数据尽可能均匀分布到所有的存储节点上去,使得系统具有良好的负载均衡性能和扩展性。感觉一致性哈希与数据结构中的“循环队列”还是有一点联系的。
1.简单哈希算法
哈希(hash)计箅是常见的数据分布技术,其通过求模运算来计算哈希值,然后据此将数据映射到存储空间中。由于只是采用了简单的求模运算.使得简单哈希计算存在很多不足:
1)增删市点时,更新效率低。当系统中存储节点数量发生增加或减少时,映射公式将发生变化为hash(object)%(N±1)(余数式哈希),这将使得所有obiect的映射位置发生变化,整个系统数据对象的映射位置都需要重新进行计算,系统无法对外界访问进行正常响应,将导致系统处于崩溃状态。
2)平衡性差,未考虑节点性能差异。由于硬件性能的提升,新添加的节点具有更好的承载能力,如何对算法进行改进,使节点性能可以得到较好利用。
3)单调性不足。衡量数据分布技术的一项重要指标是单调性,单调性是指如果已经有一些内容通过哈希计算分派到了相应的缓冲中,当又有新的缓冲加入到系统中时,哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。
2.一致性哈希算法的工作原理
2.1 数据保存
一致性哈希,是对简单哈希算法进行了修正,它的原理分为两步。
首先,对“存储节点”的哈希值进行计算,其将存储空间抽象为一个环。如下图中的1、2、3三个节点就可以理解为三个可以存储数据的“存储节点”。其次,对要存储的数据也进行同样的哈希计算,按顺时针方向将其映射到离其最近的节点上去。
2.2 节点失效情况
当有存储节点出现故障离线时,按照映射方法,受影响的仅仅为从环上故障节点开始逆时针方向至前一个节点之间区间的数据对象。而这些对象本身就是映射到故障节点之上的。
例如在存储节点4出现故障时,只会影响那些数据的哈希值在存储节点3到存储节点4哈希值之间的数据节点,影响不会进一步扩大。
2.3增加存储节点时
当有节点增加时,比如,在存储节点2和存储节点3之间重新添加一个存储节点5。受影响的也仅仅是存储节点5逆时针遍历直到存储节点2之间的数据对象,将这些重新映射到5上即可,因此,当有节点出现变动时,不会使得整个存储空间上的数据都进行重新映射。解决了简单哈希算法增删节点,重新映射所有数据带来的效
率低下的问题。
3.虚拟节点的概念
一致性哈希算法具有随机性。当存储节点数量较少时节点在环上分布不够均匀。为解决这个问题,提出了基于虚拟节点的改进算法,其核心思路是引入虚拟节点。
每个虚拟节点都有一个对应的物理节点,而每个物理节点可以对应若干个虚拟节点。
在2.1的图中有存储节点1、2、3、4可以看出分布不均匀。假定四个存储节点型号相同,可以说节点4的负载量最小的,节点3最大。为了负载均衡,可以由物理存储节点来引入了虚拟节点4''',如下图所示。可以将虚拟节点理解为一个“符号标记”,按照2.1中的规则将数据的保存在存储节点上,只是应在虚拟节点保存的数据实际保存在对应的物理节点4上。这样就在一定程度上解决了负载均衡。
http://www.cnblogs.com/xudong-bupt/p/3185194.html
发表评论
-
ReentrantLock与Condition
2017-03-17 14:25 532多线程和并发性并不是什么新内容,但是 Java 语言设计中的创 ... -
java linux监控
2017-03-13 17:49 502http://agapple.iteye.com/blog/1 ... -
transient和volatile两个关键字
2017-02-16 09:47 575transient和volatile两个关 ... -
java 锁机制
2016-12-09 13:43 479一段synchronized的代码被 ... -
java 正则表达式
2016-12-02 10:28 522众所周知,在程序开发中,难免会遇到需要匹配、查找、替换、判断字 ... -
java ClassNotFoundException和NoClassDefFoundException的差别
2016-08-17 19:47 912首先从名字上可以看出一类是异常,一类属于错误。异常可以通过异常 ... -
ThreadLocal
2016-07-19 11:10 334ThreadLocal是什么 Thre ... -
java CAS
2016-07-10 14:55 346cas 乐观锁每次不锁定整个线程,在操作之前进行判断。悲观锁独 ... -
concurrenthashmap
2016-07-10 11:11 425hash table虽然性能上不如 ... -
java 线程池的使用
2016-07-10 09:52 3761. 引言 合理利用线程池能够带来三个好处。第一:降低资源消 ... -
java.util.concurrent
2016-07-03 16:24 412我们都知道,在JDK1.5之 ... -
JVM 配置 以及垃圾收集器的选择
2016-04-15 12:36 734JVM监控的关键指标说明: a) FGC的环比增加次数。Zab ... -
jvm实时监控工具
2016-04-09 09:35 469 -
jvm dump 相关
2016-03-22 17:22 684http://www.cnblogs.com/edwardla ... -
深入剖析volatile关键字
2016-03-21 16:02 551深入剖析volatile关键字 ... -
java线程安全问题之静态变量、实例变量、局部变量
2016-03-08 12:52 577java多线程编程中,存在很多线程安全问题,至于什么是线程安全 ... -
有状态的bean和无状态的bean的区别
2016-03-08 11:23 1523有状态会话bean :每个用户有自己特有的一个实例,在用户的生 ... -
Java nio详解
2016-01-20 16:30 556http://www.ibm.com/developerwor ... -
java 不定长数组
2015-11-24 15:00 789在调用某个方法时,若是方法的参数个数事先无法确定该如何处理 ... -
Java stack and heap dump
2015-11-14 16:13 1064对于大型 java 应用程序来说,再精细的测试都难以堵住所有的 ...
相关推荐
白话解析:一致性哈希算法1 一致性哈希算法是解决分布式缓存问题的解决方案。缓存服务器数量的变化会引起缓存的雪崩,导致整体系统压力过大而崩溃。为了解决这个问题,一致性哈希算法诞生了。 在了解一致性哈希...
在本例中,"计算文件哈希值的程序"是一个能够帮助用户获取文件哈希值的应用,这有助于检测文件是否被篡改或者比较两个文件的一致性。 哈希函数是这些程序的核心,常见的有MD5(Message-Digest Algorithm 5)、SHA...
5. **余数法**:这是最简单的一种哈希函数构造方法,将输入的数字除以哈希表的大小,取余数作为哈希值。这种方法简单易行,但在处理大整数或字符串时可能会导致较多的冲突。 哈希查找算法的优势在于其高效性,理想...
总的来说,MD5、SHA和CRC哈希算法都是用来验证数据完整性和防止篡改的重要工具。虽然MD5的安全性已不再被信任,但在某些场景下仍然有用,而SHA和CRC则提供了更高的安全性和可靠性。通过`hasher.exe`这样的工具,用户...
而哈希算法则更多地用于数据完整性校验,例如在文件下载或备份时,通过比较源文件和目标文件的哈希值来确认文件是否一致。 "makeCRC"可能是一个工具或程序,用于生成CRC16校验码。使用这样的工具,用户可以输入数据...
解决哈希冲突有多种方法,包括开放寻址法、链地址法以及简单的哈希一致性策略。 1. **链地址法**: 当两个或多个键映射到同一个哈希槽时,可以使用链表来处理冲突。每个哈希槽成为一个链表的头,所有映射到该槽的...
6. **应用实例**: 哈希算法在实际开发中有着广泛的应用,如缓存(如Redis的哈希数据结构)、数据库索引、密码存储(通过哈希加密存储)、一致性哈希(分布式系统中负载均衡的关键技术)等。 学习这个开源项目,...
同时,它也能与网络通信模块配合,确保在网络传输过程中数据的完整性和一致性。 总的来说,易语言哈希类模块是易语言编程中的一个重要工具,它提供了强大的数据处理功能,特别是在数据校验和快速查找的应用中。深入...
总结来说,Memcached的分布式缓存实现主要依赖于客户端的哈希算法,包括余数计算分散法和一致性哈希。这些策略确保了数据在多台服务器间的有效分布,减少了数据库的压力,提高了系统的响应速度和可扩展性。在实际...
- 设计分布式系统中的一致性哈希。 综上所述,哈希算法在IT领域具有广泛的应用,理解和优化哈希函数对于提升系统的性能和安全性至关重要。通过分析`hash.c`和`hash.h`文件,我们可以深入理解特定哈希算法的实现...
同时,调试时要确保哈希函数的正确性和冲突处理的有效性。 总结,哈希表的实现涉及到哈希函数的设计、冲突处理策略的选择以及性能优化。通过理解这些概念,并在实际项目中应用,可以有效地提高数据存取效率,这对于...
用户可以通过这个工具输入文件路径,然后它会计算出对应文件的MD5、SHA1、普通Hash和CRC32值,以此来验证文件的完整性和一致性。 在实际应用中,这些哈希工具对于程序员、系统管理员、数据分析师等IT专业人员来说...
3. **随机法**:当关键字长度不一致时,可以使用随机函数生成哈希地址,即H(key) = ran(key),这种方法能够适应不同长度的关键字,但可能需要良好的随机数生成器来保证哈希分布的均匀性。 哈希函数设计的关键在于...
与简单的余数哈希算法相比,一致性哈希算法能够更好地处理服务器添加或删除的情况,保持缓存的一致性和可用性。 **余数哈希算法的问题:** 当服务器集群规模发生变化时,例如从3台服务器增加到4台服务器,原有的...
使用哈希版本校验工具,如提供的"hash.exe",可以对文件进行校验,确保文件在不同位置或不同时间的副本是完全一致的。具体操作通常是先计算原始文件的哈希值,然后对比目标文件的哈希值,如果两者相同,则说明文件...
MD5的主要目标是确保数据的完整性和一致性,常用于验证文件的完整性、存储密码的不可逆性和数字签名。 1. **哈希函数基础** - **单向性**:哈希函数设计使得从原始数据计算哈希值容易,但由哈希值恢复原始数据极其...
这样的工具可以帮助用户快速计算文件的哈希值,进行数据一致性验证,或者与其他已知的哈希值进行比较。在处理大量文件时,这样的工具可以极大地提高效率,确保数据的准确性和安全性。 在实际应用中,哈希算法不仅...
通常使用的哈希函数包括无符号右移16位然后异或运算,平方取中法,伪随机数法和取余数法等。无符号右移16位异或运算效率最高。当两个对象的哈希码相等时,会通过 `equals` 方法比较键的内容是否相同,以决定是否替换...
在上述例子中,简单的哈希函数是`X % 8`,它将数字对8取余,得到的余数作为哈希值。当多个对象映射到同一个哈希值时,就会形成链表,以解决冲突。 `equals()`方法同样来自`Object`类,用于比较两个对象的内容是否...
总的来说,Hash V1.04是一款实用的文件校验工具,通过MD5、SHA1和CRC32这三种哈希算法,它能帮助用户确保数据的完整性和一致性,从而保护了我们的数字资产免受潜在威胁。在日常工作中,了解并正确使用这类工具,是...