一致性hash算法java

㈠ java里equals和hashCode之间什么关系

equals与hashcode的关系是：

两个对象在equals相等的情况下，hashcode有可能相等也有可能不相等，

而两个对象在hashcode不相等的情况下，equals也必定不相等。

理解equals的应用：它是用于用户在进行对比的时候，这个时候对比的是内容是否相等

理解hashcode的应用：例如set集合，它的不可重复，进行对比的便是hashcode是否相等，因此set集合实现了不可重复。

如果根据 equals(Object) 方法，两个对象是相等的，那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。

即使两个hashCode()返回的结果相等，两个对象的equals方法也不一定相等。

(1)一致性hash算法java扩展阅读：

equals：

电脑编程语言，被用来检测两个对象是否相等，即两个对象的内容是否相等。

equals 方法（是String类从它的超类Object中继承的）

==用于比较引用和比较基本数据类型时具有不同的功能：

比较基本数据类型，如果两个值相同，则结果为true

而在比较引用时，如果引用指向内存中的同一对象，结果为true

hashCode：

是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。

支持此方法是为了提高哈希表（例如 java.util.Hashtable 提供的哈希表）的性能。

HashMap对象是根据其Key的hashCode来获取对应的Value。

在重写父类的equals方法时，也重写hashcode方法，使相等的两个对象获取的HashCode也相等。

这样当此对象做Map类中的Key时，两个equals为true的对象其获取的value都是同一个，比较符合实际。

㈡ java怎么通过hash算法比对对象是否修改

java使用哈希值判断通过hash算法比对对象是否修改。根据查询相关公开信息显示，使用string.GetHashCode()方法，将用户对象序列化成字符串，用string.GetHashCode()方法，获取字符串的哈希值，当用户点击保存按钮保存数据时即可判断对象是否修改。

㈢ java去公司工作用到的是哪方面的知识

小公司做小项目一般都用SSH+jsp大公司做项目都是根据不同的项目 采取不同的框架技术,比如银行大部分都用 EJB等

第一：先学习Java的核心库（JavaSE）

JavaSE的内容包括：环境搭建、基础语法、面向对象、数组、集合、常用类、IO流、反射机制、网络编程……..

第二：MySQL数据库

搞定一门数据库相关的课程，例如：MySQL、Oracle，搞定一个就可以了，目前互联网公司，例如：京东、阿里等，他们都在使用MySQL，所以建议大家学习MySQL数据库，小巧轻盈，免费，由于互联网公司的项目访问量比较大，所以一般会搭建数据库的集群，可以一个数据库不够，所以需要搭建数据库集群，为了应付高并发。（搭建的比较多的时候，免费就很重要了。）

第三：WEB前端

以后从事Java开发，从事JavaEE开发，主要开发的系统结构是B/S结构的，B指的是Browser，S指的是Server。要开发这种系统，B端要会，S端也要精通。WEB前端的学习就是学习B端技术。包括：HTML 、CSS、JavaScript（JS）、jQuery框架（底层对JS进行了封装）…

第四：WEB后端（JavaWEB）

WEB后端其实可以是很多种不同的编程语言，例如：php、C、C++、Java，他们都可以进行WEB后端的开发，我们既然选择了比较火爆的Java，那么我们学习的后端一定是基于Java语言实现的，包括：Servlet、Filter、Jsp、EL、JSTL、MVC架构模式、数据库连接池（阿里巴巴的Druid连接池）、代理模式（动态代理）。另外后端学习了之后，还要学习一个异步编程技术AJAX。（完成网页的局部刷新，AJAX其实不属于后端，是前端浏览器上的程序。）

学习到这里为止，表示Java基本/基础的技术已经学完了。但是这些最基层的技术在实际的开发中不会使用的，一般为了开发效率，都会使用大量的提前封装好的框架。

第五：最好能够停留下来，做一个项目。

这个项目最好能将之前所学全部串起来。（对以前的知识点进行巩固。）

这个项目最好是基于：Servlet + Jsp+AJAX+jQuery+MySQL….

在这个项目的开发过程中：大家一定要记住，目前比较好的项目自动构建工具：Maven是一定要精通的。还有一个就是团队协作开发：Git/SVN是一定要会用的。（目前使用Git比较多一些。）

第六：学习高级框架

