精华内容
下载资源
问答
  • 哈希摘要 - 数字签名/指纹 - 单向哈希函数(没有反函数不可逆) 应用领域: 1. 数据库种的用户敏感信息保存成哈希摘要 2. 给数据生成签名验证数据没有被恶意篡改 3. 云存储服务的妙传功能(去重功能) ''' class ...
    # -*- coding:utf8 -*-
    '''
    哈希摘要 - 数字签名/指纹 - 单向哈希函数(没有反函数不可逆)
    应用领域:
    1. 数据库种的用户敏感信息保存成哈希摘要
    2. 给数据生成签名验证数据没有被恶意篡改
    3. 云存储服务的妙传功能(去重功能)
    '''
    
    
    class StreamHasher():
        """摘要生成器"""
    
        def __init__(self, algorithm='md5', size=4096):
            """初始化方法
            @params:
                algorithm - 哈希摘要算法
                size - 每次读取数据的大小
            """
            self.size = size
            cls = getattr(__import__('hashlib'), algorithm.lower())
            self.hasher = cls()
    
        def digest(self, file_stream):
            """生成十六进制的摘要字符串"""
            # log = file_stream.read(self.size)
            # while log:
            #     self.hasher.update(log)
            #     log = file_stream.read(self.size)
            for data in iter(lambda: file_stream.read(self.size), b''):
                self.hasher.update(data)
            return self.hasher.hexdigest()
    
        def __call__(self, file_stream):
            return self.digest(file_stream)
    
    
    def main():
        """主函数"""
        hasher1 = StreamHasher()
        hasher2 = StreamHasher('sha1')
        hasher3 = StreamHasher('sha256')
        with open('zbar-0.10.tar.bz2', 'rb') as file_stream:
            print(hasher1.digest(file_stream))
            file_stream.seek(0, 0)
            print(hasher2.digest(file_stream))
            file_stream.seek(0, 0)
            print(hasher3(file_stream))
    
    
    if __name__ == '__main__':
        main()
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    展开全文
  • 算法将3D卷积神经网络与哈希学习方法结合应用于视频数据,既能快速学习视频时空特征表示,又能极大地缩短视频检索时间。在常用视频数据集上的实验结果表明,利用所提出的方法对视频进行相似性检索性能优于当前主流...
  • 主要介绍了c#哈希算法的实现方法及思路,有需要的朋友可以参考一下
  • 哈希算法的实现

    2015-12-11 23:36:53
    数据结构作业四,对哈希
  • 本人为在校大学生,所写源码可能不够尽善尽美,希望各位包涵指正。写这个代码只是为了练手,可能有错误,只为大家提供思路和方法。
  • 多种哈希算法代码,用于文件校验、简单加密等场合。
  • delphi下面开发的国产哈希算法SM3可以直接调用接口 里面的代码注释写的很明白 我自己做项目测试了可以使用 没得问题
  • 为克服此类问题, 设计了基于改进的局部二值模式(LBP)算子与动态更新变换的紧凑图像哈希算法。引入线性插值技术, 对输入图像实现预处理, 改善哈希序列对尺度缩放的稳健性。利用Ring分割, 将插值图像转化成二次图像。...
  • 参考网上博客的感知哈希算法的理论知识,实现基本的感知哈希算法,内有几张图片用来测试,程序可参考。
  • Redis一致性哈希算法

    千次阅读 2019-02-25 00:08:23
    网站为了支撑更大的用户访问量,往往需要对用户访问的数据做cache,服务机群和负载均衡来专门处理缓存,负载均衡的算法很多,轮循算法、哈希算法、最少连接算法、响应速度算法等,hash算法是比较常用的一种,它的常用...

    网站为了支撑更大的用户访问量,往往需要对用户访问的数据做cache,服务机群和负载均衡来专门处理缓存,负载均衡的算法很多,轮循算法、哈希算法、最少连接算法、响应速度算法等,hash算法是比较常用的一种,它的常用思想是先计算出一个hash值,然后使用 CRC余数算法将hash值和机器数mod后取余数,机器的编号可以是0到N-1(N是机器数),计算出的结果一一对应即可。

           缓存最关键的就是命中率这个因素,如果命中率非常低,那么缓存也就失去了它的意义。如采用一般的CRC取余的hash算法虽然能达到负载均衡的目的,但是它存在一个严重的问题,那就是如果其中一台服务器down掉,那么就需要在计算缓存过程中将这台服务器去掉,即N台服务器,目前就只有N-1台提供缓存服务,此时需要一个rehash过程,而reash得到的结果将导致正常的用户请求不能找到原来缓存数据的正确机器,其他N-1台服务器上的缓存数据将大量失效,此时所有的用户请求全部会集中到数据库上,严重可能导致整个生产环境挂掉.

           举个例子,有5台服务器,编号分别是0(A),1(B),2(C),3(D),4(E)  ,正常情况下,假设用户数据hash值为12,那么对应的数据应该缓存在12%5=2号服务器上,假设编号为3的服务器此时挂掉,那么将其移除后就得到一个新的0(A),1(B),2(C),3(E)(注:这里的编号3其实就是原来的4号服务器)服务器列表,此时用户来取数据,同样hash值为12,rehash后的得到的机器编号12%4=0号服务器,可见,此时用户到0号服务器去找数据明显就找不到,出现了cache不命中现象,如果不命中此时应用会从后台数据库重新读取数据再cache到0号服务器上,如果大量用户出现这种情况,那么后果不堪设想。同样,增加一台缓存服务器,也会导致同样的后果。

           可以有一种设想,要提高命中率就得减少增加或者移除服务器rehash带来的影响,那么有这样一种算法么?Consistent hashing算法就是这样一种hash算法,简单的说,在移除/添加一个 cache 时,它能够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性的要求。


    1.环形Hash空间
           按照常用的hash算法来将对应的key哈希到一个具有2^32个桶的空间中,即0~(2^32)-1的数字空间中。可以将这些数字头尾相连,想象成一个闭合的环形。如下图:


    2.把数据通过一定的hash算法处理后映射到环上
          现在将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值,然后散列到Hash环上。如下图:
          Hash(object1) = key1;
          Hash(object2) = key2;
          Hash(object3) = key3;
          Hash(object4) = key4;


    3.将机器通过hash算法映射到环上
          在采用一致性哈希算法的分布式集群中将新的机器加入,其原理是通过使用与对象存储一样的Hash算法将机器也映射到环中(一般情况下对机器的hash计算是采用机器的IP或者机器唯一的别名作为输入值),然后以顺时针的方向计算,将所有对象存储到离自己最近的机器中。
          假设现在有NODE1,NODE2,NODE3三台机器,通过Hash算法得到对应的KEY值,映射到环中,其示意图如下:
           Hash(NODE1) = KEY1;
           Hash(NODE2) = KEY2;
           Hash(NODE3) = KEY3;

           通过上图可以看出对象与机器处于同一哈希空间中,这样按顺时针转动object1存储到了NODE1中,object3存储到了NODE2中,object2、object4存储到了NODE3中。在这样的部署环境中,hash环是不会变更的,因此,通过算出对象的hash值就能快速的定位到对应的机器中,这样就能找到对象真正的存储位置了。

    4.机器的删除与添加
           普通hash求余算法最为不妥的地方就是在有机器的添加或者删除之后会照成大量的对象存储位置失效,这样就大大的不满足单调性了。下面来分析一下一致性哈希算法是如何处理的。
           1. 节点(机器)的删除
           以上面的分布为例,如果NODE2出现故障被删除了,那么按照顺时针迁移的方法,object3将会被迁移到NODE3中,这样仅仅是object3的映射位置发生了变化,其它的对象没有任何的改动。如下图:

           2. 节点(机器)的添加 
           如果往集群中添加一个新的节点NODE4,通过对应的哈希算法得到KEY4,并映射到环中,如下图:

           通过按顺时针迁移的规则,那么object2被迁移到了NODE4中,其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析,一致性哈希算法在保持了单调性的同时,还是数据的迁移达到了最小,这样的算法对分布式集群来说是非常合适的,避免了大量数据迁移,减小了服务器的的压力。

    5.平衡性
           根据上面的图解分析,一致性哈希算法满足了单调性和负载均衡的特性以及一般hash算法的分散性,但这还并不能当做其被广泛应用的原由,因为还缺少了平衡性。下面将分析一致性哈希算法是如何满足平衡性的。
           hash算法是不保证平衡的,如上面只部署了NODE1和NODE3的情况(NODE2被删除的图),object1存储到了NODE1中,而object2、object3、object4都存储到了NODE3中,这样NODE3节点由于承担了NODE2节点的数据,所以NODE3节点的负载会变高,NODE3节点很容易也宕机,这样依次下去可能造成整个集群都挂了。
           在一致性哈希算法中,为了尽可能的满足平衡性,其引入了虚拟节点。“虚拟节点”( virtual node )是实际节点(机器)在 hash 空间的复制品(replica),一实际个节点(机器)对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以hash值排列。即把想象在这个环上有很多“虚拟节点”,数据的存储是沿着环的顺时针方向找一个虚拟节点,每个虚拟节点都会关联到一个真实节点。
            图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点,机器A负载存储A1、A2的数据,机器B负载存储B1、B2的数据,机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多,均匀分布,因此不会造成“雪崩”现象。

     

          使用虚拟节点的思想,为每个物理节点(服务器)在圆上分配100~200个点。这样就能抑制分布不均匀,最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上,就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。
          下面有一个图描述了需要为每台物理服务器增加的虚拟节点。

          x轴表示的是需要为每台物理服务器扩展的虚拟节点倍数(scale),y轴是实际物理服务器数,可以看出,当物理服务器的数量很小时,需要更大的虚拟节点,反之则需要更少的节点,从图上可以看出,在物理服务器有10台时,差不多需要为每台服务器增加100~200个虚拟节点才能达到真正的负载均衡。


    简单的java代码实现:
    
     
    1. public class ConsistentHash<T> {
    2. /**
    3. * 哈希函数
    4. */
    5. private final HashFunction hashFunction;
    6. /**
    7. * 虚拟节点数 , 越大分布越均衡,但越大,在初始化和变更的时候效率差一点。 测试中,设置200基本就均衡了。
    8. */
    9. private final int numberOfReplicas;
    10. /**
    11. * 环形Hash空间
    12. */
    13. private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
    14. /**
    15. * @param hashFunction
    16. * ,哈希函数
    17. * @param numberOfReplicas
    18. * ,虚拟服务器系数
    19. * @param nodes
    20. * ,服务器节点
    21. */
    22. public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
    23. Collection<T> nodes) {
    24. this.hashFunction = hashFunction;
    25. this.numberOfReplicas = numberOfReplicas;
    26. for (T node : nodes) {
    27. this.addNode(node);
    28. }
    29. }
    30. /**
    31. * 添加物理节点,每个node 会产生numberOfReplicas个虚拟节点,这些虚拟节点对应的实际节点是node
    32. */
    33. public void addNode(T node) {
    34. for ( int i = 0; i < numberOfReplicas; i++) {
    35. int hashValue = hashFunction.hash(node.toString() + i);
    36. circle.put(hashValue, node);
    37. }
    38. }
    39. /**移除物理节点,将node产生的numberOfReplicas个虚拟节点全部移除
    40. * @param node
    41. */
    42. public void removeNode(T node) {
    43. for ( int i = 0; i < numberOfReplicas; i++) {
    44. int hashValue = hashFunction.hash(node.toString() + i);
    45. circle.remove(hashValue);
    46. }
    47. }
    48. /**
    49. * 得到映射的物理节点
    50. *
    51. * @param key
    52. * @return
    53. */
    54. public T getNode(Object key) {
    55. if (circle.isEmpty()) {
    56. return null;
    57. }
    58. int hashValue = hashFunction.hash(key);
    59. // System.out.println("key---" + key + " : hash---" + hash);
    60. if (!circle.containsKey(hashValue)) {
    61. // 返回键大于或等于hash的node,即沿环的顺时针找到一个虚拟节点
    62. SortedMap<Integer, T> tailMap = circle.tailMap(hashValue);
    63. // System.out.println(tailMap);
    64. // System.out.println(circle.firstKey());
    65. hashValue = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
    66. }
    67. // System.out.println("hash---: " + hash);
    68. return circle.get(hashValue);
    69. }
    70. static class HashFunction {
    71. /**
    72. * MurMurHash算法,是非加密HASH算法,性能很高,
    73. * 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免)
    74. * 等HASH算法要快很多,而且据说这个算法的碰撞率很低. http://murmurhash.googlepages.com/
    75. */
    76. int hash(Object key) {
    77. ByteBuffer buf = ByteBuffer.wrap(key.toString().getBytes());
    78. int seed = 0x1234ABCD;
    79. ByteOrder byteOrder = buf.order();
    80. buf.order(ByteOrder.LITTLE_ENDIAN);
    81. long m = 0xc6a4a7935bd1e995L;
    82. int r = 47;
    83. long h = seed ^ (buf.remaining() * m);
    84. long k;
    85. while (buf.remaining() >= 8) {
    86. k = buf.getLong();
    87. k *= m;
    88. k ^= k >>> r;
    89. k *= m;
    90. h ^= k;
    91. h *= m;
    92. }
    93. if (buf.remaining() > 0) {
    94. ByteBuffer finish = ByteBuffer.allocate( 8).order(
    95. ByteOrder.LITTLE_ENDIAN);
    96. finish.put(buf).rewind();
    97. h ^= finish.getLong();
    98. h *= m;
    99. }
    100. h ^= h >>> r;
    101. h *= m;
    102. h ^= h >>> r;
    103. buf.order(byteOrder);
    104. return ( int) h;
    105. }
    106. }
    107. }
    
     
    1. public class Test {
    2. public static void main(String[] args) {
    3. HashSet<String> serverNode = new HashSet<String>();
    4. serverNode.add( "127.1.1.1#A");
    5. serverNode.add( "127.2.2.2#B");
    6. serverNode.add( "127.3.3.3#C");
    7. serverNode.add( "127.4.4.4#D");
    8. Map<String, Integer> serverNodeMap = new HashMap<String, Integer>();
    9. ConsistentHash<String> consistentHash = new ConsistentHash<String>(
    10. new HashFunction(), 200, serverNode);
    11. int count = 50000;
    12. for ( int i = 0; i < count; i++) {
    13. String serverNodeName = consistentHash.getNode(i);
    14. // System.out.println(i + " 映射到物理节点---" + serverNodeName);
    15. if (serverNodeMap.containsKey(serverNodeName)) {
    16. serverNodeMap.put(serverNodeName,
    17. serverNodeMap.get(serverNodeName) + 1);
    18. } else {
    19. serverNodeMap.put(serverNodeName, 1);
    20. }
    21. }
    22. // System.out.println(serverNodeMap);
    23. showServer(serverNodeMap);
    24. serverNodeMap.clear();
    25. consistentHash.removeNode( "127.1.1.1#A");
    26. System.out.println( "-------------------- remove 127.1.1.1#A");
    27. for ( int i = 0; i < count; i++) {
    28. String serverNodeName = consistentHash.getNode(i);
    29. // System.out.println(i + " 映射到物理节点---" + serverNodeName);
    30. if (serverNodeMap.containsKey(serverNodeName)) {
    31. serverNodeMap.put(serverNodeName,
    32. serverNodeMap.get(serverNodeName) + 1);
    33. } else {
    34. serverNodeMap.put(serverNodeName, 1);
    35. }
    36. }
    37. showServer(serverNodeMap);
    38. serverNodeMap.clear();
    39. consistentHash.addNode( "127.5.5.5#E");
    40. System.out.println( "-------------------- add 127.5.5.5#E");
    41. for ( int i = 0; i < count; i++) {
    42. String serverNodeName = consistentHash.getNode(i);
    43. // System.out.println(i + " 映射到物理节点---" + serverNodeName);
    44. if (serverNodeMap.containsKey(serverNodeName)) {
    45. serverNodeMap.put(serverNodeName,
    46. serverNodeMap.get(serverNodeName) + 1);
    47. } else {
    48. serverNodeMap.put(serverNodeName, 1);
    49. }
    50. }
    51. showServer(serverNodeMap);
    52. serverNodeMap.clear();
    53. consistentHash.addNode( "127.6.6.6#F");
    54. System.out.println( "-------------------- add 127.6.6.6#F");
    55. count *= 2;
    56. System.out.println( "-------------------- 业务量加倍");
    57. for ( int i = 0; i < count; i++) {
    58. String serverNodeName = consistentHash.getNode(i);
    59. // System.out.println(i + " 映射到物理节点---" + serverNodeName);
    60. if (serverNodeMap.containsKey(serverNodeName)) {
    61. serverNodeMap.put(serverNodeName,
    62. serverNodeMap.get(serverNodeName) + 1);
    63. } else {
    64. serverNodeMap.put(serverNodeName, 1);
    65. }
    66. }
    67. showServer(serverNodeMap);
    68. }
    69. /**
    70. * 服务器运行状态
    71. *
    72. * @param map
    73. */
    74. public static void showServer(Map<String, Integer> map) {
    75. for (Entry<String, Integer> m : map.entrySet()) {
    76. System.out.println(m.getKey() + ", 存储数据量 " + m.getValue());
    77. }
    78. }
    79. }
    运行结果:
    
     
    1. 127.4.4.4#D, 存储数据量 13177
    2. 127.2.2.2#B, 存储数据量 11834
    3. 127.3.3.3#C, 存储数据量 12827
    4. 127.1.1.1#A, 存储数据量 12162
    5. -------------------- remove 127.1.1.1#A
    6. 127.4.4.4#D, 存储数据量 17696
    7. 127.2.2.2#B, 存储数据量 15114
    8. 127.3.3.3#C, 存储数据量 17190
    9. -------------------- add 127.5.5.5#E
    10. 127.4.4.4#D, 存储数据量 12154
    11. 127.2.2.2#B, 存储数据量 11878
    12. 127.3.3.3#C, 存储数据量 12908
    13. 127.5.5.5#E, 存储数据量 13060
    14. -------------------- add 127.6.6.6#F
    15. -------------------- 业务量加倍
    16. 127.4.4.4#D, 存储数据量 18420
    17. 127.2.2.2#B, 存储数据量 20197
    18. 127.6.6.6#F, 存储数据量 21015
    19. 127.5.5.5#E, 存储数据量 19038
    20. 127.3.3.3#C, 存储数据量 21330
    展开全文
  • 针对非局部均值(NLM)算法度量邻域块相似度不够准确的缺点,提出了一种基于差异哈希算法与汉明距离的改进NLM算法。传统算法通过欧氏距离度量邻域块之间的相似度,保持边缘和细节的能力较弱,易导致滤波后的图像模糊失真...
  • 分布式哈希算法

    2017-10-26 14:17:55
    在介绍分布式哈希算法之前,先了解下普通的Hash是如何实现的。JDK中的java.util.HashMap类就实现了一个哈希表,它的特点有:①创建哈希表(HashMap)需要先指定大小,即默认创建一个能够存储多少个元素的哈希表,它的...

    一,普通的Hash方式

    在介绍分布式哈希算法之前,先了解下普通的Hash是如何实现的。JDK中的java.util.HashMap类就实现了一个哈希表,它的特点有:①创建哈希表(HashMap)需要先指定大小,即默认创建一个能够存储多少个元素的哈希表,它的默认大小为16。

    ②当不断地向HashMap中添加元素时,HashMap越来越满,当添加的元素达到了装载因子乘以表长时,就需要扩容了。扩容时,原来已经映射到哈希表中的某个位置(桶)的元素需要重新再哈希,然后再把原来的数据复制到新的哈希表中。

    对于普通的哈希表而言,扩容的代价是很大的。因为普通的Hash计算地址方式如下:Hash(Key)%M,为了演示方便,举个极端的例子如下:

    假设哈希函数为 hash(x)=x ,哈希表的长度为5(有5个桶)

    key=6时,hash(6)%5 = 1,即Key为6的元素存储在第一个桶中

    key=7时,hash(7)%5 = 2,即Key为7的元素存储在第二个桶中

    Key=13时,hash(13)%5=3,即Key为13的元素存储在第三个桶中....

    假设现在hash表长度扩容成8,那么Key为6,7,13 的数据全都需要重新哈希。因为,

    key=6时,hash(6)%8 = 6,即Key为6的元素存储在第六个桶中

    key=7时,hash(2)%8 = 7,即Key为7的元素存储在第七个桶中

    Key=13时,hash(13)%8=5,即key为13的元素存储在第五个桶中....

    从上可以看出:扩容之后,元素的位置全变了。比如:Key为6的元素原来存储在第一个桶中,扩容之后需要存储到第6个桶中。

    因此,这是普通哈希的一个不足:扩容可能会影响到所有元素的移动。这也是为什么:为了减少扩容时元素的移动,总是将哈希表扩容成原来大小的两倍的原因。因为,有数学证明,扩容成两倍大小,使得再哈希的元素个数最少。

     

    二,一致性哈希方式

    在分布式系统中,节点的宕机、某个节点加入或者移出集群是常事。对于分布式存储而言,假设存储集群中有10台机子,如果采用Hash方式对数据分片(即将数据根据哈希函数映射到某台机器上存储),哈希函数应该是这样的:hash(file) % 10。根据上面的介绍,扩容是非常不利的,如果要添加一台机器,很多已经存储到机器上的文件都需要重新分配移动,如果文件很大,这种移动就造成网络的负载。

    因此,就出现了一种一致性哈希的方式。关于一致性哈希,可参考:一致性哈希算法学习及JAVA代码实现分析

    一致性哈希,其实就是把哈希函数可映射的空间(相当于普通哈希中桶的数目是固定的)固定下来了,比如固定为: 2n-1,并组织成环的形状

    每个机器对应着一个n位的ID,并且映射到环中。每个查询键,也是一个 n 位的ID,节点的ID和查询键对应着相同的映射空间。

    Each node choose a n-bit ID
      Intention is that they be random Though probably a hash of some fixed info IDs are arranged in a ring
    
    Each lookup key is also a n-bit ID
       I.e., the hash of the real lookup key
       Node IDs and keys occupy the same space!

     

    如下图:有四台机器映射到固定大小为2n-1的哈希环中。四台机器一共将整个环分成了四部分:(A,B)、 (B,C)、 (C,D)、 (D,A)

     

    机器A负责存储落在(D,A)范围内的数据,机器B负责存储落在(A,B)范围内的数据.....

    也就是说,对数据进行Hash时,数据的地址会落在环上的某个点上,数据就存储 该点的 顺时针方向上的那台机器上。

    相比于普通哈希方式,一致性哈希的好处就是:当添加新机器或者删除机器时,不会影响到全部数据的存储,而只是影响到这台机器上所存储的数据(落在这台机器所负责的环上的数据)。

    比如,B机器被移除了,那落在(A,B)范围内的数据 全部需要由 C机器来存储,也就只影响到落在(A,B)这个范围内的数据。

    同时,扩容也很方便,比如在(C,D)这段环上再添加一台机器E,只需要将D上的一部分数据拷贝到机器E上即可。

    那一致性哈希有没有缺点呢?当然是有的。总结一下就是:没有考虑到每台机器的异构性质,不能实现很好的负载均衡。

    举个例子:机器C的配置很高,性能很好,而机器D的配置很低。但是,可能 现实中 大部分数据由于某些特征 都哈希到(C,D)这段环上,直接就导致了机器D的存储压力很大。

    另外,一致性哈希还存在“热点”问题(hotspot)。

    比如说,由于机器D上存储了大量的数据,为了缓解下机器D的压力,在 环(C,D)段再添加一台机器E,就需要将机器D上的一部分数据拷贝到机器E上。而且只有一台机器:即机器D参与拷贝,这会引起机器D 与 机器 E之间的网络负载突然增大。机器D,就是我们所说的hotspot。

     

    三,引入虚拟节点的一致性哈希方式

    为了解决一致性哈希的一些不足,又引入了虚拟节点的概念。

    引入虚拟节点,可以有效地防止物理节点(机器)映射到哈希环中出现不均匀的情况。比如上图中的机器A、B、C都映射在环的右半边上。

    一般,虚拟节点会比物理节点多很多,并可均衡分布在环上,从而可以提高负载均衡的能力。如下图:

     

    ①如果虚拟机器与物理机器映射得好,某一台物理机器宕机后,其上的数据可由其他若干台物理机器共同分担。

    ②如果新添加一台机器,它可以对应多个不相邻 环段 上的虚拟节点,从而使得hash的数据存储得更分散。

     

    四,分布式哈希的查询过程

    当某台机器接受到查询请求时,先待查找的数据是否在本地,如果不在本地,则将查询请求转发到顺时针方向的下一个节点上。

    比如,机器N10,接受Client的查询“谁有Key80?对应的数据?”,由于Key80对应的数据存储在 机器N90 上,故故需要沿着顺时针转发:N10-->N32-->N60-->N80

    这种查询方式最坏情况下,查询的时间复杂度为O(N)

    为了提高查询效率,需要在每台机器上维护一些路由信息:即哪些Key存储在哪些节点上。比如,若机器N10上存储着“Key80的数据在机器N90上”(<key80, N90>)这样的路由信息,那机器N10立即就能把查询请求转发给机器N90,从而不需要顺时针转发了。

    那实际系统中的路由信息是如何维护的呢?Chord中实现的查询算法大致如下:

    A node’s finger table contains the IP address of a node halfway around the ID space from it, a quarter-of-the-way , and so forth in powers of two.
    A node forwards a query for key k to the node in its finger table with the highest ID less than k. 
    The power-of-two structure of the finger table ensures that the node can always forward the query at least half of the remaining ID-space distance to k. 
    As a result Chord lookups use O(log N ) messages.

     

    在Chord中,用到一个叫做“Finger Table”的机制:Entry i in the finger table of node n is the first node that succeeds or equals n + 2i

    机器1的id就是1,机器2的id就是2,机器6的id就是6。succ表示下一台机器所在的地址。比如机器1上的路由表如下:

    i        id+2i                    succ

    0       1+2^0=2             2

    1       1+2^1=3             6

    2       1+2^2=5             6

    它指出了 items 为2,3,5 所对应的数据分别在 机器2、机器6、机器6上。

    这里解释下它的查询方式如下:

    机器1本地存储着 items为1的数据;机器2本地存储着 items为2的数据;机器6本地存储着 items为3,4,5,6的数据;机器0本地存储着items为7,0 的数据。

    与此同时,机器1上,还存储着items 为2,3,5 的数据 所在的机器地址。比如,机器1知道,items为5的数据存储在机器6上面。

    比如,当机器1接收到 查询 items为7的数据在哪台机器上时,它发现 items=7 比它的路由表中的最大的items5还大,于是将查询请求转发到 items=5所对应的机器6上。

    机器6上的路由表指出:items=7的数据在机器0上,于是就找到了items=7的数据 在机器0上了。

    对于每步的查询而言,目标就是:尽可能地将查询key发送到离存储这个key最近的那台机器上。比如,上面的机器1接收到  key 为 items7 的查询,机器1上存储着 key为 2,3,5的数据,但是由于items 7 比items 2,3,5都要大,因此它判断出存储 items=5 的那台机器 距离 存储items=7的机器 更近,故把查询请求转发给 items=5 所在的那台机器(机器6)

     

     

    通过在每台机器上保存路由信息,上面的方式可以做到O(logN)的查询时间复杂度。关于其他实现的时间复杂度,可参考维基百科

    另外,比如Amazon Dynamo论文中所说的:Dynamo通过在每台机子上保存足够多路由信息,从而做到O(1)时间的查询。

    Dynamo can be characterized as a zero-hop DHT,where each node maintains
    enough routing information locally to route a request to the appropriate
    node directly

     

    五,参考资料:

    分布式Hash一致性算法

     https://en.wikipedia.org/wiki/Distributed_hash_table

    Distributed Hash Table.pdf  15­441 Spring 2004, Jeff Pang

    一致性哈希算法学习及JAVA代码实现分析

     

    原文:http://www.cnblogs.com/hapjin/p/5760463.html


    展开全文
  • 哈希表,哈希算法(C语言)

    千次阅读 2017-08-15 16:17:31
    哈希哈希表,又称散列表,常用于在海量数据中查找数据哈希表中元素是由哈希函数确定的。将数据元素的关键字key作为自变量,通过一定的函数关系H(称为哈希函数),计算出的值,即为该元素的存储地址。其优点是:运算...

    哈希表

    哈希表,又称散列表,常用于在海量数据中查找数据

    哈希表中元素是由哈希函数确定的。将数据元素的关键字key作为自变量,通过一定的函数关系H(称为哈希函数),计算出的值,即为该元素的存储地址。其优点是:运算速度快;缺点是:基于数组、难于扩展,不可遍历。

    在建立一个哈希表之前需要解决两个主要问题:

    1. 构造均匀的哈希函数
      使H(key)均匀分布在哈希表中,以提高地址计算的速度。
      构造哈希函数的方法:直接定址法,数字分析法,平法折中法,折叠法,除留余数法,随机数法等。
    2. 处理冲突
      冲突是指在哈希表中,不同的关键字值对应到同一个存储位置的现象。即存在K1≠K2,但H(K1)=H(K2)。
      再均匀的哈希函数都只能可减少冲突,但不可能避免冲突。
      发生冲突后,必须解决,即必须寻找下一个可用地址。
      解决冲突的方法:开放地址法(包括线性探测,二次探测,随机探测),再哈希法,链地址法,建立公共溢出区等。

    C语言实现

    哈希表的数据结构

    typedef struct HashNode_Struct HashNode;  
    struct HashNode_Struct  {  
        char* sKey;//键值指针
        int nValue;  //键值
        HashNode* pNext; //指向下一个哈希结构
    };   

    定义最大哈希长度及哈希数组

    #define HASH_TABLE_MAX_SIZE 10000
    HashNode* hashTable[HASH_TABLE_MAX_SIZE]; //哈希数组
    int hash_table_size;  //当前哈希长度 

    哈希表初始化函数

    void hash_table_init()  
    {  
        hash_table_size = 0;  
        memset(hashTable, 0 , sizeof(HashNode*) * HASH_TABLE_MAX_SIZE);
        //memset(void *s,int c,size_t n); 
        //将s中后n个字节换成c所代表的内容 
        //该函数是对较大结构体或数组进行清零操作的一种最快的方法 
    } 

    去符号化函数

    unsigned int hash_table_hash_str(const char* skey)  
    {  //无符号unsigned能保存2倍与有符号类型的正整型数据 
        const signed char *p = (const signed char*)skey; //常量 
        unsigned int h = *p;  
        if(h)
        {  
            for(p += 1; *p != '\0'; ++p)  
                h = (h << 5) - h + *p;  
        }  
        return h;  
    }

    插入函数

    void hash_table_insert(const char* skey, int nvalue)  
    {  
        if(hash_table_size >= HASH_TABLE_MAX_SIZE) //如果定义的哈希表长度大于等于最大长度 
        {  
            printf("内存溢出!\n");
            return;  
        }  
    
        unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;  
      //用于解决冲突,pos为哈希函数 
        HashNode* pHead = hashTable[pos];
        while(pHead)
        {  
            if(strcmp(pHead->sKey, skey) == 0)  
            {  
                printf("%s发生冲突!\n", skey);
                return ;  
            }  
            pHead = pHead->pNext;  
        }  
        //动态建立结点,初始化,分配内存空间 
        HashNode* pNewNode = (HashNode*)malloc(sizeof(HashNode));  
        memset(pNewNode, 0, sizeof(HashNode));  
        pNewNode->sKey = (char*)malloc(sizeof(char) * (strlen(skey) + 1));  
        strcpy(pNewNode->sKey, skey);  
        pNewNode->nValue = nvalue;  
    
        //指针后移 
        pNewNode->pNext = hashTable[pos];  
        hashTable[pos] = pNewNode;  
        //表长增加 
        hash_table_size++;  
    }  

    删除函数

    void hash_table_remove(const char* skey)  
    {  
        unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE; 
    
        if(hashTable[pos])  
        {  
            HashNode* pHead = hashTable[pos];  
            HashNode* pLast = NULL;  
            HashNode* pRemove = NULL;  
            while(pHead)  
            {  
                if(strcmp(skey, pHead->sKey) == 0)  
                {   //若str1==str2,则返回零;
                    //若str1>str2,则返回正数;
                    //若str1<str2,则返回负数。 
                    pRemove = pHead;//若相等,用pRemove记录  
                    break; 
                }  
                pLast = pHead;  //若不相等,不断后移 
                pHead = pHead->pNext;  
            }  
            if(pRemove)  
            {  
                if(pLast)
                    pLast->pNext = pRemove->pNext;//实现删除1 
                else  
                    hashTable[pos] = NULL;//实现删除2
    
                free(pRemove->sKey);  
                free(pRemove);  
            }  
        }  
    }  

    查找函数

    HashNode* hash_table_lookup(const char* skey)  
    {  
        unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;  
    
        if(hashTable[pos])  
        {  
            HashNode* pHead = hashTable[pos];  
            while(pHead)  
            {  
                if(strcmp(skey, pHead->sKey) == 0)  
                    return pHead;//查找成功 
    
                pHead = pHead->pNext;  
            }  
        }  
        return NULL;  
    }  

    打印哈希表函数

    void hash_table_print()  
    { 
        int i;  
        for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)  
            if(hashTable[i])//表不空 
            {  
                HashNode* pHead = hashTable[i];  
                printf("%d=>", i);  
                while(pHead)  
                {  
                    printf("%s:%d  ", pHead->sKey, pHead->nValue);  
                    pHead = pHead->pNext;  
                }  
                printf("\n");  
            }  
    }  

    释放内存函数

    void hash_table_release()  
    {  
        int i;  
        for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)  
        {  
            if(hashTable[i])  
            {  
                HashNode* pHead = hashTable[i];  
                while(pHead)  
                {  
                    HashNode* pTemp = pHead;  
                    pHead = pHead->pNext;  
                    if(pTemp)  
                    {  
                        free(pTemp->sKey);  
                        free(pTemp);  
                    }  
                    //逐个释放 
                }  
            }  
        }  
    }  

    随机生成函数

    #define MAX_STR_LEN 20  
    #define MIN_STR_LEN 10  
    void rand_str(char r[])  
    {  
        int i;  
        int len = MIN_STR_LEN + rand() % (MAX_STR_LEN - MIN_STR_LEN);  
        for(i = 0; i < len - 1; ++i)  
            r[i] = 'a' + rand() % ( 'z' - 'a');  
        r[len - 1] = '\0';  
    }

    具体代码如下:

    #include <stdio.h>  
    #include <stdlib.h>  
    #include <string.h>  
    #include <time.h>  
    
    #define HASH_TABLE_MAX_SIZE 10000  
    typedef struct HashNode_Struct HashNode;  
    struct HashNode_Struct  {  
        char* sKey;  
        int nValue;  
        HashNode* pNext;  
    };  //哈希表数据结构 
    
    HashNode* hashTable[HASH_TABLE_MAX_SIZE]; 
    int hash_table_size;  //哈希表中键值对的数量 
    
    //初始化哈希表 
    void hash_table_init()  
    {  
        hash_table_size = 0;  
        memset(hashTable, 0, sizeof(HashNode*) * HASH_TABLE_MAX_SIZE);
        //memset(void *s,int c,size_t n); 
        //将s中后n个字节换成c所代表的内容 
        //该函数是对较大结构体或数组进行清零操作的一种最快的方法 
    }  
    
    
    //去符号化哈希表  
    unsigned int hash_table_hash_str(const char* skey)  
    {  //无符号unsigned能保存2倍与有符号类型的正整型数据 
        const signed char *p = (const signed char*)skey; //常量 
        unsigned int h = *p;  
        if(h)
        {  
            for(p += 1; *p != '\0'; ++p)  
                h = (h << 5) - h + *p;  
        }  
        return h;  
    }
    //插入 
    void hash_table_insert(const char* skey, int nvalue)  
    {  
        if(hash_table_size >= HASH_TABLE_MAX_SIZE) //如果定义的哈希表长度大于等于最大长度 
        {  
            printf("内存溢出!\n");
            return;  
        }  
    
        unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;  
      //用于解决冲突,pos为哈希函数 
        HashNode* pHead = hashTable[pos];
        while(pHead)
        {  
            if(strcmp(pHead->sKey, skey) == 0)  
            {  
                printf("%s发生冲突!\n", skey);
                return ;  
            }  
            pHead = pHead->pNext;  
        }  
        //动态建立结点,初始化,分配内存空间 
        HashNode* pNewNode = (HashNode*)malloc(sizeof(HashNode));  
        memset(pNewNode, 0, sizeof(HashNode));  
        pNewNode->sKey = (char*)malloc(sizeof(char) * (strlen(skey) + 1));  
        strcpy(pNewNode->sKey, skey);  
        pNewNode->nValue = nvalue;  
    
        //指针后移 
        pNewNode->pNext = hashTable[pos];  
        hashTable[pos] = pNewNode;  
        //表长增加 
        hash_table_size++;  
    }  
    //删除 
    void hash_table_remove(const char* skey)  
    {  
        unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE; 
    
        if(hashTable[pos])  
        {  
            HashNode* pHead = hashTable[pos];  
            HashNode* pLast = NULL;  
            HashNode* pRemove = NULL;  
            while(pHead)  
            {  
                if(strcmp(skey, pHead->sKey) == 0)  
                {   //若str1==str2,则返回零;
                    //若str1>str2,则返回正数;
                    //若str1<str2,则返回负数。 
                    pRemove = pHead;//若相等,用pRemove记录  
                    break; 
                }  
                pLast = pHead;  //若不相等,不断后移 
                pHead = pHead->pNext;  
            }  
            if(pRemove)  
            {  
                if(pLast)
                    pLast->pNext = pRemove->pNext;//实现删除1 
                else  
                    hashTable[pos] = NULL;//实现删除2
    
                free(pRemove->sKey);  
                free(pRemove);  
            }  
        }  
    }  
    
    //查找 
    HashNode* hash_table_lookup(const char* skey)  
    {  
        unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;  
    
        if(hashTable[pos])  
        {  
            HashNode* pHead = hashTable[pos];  
            while(pHead)  
            {  
                if(strcmp(skey, pHead->sKey) == 0)  
                    return pHead;//查找成功 
    
                pHead = pHead->pNext;  
            }  
        }  
        return NULL;  
    }  
    
    //打印 
    void hash_table_print()  
    { 
        int i;  
        for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)  
            if(hashTable[i])//表不空 
            {  
                HashNode* pHead = hashTable[i];  
                printf("%d=>", i);  
                while(pHead)  
                {  
                    printf("%s:%d  ", pHead->sKey, pHead->nValue);  
                    pHead = pHead->pNext;  
                }  
                printf("\n");  
            }  
    }  
    
    //释放内存 
    void hash_table_release()  
    {  
        int i;  
        for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)  
        {  
            if(hashTable[i])  
            {  
                HashNode* pHead = hashTable[i];  
                while(pHead)  
                {  
                    HashNode* pTemp = pHead;  
                    pHead = pHead->pNext;  
                    if(pTemp)  
                    {  
                        free(pTemp->sKey);  
                        free(pTemp);  
                    }  
                    //逐个释放 
                }  
            }  
        }  
    }  
    
    
    /* ============================主测试函数============================*/  
    #define MAX_STR_LEN 20  
    #define MIN_STR_LEN 10  
    void rand_str(char r[])  
    {  
        int i;  
        int len = MIN_STR_LEN + rand() % (MAX_STR_LEN - MIN_STR_LEN);  
        for(i = 0; i < len - 1; ++i)  
            r[i] = 'a' + rand() % ( 'z' - 'a');  
        r[len - 1] = '\0';  
    }  
    
    int main(int argc, char** argv)  
    {  
        srand(time(NULL));  
        hash_table_init();     
        int n = 10;  
        char str[MAX_STR_LEN + 1]; 
        const char *key1 = "aaa111";  
        const char *key2 = "bbb222";  
        const char *key3 = "ccc333";
    
        while(n--)  
        {  
            rand_str(str);  
            hash_table_insert(str, n);  
        }
        printf("插入前\n");
        hash_table_print(); 
    
        hash_table_insert(key1, 1);  
        hash_table_insert(key2, 2);  
        hash_table_insert(key3, 2);   
    
        printf("插入后\n");
        hash_table_print();  
    
        HashNode* pNode = hash_table_lookup(key1);  
        printf("查找结果:%d\n", pNode->nValue);  
        pNode = hash_table_lookup(key2);  
        printf("查找结果:%d\n", pNode->nValue);
    
        printf("删除之前:\n");  
        hash_table_print();  
        hash_table_remove(key3);  
        printf("删除之后:\n");  
        hash_table_print();  
    
        hash_table_release();  
    
        return 0;  
    }  
    展开全文
  • 哈希算法C语言实现

    2016-02-17 12:56:54
    哈希算法C语言实现
  • locality-sensitive hashing(局部敏感哈希),实现高位数据搜索平台
  • 该压缩包包含编译方式,示例代码,只需拍两张图片即可比较,比较打印输出值小于10,即为相似图片。使用改代码的用户linux系统必须先安装opencv环境.
  • 哈希算法 哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的...
  • 区块链100篇之哈希算法

    千次阅读 2019-05-07 18:07:56
    哈希算法 维基百科的定义:是一种从任何一种数据中创建小的数字“指纹”的方法。简单的说就是将任意的数据通过一个函数转化成一个有着固定长度的数据串,这个数据串就叫哈希值。
  • 这是几种经典的Hash算法的实现(源代码),里面源代码和文字解说都有
  • 哈希火炬 一些Deep Hash算法基线的实现。 怎么跑 我的环境是 python==3.7.0 torchvision==0.5.0 pytorch==1.4.0 您可以轻松地训练和测试任何算法 pyhon DSH.py pyhon DPSH.py pyhon DHN.py pyhon DSDH.py ...
  • 运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
  • 冒泡排序算法的基本原理就是比较相邻两个数字的大小。将两个数中比较大的那个数交换到靠后的位置,不断交换下去就可以将最大的那两个数放到队列的尾部。然后重头再次交换)(交换list.lenght-1次),直到将数列排成有序...
  • 哈希算法应用

    千次阅读 2019-06-13 20:49:02
    哈希算法 还记得 2011 年 CSDN 的“脱库”事件吗?当时,CSDN 网站被黑客攻击,超过 600 万用户的注册邮箱和密码明文被泄露,很多网友对 CSDN 明文保存用户密码行为产生了不满。如果你是 CSDN 的一名工程师,你会...
  • 哈希算法

    2020-08-17 15:01:34
    哈希算法(Hash)又称摘要算法(Digest),它的作用是:对任意一组输入数据进行计算,得到一个对固定长度额输出摘要。 哈希算法最重要的特点就是: 相同的输入一定得到相同的输出; 不同的输入大概率得到不同的输出。 ...
  • 哈希算法C++实现

    2015-02-26 11:27:31
    哈希算法C++实现 SGI 哈希表是一个线性存储结构,其关键是哈希函数与哈希算法
  • 摘 要: 哈希算法被广泛用于数据完整性检测.在物联网数据完整性检测中,现有标准哈希算法的软硬件开销仍需进一步降低.从低功耗AVR 微处理器的特点出发,通过基于字节的压缩函数变换操作和基于布尔运算特点的函数优化...
  • 复制代码 代码如下:APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, apr_ssize_t *klen){ unsigned int hash = 0; const unsigned char *key = (const unsigned char *)char_key;...
  • Kornblum提出了模糊哈希算法。模糊哈希的主要原理是,使用一个弱哈希计算文件局部内容,在特定条件下对文件进行分片,然后使用一个强哈希对文件每片计算哈希值,取这些值的一部分并连接起来,与分片条件一起构成一个...
  • 我在电信行业和信息安全行业里的工作经历发现,目前网络上的哈希算法都在查询速度上远远无法满足日趋增长的网络大数据要求。因此产生了自己写算法的想法。 现在我把自己的算法初稿发布出来,用我在一家信息安全的...
  • 在浏览器的图片搜索中,用户可以上传一张图片,浏览器显示因特网中与此图片相同或者相似的图,实现这种功能的关键技术叫做"感知哈希算法"(Perceptual Hash Algorithm), 意思是为图片生成一个指纹(字符串格式), 两张...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 139,883
精华内容 55,953
关键字:

哈希算法代码