【策略】一致性Hash算法（Hash环）的java代码实现-白红宇

【一】一致性hash算法，基本实现分布平衡。

1 package org.ehking.quartz.curator; 2  3 import java.util.SortedMap; 4 import java.util.TreeMap; 5  6 public class ConsistentHashingWithoutVirtualNode { 7     /** 8            * 待添加入Hash环的服务器列表 9           */10          private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",11                 "192.168.0.3:111", "192.168.0.4:111"};12      13        /**14       * key表示服务器的hash值，value表示服务器的名称15          */16          private static SortedMap
      
        sortedMap = 17              new TreeMap
       
        ();18         19      /**20       * 程序初始化，将所有的服务器放入sortedMap中21      */22      static23   {24       for (int i = 0; i < servers.length; i++)25        {26           int hash = getHash(servers[i]);27           System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);28            sortedMap.put(hash, servers[i]);29        }30         System.out.println();31     }32      33      /**34       * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别 35      */36      private static int getHash(String str)37      {38          final int p = 16777619;39          int hash = (int)2166136261L;40          for (int i = 0; i < str.length(); i++)41         hash = (hash ^ str.charAt(i)) * p;42         hash += hash << 13;43        hash ^= hash >> 7;44        hash += hash << 3;45       hash ^= hash >> 17;46         hash += hash << 5;47          48         // 如果算出来的值为负数则取其绝对值49         if (hash < 0)50             hash = Math.abs(hash);51          return hash;52      }53    54      /**55       * 得到应当路由到的结点56       */57      private static String getServer(String node)58      {59          // 得到带路由的结点的Hash值60          int hash = getHash(node);61         // 得到大于该Hash值的所有Map62          SortedMap
        
          subMap = 63                  sortedMap.tailMap(hash);64          // 第一个Key就是顺时针过去离node最近的那个结点65         Integer i = subMap.firstKey();66          // 返回对应的服务器名称67        return subMap.get(i);68      }69     70      public static void main(String[] args)71     {72          String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};73        for (int i = 0; i < nodes.length; i++)74            System.out.println("[" + nodes[i] + "]的hash值为" + 75                     getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");76     }77 }

View Code

【二】借助虚拟节点，实现分布平衡的hash算法

1 package org.ehking.quartz.curator;  2   3 import java.util.ArrayList;  4 import java.util.HashMap;  5 import java.util.LinkedList;  6 import java.util.List;  7 import java.util.Set;  8 import java.util.SortedMap;  9 import java.util.TreeMap; 10 import java.util.UUID; 11  12 public class ConsistentHashingWithVirtualNode { 13     /** 14      * 待添加入Hash环的服务器列表 15       */ 16     private static String[] servers = { "192.168.0.0:111","192.168.0.1:111", "192.168.0.2:111"}; 17     18    /** 19       * 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好 20      */ 21    private static List
      
        realNodes = new LinkedList
       
        (); 22    /** 23     * 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称 24     */ 25    private static SortedMap
        
          virtualNodes =  26            new TreeMap
         
          (); 27      28     /** 29       * 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点 30     */ 31      private static final int VIRTUAL_NODES = 1000; 32     33   static 34   { 35         // 先把原始的服务器添加到真实结点列表中 36          for (int i = 0; i < servers.length; i++) 37              realNodes.add(servers[i]); 38           39         // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高 40          for (String str : realNodes) 41          { 42              for (int i = 0; i < VIRTUAL_NODES; i++) 43              { 44                String virtualNodeName = str + "&&VN" + String.valueOf(i); 45                  int hash = getHash(virtualNodeName); 46                  System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash); 47                 virtualNodes.put(hash, virtualNodeName); 48             } 49          } 50          System.out.println(); 51    } 52     53      /** 54       * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别  55       */ 56      private static int getHash(String str) 57      { 58          final int p = 16777619; 59         int hash = (int)2166136261L; 60         for (int i = 0; i < str.length(); i++) 61             hash = (hash ^ str.charAt(i)) * p; 62           hash += hash << 13; 63         hash ^= hash >> 7; 64         hash += hash << 3; 65         hash ^= hash >> 17; 66         hash += hash << 5; 67         68         // 如果算出来的值为负数则取其绝对值 69          if (hash < 0) 70              hash = Math.abs(hash); 71          return hash; 72      } 73      74      /** 75       * 得到应当路由到的结点 76       */ 77      private static String getServer(String node) 78      { 79          // 得到带路由的结点的Hash值 80          int hash = getHash(node); 81          // 得到大于该Hash值的所有Map 82          SortedMap
          
            subMap =  83                  virtualNodes.tailMap(hash); 84          Integer i=null; 85          String virtualNode = null; 86          if(subMap==null||subMap.size()==0){ 87              i=virtualNodes.firstKey(); 88              virtualNode=virtualNodes.get(i); 89          }else{ 90               i = subMap.firstKey(); 91               virtualNode= subMap.get(i); 92          } 93          // 第一个Key就是顺时针过去离node最近的那个结点 94         95          // 返回对应的虚拟节点名称，这里字符串稍微截取一下 96          return virtualNode.substring(0, virtualNode.indexOf("&&")); 97      } 98       99      public static void main(String[] args)100      {101         102         HashMap
           
             map=new HashMap
            
             (); 103 List
             
               id=new ArrayList
              
               ();104 for(int i=0;i<1000;i++){105 id.add(UUID.randomUUID().toString().replace("-", ""));106 //id.add("adasfdsafdsgfdsagdsafdsafdsaf"+i);107 } 108 for (int i = 0; i < id.size(); i++){109 String aString=getServer(id.get(i));110 Integer aInteger=map.get(aString);111 if(aInteger==null){112 map.put(aString,1);113 }else{114 map.put(aString, aInteger+1);115 }116 }117 Set
               
                 set= map.keySet();118 for(String a:set){119 System.out.println("节点【"+a+"】分配到元素个数为==>"+map.get(a));120 }121 }122 }

View Code