Spring、SpringMVC、MyBatis（持久层框架，这个框架互联网公司使用比较多，因为互联网项目需要进行SQL优化，MyBatis的SQL优化很方便，所以大部分都是使用MyBatis）

Struts2（很少使用了，使用这个的肯定是很老的项目）、Hibernate（传统企业，还有政府等可能会使用Hibernate。）

SpringBoot（新项目大部分使用的都是boot了。所以在项目中遇到还在使用SSM的一般都是遗留项目。）

当你走到这里之后，基本上你可以出山了。（去找工作，8K的薪资应该问题不大，但前提是你学的好。学习的深度够了，广度够了。）

第七：最好能有一个大型项目是使用框架来完成的。

SpringBoot做一个项目。

Spring SpringMVC MyBatis做一个项目。

这个项目最好是找几个人搭伙做一下。体验一下团队协作。（尤其是使用一些协作的工具。怎么沟通，怎么写日报，怎么开会，怎么使用Git，等等….）

第八：如果你的薪资想达到15K的话，你可能需要还要学习一些分布式相关的一些技术。

能够应付高并发的一些技术，例如：分布式框架Dubbo、SpringCloud、MQ、Nginx、Redis…..

java的知识体系构架

....祝 工作顺心 哈哈

㈣ 关于Java中的对象的哈希值何时相等

1.标准的基本类型只要值相等，哈希值就相同；
Integer a=10;
Integer b=10;
那么a和b的哈希值就相同。类似的还有Short、Long、Byte、Boolean、String等等

2.同一个对象，与何时运行该程序无关；
哈希值算法中，对象的内存地址不参与运算。因此只要是同一个对象，那么该对象的哈希值就不会改变。

3.关于容器的哈希值
java中常用的容器有List、Map、Set。那么它们的哈希值又有什么特点呢？
假设有如下两个List：
List<String> list1= new ArrayList<String>();
list1.add("item1");
list1.add("item2");
List<String> list2= new ArrayList<String>();
list2.add("item2");
list2.add("item1");
这两个List的哈希值是不一样的。对于List来讲，每一个元素都有它的顺序。如果被添加的顺序不同，最后的哈希值必然不同。

假如有如下两个Map：
Map<String, String> map1= new HashMap<String, String>();
map1.put("a", "1");
map1.put("b", "2");
map1.put("c", "3");
Map<String, String> map2= new HashMap<String, String>();
map2.put("b", "2");
map2.put("a", "1");
map2.put("c", "3");
这两个Map虽然元素添加的顺序不一样，但是每一个元素的Key-Value值一样。Map是一种无序的存储结构，因此它的哈希值与元素添加顺序无关，这两个Map的哈希值相同。

假如有如下两个Set：
Set<String> set1= new HashSet<String>();
set1.add("a");
set1.add("b");
set1.add("c");
Set<String> set2= new HashSet<String>();
set2.add("b");
set2.add("a");
set2.add("c");
类似的，由于Set也是一种无序的存储结构，两个Set虽然添加元素的顺序不一样，但是总体来说元素的个数和内容是一样的。因此这两个Set的哈希值也相同。

其实，Set的实现是基于Map的。我们可以看到，如果将Set中的元素当做Map中的Key，把Map中的value始终设置为null，那么它就变成了一个Set。
Set<String> set1= new HashSet<String>();
set1.add("a");
set1.add("b");
set1.add("c");
Map<String, String> map1= new HashMap<String, String>();
map1.put("a", null);
map1.put("b", null);
map1.put("c", null);
通过实验我最后得到了印证，set1与map1的哈希值相同。

㈤ java分布式架构有哪些技术

既然是分布式系统，系统间通信的技术就不可避免的要掌握。

首先，我们必须掌握一些基本知识，例如网络通信协议（例如TCP / UDP等），网络IO（Blocking-IO，NonBlocking-IO，Asyn-IO），网卡（多队列等）。 了解有关连接重用，序列化/反序列化，RPC，负载平衡等的信息。

在学习了这些基本知识之后，您基本上可以在分布式系统中编写一个简单的通信模块，但这实际上还远远不够。 现在，您已经进入了分布式字段，您已经对规模有很多要求。 这意味着需要一种通信程序，该程序可以支持大量连接，高并发性和低资源消耗。

大量的连接通常会有两种方式：

大量client连一个server

