java最短路徑算法如何實現(xiàn)有向任意兩點的最短路徑？Dijkstra算法是一種典型的最短路徑路由算法，用于計算從一個節(jié)點到所有其他節(jié)點的最短路徑。主要特征是從起點向外擴展，直到終點。Dijkstra一

java最短路徑算法如何實現(xiàn)有向任意兩點的最短路徑？

1.聲明兩組，打開和關閉。open用于存儲未遍歷的節(jié)點，close用于存儲已遍歷的節(jié)點。

2.在初始階段，將初始節(jié)點置于關閉狀態(tài)，將所有其他節(jié)點置于打開狀態(tài)。

3.以初始節(jié)點為中心逐層向外遍歷，得到離指定節(jié)點最近的子節(jié)點，放入close并重新計算路徑，直到close包含所有子節(jié)點編碼。例子如下:Node對象用于封裝節(jié)點信息，包括名稱和子節(jié)點[Java]view plain copy public class

用最通俗易懂的解釋一致哈希算法；

首先要明確，一般的哈希算法在取模的時候往往和實際應用有關！

比如使用nginx hash時，會根據(jù)后臺應用服務器的數(shù)量取模。比如后臺有四個應用，通過hash(key)%4 =(0，1，2，3)可以得到其中一個的具體標簽。此時，如果后臺應用需要擴展，哈希算法將改為hash (key) % 6 = (0，1)。它不 t把請求分發(fā)到6臺不同的機器上看起來問題不大，但是如果我們把場景切換到一個數(shù)據(jù)庫按照業(yè)務主鍵business_no進行哈希的子數(shù)據(jù)庫和子表結構，切換之后因為哈希算法的變化，原始數(shù)據(jù)下降到4，但是哈希結果是5，那么原始數(shù)據(jù)可以 t被發(fā)現(xiàn)，并且存在數(shù)據(jù)查詢錯誤問題！

但如果在redis上出現(xiàn)上述問題，由于大量數(shù)據(jù)未命中，大量查詢降落在底層數(shù)據(jù)庫上，嚴重的話會出現(xiàn)緩存雪崩問題，導致數(shù)據(jù)庫系統(tǒng)甚至整個系統(tǒng)的雪崩；

讓 下面我們來詳細說說一致哈希算法(以redis存儲為例)解決上述問題的方法:

一致哈希算法，不管你有多少應用，都是以2 ^ 32(2的32次方)為模數(shù)，把0和2 ^ 32-1首尾相連形成一個環(huán)，這樣所有使用一致哈希算法的數(shù)據(jù)都是大概率一致的。落在這枚戒指上；

掉在環(huán)上的數(shù)據(jù)最后怎么會在不同的redis服務器上？無論我們使用redis服務器的IP還是域名，它都是一個唯一的標識符。很好理解，通過計算hash值，同樣落在這個環(huán)上(ABCD服務器節(jié)點)，然后規(guī)定落在環(huán)上的數(shù)據(jù)順時針旋轉(zhuǎn)，存儲在我們遇到的第一個節(jié)點(服務器)上。如下圖所示:

使用一致哈希后，我們服務器的擴展也將變得非常容易。如果監(jiān)測到一個節(jié)點(D)的壓力相對較高，則通過計算哈希值，在這個節(jié)點的上游逆時針方向增加一個服務器E(A和D之間)，如下圖所示:

這時，如果有請求進來，整個環(huán)中只有A和E之間的數(shù)據(jù)可以 t被獲取，會對下層數(shù)據(jù)庫產(chǎn)生影響，其他所有數(shù)據(jù)不會有任何影響，所以使用一致哈希擴展非常方便！

一致性哈希存在的問題:

1.雪崩效應:假設我們不 t有類似上面說的監(jiān)控，或者A節(jié)點(B)的數(shù)據(jù)激增，在我們做出反應之前，這個節(jié)點此時宕機，那么所有的數(shù)據(jù)請求都會迅速落在A身上，A不僅要承擔自己的數(shù)據(jù)，還要承擔B ;s，而且肯定會馬上崩潰，最后整個緩存系統(tǒng)都會產(chǎn)生雪崩效應！

2.分布不均勻:上面的例子對于哈希算法來說太理想化了。比如四臺ABCD服務器的hash值剛好是1，2，3，4，這意味著所有hash值在(4，2 32-1)范圍內(nèi)的數(shù)據(jù)都會落在一個服務上，這也將是災難性的。。。

那么我們?nèi)绾谓鉀Q這種非常不均勻的數(shù)據(jù)分布呢？

解決方案:最好的方法是添加虛擬節(jié)點。截圖如下:

ABCD向每個服務器A、B、C和D添加了一個虛擬節(jié)點(或多個虛擬節(jié)點),這意味著節(jié)點A現(xiàn)在可以接受從B2-A1加上C1到A2的數(shù)據(jù)。假設服務A宕機，A1的數(shù)據(jù)會落在C2(也就是C)，A2的數(shù)據(jù)會落在D1(也就是D)，這意味著隨著崩潰服務器的增加，相應的數(shù)據(jù)會更加分散。

通過以上案例，我們可以看到，一致哈希遵循以下原則:①平衡:將數(shù)據(jù)盡可能均勻地分布在整個哈希環(huán)上，

(2)單調(diào)性:在擴展時，會保證原始數(shù)據(jù)盡可能少的落在新的節(jié)點上。

3.去中心化:盡量避免相同的內(nèi)容落在不同的節(jié)點上！

一致哈希的原理很簡單，但是一致哈希算法在redis集群、數(shù)據(jù)庫子數(shù)據(jù)庫子表等場景中應用廣泛，解決了數(shù)據(jù)分布不均勻、擴展困難等問題，是大規(guī)模集群中的優(yōu)秀算法！

本文個人感受這個解釋相當容易理解。如果你有朋友不喜歡。;我不明白，你可以私下信任我。我會再解釋一遍。后期會有更多的技術分享，請繼續(xù)關注。謝謝你。。。