一致性hash算法 java代码实现与测试

xiaoxiao2021-02-28  88

转载:http://blog.csdn.net/pcceo1/article/details/51493934

写了一个一致性hash的Java实现代码,算法是用别人的,据说很好,然后自己做了一个测试,用线程池起了1000个线程,每个线程hash10000次,模拟一万次数据hash,并将测试结果上传。

[java]  view plain  copy /**   * 一致性hash代码   *    * @author shiguiming   *   * @param <T>   */   public class Shared<T> {          // 真实节点对应的虚拟节点数量       private int length = 100;       // 虚拟节点信息       private TreeMap<Long, T> virtualNodes;       // 真实节点信息       private List<T> realNodes;          public Shared(List<T> realNodes) {           this.realNodes = realNodes;           init();       }          public List<T> getReal() {           return realNodes;       }          /**       * 初始化虚拟节点       */       private void init() {           virtualNodes = new TreeMap<Long, T>();           for (int i = 0; i < realNodes.size(); i++) {               for (int j = 0; j < length; j++) {                   virtualNodes.put(hash("aa" + i + j), realNodes.get(i));               }           }       }          /**       * 获取一个结点       *        * @param key       * @return       */       @SuppressWarnings("unchecked")       public T getNode(String key) {           Long hashedKey = hash(key);           // TODO judge null           Entry en = virtualNodes.ceilingEntry(hashedKey);           if (en == null) {               return (T) virtualNodes.firstEntry().getValue();           }           return (T) en.getValue();       }          /**       * MurMurHash算法,是非加密HASH算法,性能很高,       * 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免)       * 等HASH算法要快很多,而且据说这个算法的碰撞率很低. http://murmurhash.googlepages.com/       */       private Long hash(String key) {           ByteBuffer buf = ByteBuffer.wrap(key.getBytes());           int seed = 0x1234ABCD;              ByteOrder byteOrder = buf.order();           buf.order(ByteOrder.LITTLE_ENDIAN);              long m = 0xc6a4a7935bd1e995L;           int r = 47;              long h = seed ^ (buf.remaining() * m);              long k;           while (buf.remaining() >= 8) {               k = buf.getLong();                  k *= m;               k ^= k >>> r;               k *= m;                  h ^= k;               h *= m;           }              if (buf.remaining() > 0) {               ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);               // for big-endian version, do this first:               // finish.position(8-buf.remaining());               finish.put(buf).rewind();               h ^= finish.getLong();               h *= m;           }              h ^= h >>> r;           h *= m;           h ^= h >>> r;              buf.order(byteOrder);           return h;       }          /**       * 测试内部类       *        * @author shiguiming       *       */       static public class Node {           private int name;           private int count = 0;              public Node() {              }              public Node(int i) {               this.name = i;           }              public int getName() {               return name;           }              public void setName(int name) {               this.name = name;           }              public int getCount() {               return count;           }              // 同步方法,防止并发           synchronized public void inc() {               count++;           }          }          /**       * 测试方法       *        * @param args       * @throws InterruptedException       */       public static void main(String[] args) throws InterruptedException {           List<Node> ndList = new ArrayList<Node>();           int i = 0;           while (true) {               ndList.add(new Node(i));               if (i++ == 9)                   break;           }              final Shared<Node> sh = new Shared<Node>(ndList);           ExecutorService es = Executors.newCachedThreadPool();           final CountDownLatch cdl = new CountDownLatch(1000);           // 1000个线程           for (int j = 0; j < 1000; j++) {               es.execute(new Runnable() {                      @Override                   public void run() {                       // Random rd = new Random(1100);                       for (int k = 0; k < 10000; k++) {                           sh.getNode(String.valueOf(Math.random())).inc();                       }                       cdl.countDown();                   }               });           }              // 等待所有线程结束           cdl.await();           List<Node> nodeList = sh.getReal();           for (Node node : nodeList) {               System.out.println("node" + node.getName() + ":" + node.getCount());           }          }   }  

测试结果:

一共10,000,000次 hash,基本算是较均匀投递到10个节点,有什么问题大家交流~

转载请注明原文地址: https://www.6miu.com/read-28123.html

最新回复(0)