当前在NonBlocking-IO非常成熟的情况下，支持大量客户端的服务器并不难编写，但是在大规模且通常是长连接的情况下，有一点需要特别注意 ，即服务器挂起时不可能所有客户端都在某个时间点启动重新连接。 那基本上是一场灾难。 我见过一些没有经验的类似案例。 客户端规模扩大后，服务器基本上会在重新启动后立即刷新。 大量传入连接中断（当然，服务器的积压队列首先应设置为稍大一些）。 可以使用的通常方法是在客户端重新连接之前睡眠一段随机的时间。 另外，重连间隔采用避让算法。

一个client连大量的server

有些场景也会出现需要连大量server的现象，在这种情况下，同样要注意的也是不要并发同时去建所有的连接，而是在能力范围内分批去建。

除了建连接外，另外还要注意的地方是并发发送请求也同样，一定要做好限流，否则很容易会因为一些点慢导致内存爆掉。

这些问题在技术风险上得考虑进去，并在设计和代码实现上体现，否则一旦随着规模上去了，问题一时半会还真不太好解。

高并发这个点需要掌握CAS、常见的lock-free算法、读写锁、线程相关知识（例如线程交互、线程池）等，通信层面的高并发在NonBlocking-IO的情况下，最重要的是要注意在整体设计和代码实现上尽量减少对io线程池的时间占用。

低资源消耗这点的话NonBlocking-IO本身基本已经做到。

伸缩性

分布式系统基本上意味着规模不小。 对于此类系统，在设计时必须考虑可伸缩性。 在体系结构图上绘制的任何点，如果请求量或数据量继续增加，该怎么办？ 通过添加机器来解决。 当然，此过程不需要考虑无限的情况。 如果您有经验的建筑师，从相对较小的规模到非常大型的范围，那么优势显然并不小，而且它们也将越来越稀缺。 。

横向可扩展性（Scale Out）是指通过增加服务器数量来提高群集的整体性能。 垂直可伸缩性（Scale Up）是指提高每台服务器的性能以提高集群的整体性能。 纵向可扩展性的上限非常明显，而分布式系统则强调水平可伸缩性。

分布式系统应用服务最好做成无状态的

应用服务的状态是指运行时程序因为处理服务请求而存在内存的数据。分布式应用服务最好是设计成无状态。因为如果应用程序是有状态的，那么一旦服务器宕机就会使得应用服务程序受影响而挂掉，那存在内存的数据也就丢失了，这显然不是高可靠的服务。把应用服务设计成无状态的，让程序把需要保存的数据都保存在专门的存储上(eg. 数据库)，这样应用服务程序可以任意重启而不丢失数据，方便分布式系统在服务器宕机后恢复应用服务。

伸缩性的问题围绕着以下两种场景在解决：

无状态场景

对于无状态场景，要实现随量增长而加机器支撑会比较简单，这种情况下只用解决节点发现的问题，通常只要基于负载均衡就可以搞定，硬件或软件方式都有；

无状态场景通常会把很多状态放在db，当量到一定阶段后会需要引入服务化，去缓解对db连接数太多的情况。

有状态场景

所谓状态其实就是数据，通常采用Sharding来实现伸缩性，Sharding有多种的实现方式，常见的有这么一些：

2.1 规则Sharding

基于一定规则把状态数据进行Sharding，例如分库分表很多时候采用的就是这样的，这种方式支持了伸缩性，但通常也带来了很复杂的管理、状态数据搬迁，甚至业务功能很难实现的问题，例如全局join，跨表事务等。

2.2 一致性Hash

一致性Hash方案会使得加机器代价更低一些，另外就是压力可以更为均衡，例如分布式cache经常采用，和规则Sharding带来的问题基本一样。

2.3 Auto Sharding

Auto Sharding的好处是基本上不用管数据搬迁，而且随着量上涨加机器就OK，但通常Auto Sharding的情况下对如何使用会有比较高的要求，而这个通常也就会造成一些限制，这种方案例如HBase。

2.4 Copy

Copy这种常见于读远多于写的情况，实现起来又会有最终一致的方案和全局一致的方案，最终一致的多数可通过消息机制等，全局一致的例如zookeeper/etcd之类的，既要全局一致又要做到很高的写支撑能力就很难实现了。

即使发展到今天，Sharding方式下的伸缩性问题仍然是很大的挑战，非常不好做。

