`
kuyuyingzi
  • 浏览: 52608 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

一致性Hash算法介绍及简单实现

 
阅读更多
一致性 hash 算法( consistent hashing )介绍:
http://blog.csdn.net/sparkliang/archive/2010/02/02/5279393.aspx

一致性 hash 算法简单实现:
hashcode产生接口
Java代码收藏代码
  1. packageconsistentHash;
  2. /**
  3. *@authorzhengtian
  4. *
  5. *@date2012-4-20下午02:51:39
  6. */
  7. @SuppressWarnings("all")
  8. publicinterfaceHashFunction{
  9. publicinthash(Objectkey);
  10. }

一致性 hash循环圈
Java代码收藏代码
  1. packageconsistentHash;
  2. importjava.util.Collection;
  3. importjava.util.SortedMap;
  4. importjava.util.TreeMap;
  5. /**
  6. *@authorzhengtian
  7. *
  8. *@date2012-4-20下午02:50:26
  9. */
  10. @SuppressWarnings("all")
  11. publicclassConsistentHash<T>{
  12. //hashcode生成接口
  13. privatefinalHashFunctionhashFunction;
  14. //需要复制的虚拟节点个数
  15. privatefinalintnumberOfReplicas;
  16. //hashcode循环圈
  17. privatefinalSortedMap<Integer,T>circle=newTreeMap<Integer,T>();
  18. /**
  19. *构造函数
  20. *
  21. *@paramhashFunction
  22. *@paramnumberOfReplicas
  23. *@paramnodes
  24. *真实节点数
  25. */
  26. publicConsistentHash(HashFunctionhashFunction,intnumberOfReplicas,Collection<T>nodes){
  27. this.hashFunction=hashFunction;
  28. this.numberOfReplicas=numberOfReplicas;
  29. for(Tnode:nodes){
  30. add(node);
  31. }
  32. }
  33. /**
  34. *增加节点
  35. *
  36. *@paramnode
  37. */
  38. publicvoidadd(Tnode){
  39. for(inti=0;i<numberOfReplicas;i++){
  40. circle.put(hashFunction.hash(node.toString()+i),node);
  41. }
  42. }
  43. /**
  44. *移除节点
  45. *
  46. *@paramnode
  47. */
  48. publicvoidremove(Tnode){
  49. for(inti=0;i<numberOfReplicas;i++){
  50. circle.remove(hashFunction.hash(node.toString()+i));
  51. }
  52. }
  53. /**
  54. *根据对象的key得到顺时针方向的第一个node
  55. *
  56. *@paramkey
  57. *@return
  58. */
  59. publicTget(Objectkey){
  60. if(circle.isEmpty()){
  61. returnnull;
  62. }
  63. inthash=hashFunction.hash(key);
  64. if(!circle.containsKey(hash)){
  65. //得到circle中hashcode值大于等于hash的部分映射
  66. SortedMap<Integer,T>tailMap=circle.tailMap(hash);
  67. hash=tailMap.isEmpty()?circle.firstKey():tailMap.firstKey();
  68. }
  69. returncircle.get(hash);
  70. }
  71. publicstaticvoidmain(String[]args){
  72. SortedMap<Integer,String>tailMap=newTreeMap<Integer,String>();
  73. tailMap.put(1,"111");
  74. tailMap.put(3,"333");
  75. tailMap.put(4,"444");
  76. tailMap.put(2,"222");
  77. System.out.println(tailMap.firstKey());
  78. System.out.println(tailMap.get(tailMap.firstKey()));
  79. }
  80. }
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics