一致性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找到下行節點並獲得下行節點列表，然後要求上行節點修改其下行節點列表，這樣就恢復了路由關系。