上面所写的基本都还只是解决的方向，到细节点基本就很容易判断是一个解决过多大规模场景问题的架构师，:)

稳定性

作为分布式系统，必须要考虑清楚整个系统中任何一个点挂掉应该怎么处理（到了一定机器规模，每天挂掉一些机器很正常），同样主要还是分成了无状态和有状态：

无状态场景

对于无状态场景，通常好办，只用节点发现的机制上具备心跳等检测机制就OK，经验上来说无非就是纯粹靠4层的检测对业务不太够，通常得做成7层的，当然，做成7层的就得处理好规模大了后的问题。

有状态场景

对于有状态场景，就比较麻烦了，对数据一致性要求不高的还OK，主备类型的方案基本也可以用，当然，主备方案要做的很好也非常不容易，有各种各样的方案，对于主备方案又觉得不太爽的情况下，例如HBase这样的，就意味着挂掉一台，另外一台接管的话是需要一定时间的，这个对可用性还是有一定影响的；

全局一致类型的场景中，如果一台挂了，就通常意味着得有选举机制来决定其他机器哪台成为主，常见的例如基于paxos的实现。

可维护性

维护性是很容易被遗漏的部分，但对分布式系统来说其实是很重要的部分，例如整个系统环境应该怎么搭建，部署，配套的维护工具、监控点、报警点、问题定位、问题处理策略等等。

㈥ hash算法的作用是什么

身份验证
数字签名

㈦ Redis怎么做集群

为什么集群？

通常，为了提高网站响应速度，总是把热点数据保存在内存中而不是直接从后端数据库中读取。Redis是一个很好的Cache工具。大型网站应用，热点数据量往往巨大，几十G上百G是很正常的事儿，在这种情况下，如何正确架构Redis呢？

首先，无论我们是使用自己的物理主机，还是使用云服务主机，内存资源往往是有限制的，scale up不是一个好办法，我们需要scale out横向可伸缩扩展，这需要由多台主机协同提供服务，即分布式多个Redis实例协同运行。

其次，目前硬件资源成本降低，多核CPU，几十G内存的主机很普遍，对于主进程是单线程工作的Redis，只运行一个实例就显得有些浪费。同时，管理一个巨大内存不如管理相对较小的内存高效。因此，实际使用中，通常一台机器上同时跑多个Redis实例。

方案

1.Redis官方集群方案 Redis Cluster

Redis Cluster是一种服务器Sharding技术，3.0版本开始正式提供。

Redis Cluster中，Sharding采用slot(槽)的概念，一共分成16384个槽，这有点儿类pre sharding思路。对于每个进入Redis的键值对，根据key进行散列，分配到这16384个slot中的某一个中。使用的hash算法也比较简单，就是CRC16后16384取模。

Redis集群中的每个node(节点)负责分摊这16384个slot中的一部分，也就是说，每个slot都对应一个node负责处理。当动态添加或减少node节点时，需要将16384个槽做个再分配，槽中的键值也要迁移。当然，这一过程，在目前实现中，还处于半自动状态，需要人工介入。

Redis集群，要保证16384个槽对应的node都正常工作，如果某个node发生故障，那它负责的slots也就失效，整个集群将不能工作。

为了增加集群的可访问性，官方推荐的方案是将node配置成主从结构，即一个master主节点，挂n个slave从节点。这时，如果主节点失效，Redis Cluster会根据选举算法从slave节点中选择一个上升为主节点，整个集群继续对外提供服务。这非常类似前篇文章提到的Redis Sharding场景下服务器节点通过Sentinel监控架构成主从结构，只是Redis Cluster本身提供了故障转移容错的能力。

Redis Cluster的新节点识别能力、故障判断及故障转移能力是通过集群中的每个node都在和其它nodes进行通信，这被称为集群总线(cluster bus)。它们使用特殊的端口号，即对外服务端口号加10000。例如如果某个node的端口号是6379，那么它与其它nodes通信的端口号是16379。nodes之间的通信采用特殊的二进制协议。

对客户端来说，整个cluster被看做是一个整体，客户端可以连接任意一个node进行操作，就像操作单一Redis实例一样，当客户端操作的key没有分配到该node上时，Redis会返回转向指令，指向正确的node，这有点儿像浏览器页面的302 redirect跳转。

Redis Cluster是Redis 3.0以后才正式推出，时间较晚，目前能证明在大规模生产环境下成功的案例还不是很多，需要时间检验。

2.Redis Sharding集群

Redis 3正式推出了官方集群技术，解决了多Redis实例协同服务问题。Redis Cluster可以说是服务端Sharding分片技术的体现，即将键值按照一定算法合理分配到各个实例分片上，同时各个实例节点协调沟通，共同对外承担一致服务。

多Redis实例服务，比单Redis实例要复杂的多，这涉及到定位、协同、容错、扩容等技术难题。这里，我们介绍一种轻量级的客户端Redis Sharding技术。

Redis Sharding可以说是Redis Cluster出来之前，业界普遍使用的多Redis实例集群方法。其主要思想是采用哈希算法将Redis数据的key进行散列，通过hash函数，特定的key会映射到特定的Redis节点上。这样，客户端就知道该向哪个Redis节点操作数据。

庆幸的是，java redis客户端驱动jedis，已支持Redis Sharding功能，即ShardedJedis以及结合缓存池的ShardedJedisPool。

Jedis的Redis Sharding实现具有如下特点：

1. 采用一致性哈希算法(consistent hashing)，将key和节点name同时hashing，然后进行映射匹配，采用的算法是MURMUR_HASH。采用一致性哈希而不是采用简单类似哈希求模映射的主要原因是当增加或减少节点时，不会产生由于重新匹配造成的rehashing。一致性哈希只影响相邻节点key分配，影响量小。

2.为了避免一致性哈希只影响相邻节点造成节点分配压力，ShardedJedis会对每个Redis节点根据名字(没有，Jedis会赋予缺省名字)会虚拟化出160个虚拟节点进行散列。根据权重weight，也可虚拟化出160倍数的虚拟节点。用虚拟节点做映射匹配，可以在增加或减少Redis节点时，key在各Redis节点移动再分配更均匀，而不是只有相邻节点受影响。

3.ShardedJedis支持keyTagPattern模式，即抽取key的一部分keyTag做sharding，这样通过合理命名key，可以将一组相关联的key放入同一个Redis节点，这在避免跨节点访问相关数据时很重要。

㈧ java有没有不会冲突的hash算法

java.util.HashMap的中put方法的具体实现：
static inline intptr_t get_next_hash(Thread * Self, oop obj) {
intptr_t value = 0 ;
if (hashCode == 0) {
// This form uses an unguarded global Park-Miller RNG,
// so it's possible for two threads to race and generate the same RNG.
// On MP system we'll have lots of RW access to a global, so the
// mechanism inces lots of coherency traffic.
value = os::random() ;
} else
if (hashCode == 1) {
// This variation has the property of being stable (idempotent)
// between STW operations. This can be useful in some of the 1-0
// synchronization schemes.
intptr_t addrBits = intptr_t(obj) >> 3 ;
value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
} else
if (hashCode == 2) {
value = 1 ; // for sensitivity testing
} else
if (hashCode == 3) {
value = ++GVars.hcSequence ;
} else
if (hashCode == 4) {
value = intptr_t(obj) ;
} else {
// Marsaglia's xor-shift scheme with thread-specific state
// This is probably the best overall implementation -- we'll
// likely make this the default in future releases.
unsigned t = Self->_hashStateX ;
t ^= (t << 11) ;
Self->_hashStateX = Self->_hashStateY ;
Self->_hashStateY = Self->_hashStateZ ;
Self->_hashStateZ = Self->_hashStateW ;
unsigned v = Self->_hashStateW ;
v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
Self->_hashStateW = v ;
value = v ;
}

value &= markOopDesc::hash_mask;
if (value == 0) value = 0xBAD ;
assert (value != markOopDesc::no_hash, "invariant") ;
TEVENT (hashCode: GENERATE) ;
return value;
}

该实现位于hotspot/src/share/vm/runtime/synchronizer.cpp文件下。

㈨ php的memcached分布式hash算法,如何解决分布不均crc32这个算法没办法把key值均匀的分布出去

memcached的总结和分布式一致性hash
当前很多大型的web系统为了减轻数据库服务器负载，会采用memchached作为缓存系统以提高响应速度。
目录： （http://hounwang.com/lesson.html）
memchached简介
hash
取模
一致性hash
虚拟节点
源码解析
参考资料
1. memchached简介
memcached是一个开源的高性能分布式内存对象缓存系统。
其实思想还是比较简单的，实现包括server端（memcached开源项目一般只单指server端）和client端两部分:
server端本质是一个in-memory key-value store，通过在内存中维护一个大的hashmap用来存储小块的任意数据，对外通过统一的简单接口（memcached protocol）来提供操作。
client端是一个library，负责处理memcached protocol的网络通信细节，与memcached server通信，针对各种语言的不同实现分装了易用的API实现了与不同语言平台的集成。
web系统则通过client库来使用memcached进行对象缓存。
2. hash
memcached的分布式主要体现在client端，对于server端，仅仅是部署多个memcached server组成集群，每个server独自维护自己的数据（互相之间没有任何通信），通过daemon监听端口等待client端的请求。
而在client端，通过一致的hash算法，将要存储的数据分布到某个特定的server上进行存储，后续读取查询使用同样的hash算法即可定位。
client端可以采用各种hash算法来定位server：
取模
最简单的hash算法
targetServer = serverList[hash(key) % serverList.size]
直接用key的hash值（计算key的hash值的方法可以自由选择，比如算法CRC32、MD5,甚至本地hash系统，如java的hashcode）模上server总数来定位目标server。这种算法不仅简单，而且具有不错的随机分布特性。
但是问题也很明显，server总数不能轻易变化。因为如果增加/减少memcached server的数量，对原先存储的所有key的后续查询都将定位到别的server上，导致所有的cache都不能被命中而失效。
一致性hash
为了解决这个问题，需要采用一致性hash算法（consistent hash）
相对于取模的算法，一致性hash算法除了计算key的hash值外，还会计算每个server对应的hash值，然后将这些hash值映射到一个有限的值域上（比如0~2^32）。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到，则直接把具有最小hash值的server作为目标server。
为了方便理解，可以把这个有限值域理解成一个环，值顺时针递增。
如上图所示，集群中一共有5个memcached server，已通过server的hash值分布到环中。
如果现在有一个写入cache的请求，首先计算x=hash(key)，映射到环中，然后从x顺时针查找，把找到的第一个server作为目标server来存储cache，如果超过了2^32仍然找不到，则命中第一个server。比如x的值介于A~B之间，那么命中的server节点应该是B节点
可以看到，通过这种算法，对于同一个key，存储和后续的查询都会定位到同一个memcached server上。
那么它是怎么解决增/删server导致的cache不能命中的问题呢？
假设，现在增加一个server F，如下图
此时，cache不能命中的问题仍然存在，但是只存在于B~F之间的位置（由C变成了F），其他位置（包括F~C）的cache的命中不受影响（删除server的情况类似）。尽管仍然有cache不能命中的存在，但是相对于取模的方式已经大幅减少了不能命中的cache数量。
虚拟节点
但是，这种算法相对于取模方式也有一个缺陷：当server数量很少时，很可能他们在环中的分布不是特别均匀，进而导致cache不能均匀分布到所有的server上。
如图，一共有3台server – 1，2，4。命中4的几率远远高于1和2。
为解决这个问题，需要使用虚拟节点的思想：为每个物理节点（server）在环上分配100～200个点，这样环上的节点较多，就能抑制分布不均匀。
当为cache定位目标server时，如果定位到虚拟节点上，就表示cache真正的存储位置是在该虚拟节点代表的实际物理server上。
另外，如果每个实际server的负载能力不同，可以赋予不同的权重，根据权重分配不同数量的虚拟节点。
// 采用有序map来模拟环
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值
// 计算总权重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 为每个server分配虚拟节点
for ( int i = 0; i < servers.length; i++ ) {
// 计算当前server的权重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用来控制每个server分配的虚拟节点数量
// 权重都相同时，factor=40
// 权重不同时，factor=40*server总数*该server权重所占的百分比
// 总的来说，权重越大，factor越大，可以分配越多的虚拟节点
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每个server有factor个hash值
// 使用server的域名或IP加上编号来计算hash值
// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每个hash值生成4个虚拟节点
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在环上保存节点
consistentBuckets.put( k, servers[i] );
}
}
// 每个server一共分配4*factor个虚拟节点
}
// 采用有序map来模拟环
this.consistentBuckets = new TreeMap();
MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值
// 计算总权重
if ( this.totalWeight for ( int i = 0; i < this.weights.length; i++ )
this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];
} else if ( this.weights == null ) {
this.totalWeight = this.servers.length;
}
// 为每个server分配虚拟节点
for ( int i = 0; i < servers.length; i++ ) {
// 计算当前server的权重
int thisWeight = 1;
if ( this.weights != null && this.weights[i] != null )
thisWeight = this.weights[i];
// factor用来控制每个server分配的虚拟节点数量
// 权重都相同时，factor=40
// 权重不同时，factor=40*server总数*该server权重所占的百分比
// 总的来说，权重越大，factor越大，可以分配越多的虚拟节点
double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );
for ( long j = 0; j < factor; j++ ) {
// 每个server有factor个hash值
// 使用server的域名或IP加上编号来计算hash值
// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值：
// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor
byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );
// 每个hash值生成4个虚拟节点
for ( int h = 0 ; h < 4; h++ ) {
Long k =
((long)(d[3+h*4]&0xFF) << 24)
| ((long)(d[2+h*4]&0xFF) << 16)
| ((long)(d[1+h*4]&0xFF) << 8 )
| ((long)(d[0+h*4]&0xFF));
// 在环上保存节点
consistentBuckets.put( k, servers[i] );
}
}
// 每个server一共分配4*factor个虚拟节点
}
// 用MD5来计算key的hash值
MessageDigest md5 = MD5.get();
md5.reset();
md5.update( key.getBytes() );
byte[] bKey = md5.digest();

// 取MD5值的低32位作为key的hash值
long hv = ((long)(bKey[3]&0xFF) << 24) | ((long)(bKey[2]&0xFF) << 16) | ((long)(bKey[1]&0xFF) << 8 ) | (long)(bKey[0]&0xFF);

// hv的tailMap的第一个虚拟节点对应的即是目标server
SortedMap tmap = this.consistentBuckets.tailMap( hv );
return ( tmap.isEmpty() ) ? this.consistentBuckets.firstKey() : tmap.firstKey();
更多问题到问题求助专区（http://bbs.hounwang.com/）

㈩ 一致性哈希 java实现 怎么映射到圆环上

一致性哈希提出了在动态变化的Cache环境中，哈希算法应该满足的4个适应条件：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。（这段翻译信息有负面价值的，当缓冲区大小变化时一致性哈希(Consistenthashing)尽量保护已分配的内容不会被重新映射到新缓冲区。）简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x→ax+bmod(P)在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。从表面上看，一致性哈希针对的是分布式缓冲的问题，但是如果将缓冲看作P2P系统中的Peer，将映射的内容看作各种共享的资源(数据，文件，媒体流等)，就会发现两者实际上是在描述同一问题。路由算法在一致性哈希算法中，每个节点(对应P2P系统中的Peer)都有随机分配的ID。在将内容映射到节点时，使用内容的关键字和节点的ID进行一致性哈希运算并获得键值。一致性哈希要求键值和节点ID处于同一值域。最简单的键值和ID可以是一维的，比如从0000到9999的整数集合。根据键值存储内容时，内容将被存储到具有与其键值最接近的ID的节点上。例如键值为1001的内容，系统中有ID为1000，1010，1100的节点，该内容将被映射到1000节点。为了构建查询所需的路由，一致性哈希要求每个节点存储其上行节点(ID值大于自身的节点中最小的)和下行节点(ID值小于自身的节点中最大的)的位置信息(IP地址)。当节点需要查找内容时，就可以根据内容的键值决定向上行或下行节点发起查询请求。收到查询请求的节点如果发现自己拥有被请求的目标，可以直接向发起查询请求的节点返回确认；如果发现不属于自身的范围，可以转发请求到自己的上行/下行节点。为了维护上述路由信息，在节点加入/退出系统时，相邻的节点必须及时更新路由信息。这就要求节点不仅存储直接相连的下行节点位置信息，还要知道一定深度(n跳)的间接下行节点信息，并且动态地维护节点列表。当节点退出系统时，它的上行节点将尝试直接连接到最近的下行节点，连接成功后，从新的下行节点获得下行节点列表并更新自身的节点列表。同样的，当新的节点加入到系统中时，首先根据自身的ID找到下行节点并获得下行节点列表，然后要求上行节点修改其下行节点列表，这样就恢复了路由关系。