一致性哈希算法相關問題

老師這邊演算法的部分有些地方我不是很確定觀念是否正確不是很懂思考整理了以後想請老師指點迷津一下萬分感謝

*在route(int hashId, List<Server> addressList) function裡

由url得到的hashId要再做一次我們自己訂的hash是不是因為要和server和其虛擬節點採用一樣的hash算法之後才有辦法排序比較大小所以才必須再hash一次?
透過 for 0~7 long hash = hash(e.getId() + i) 虚化若干个服务节点到环上這種方式會不會讓同一server的節點和其虛擬節點都在圓環上同一區？還是因為下面hash function有先做過ＭＤ５了所以可以避免掉這問題？

*在long hash(String key) function裡

hashCode & 0xffffffffL 這邊需要 & 0xffffffffL 是不是因為一制性哈希本身能容納的就是32位的long整數範圍？
這邊要先取md5是不是也是有一部分是為了上面問題２提到的讓同一server的節點和其虛擬節點不會都在圓環上同一區？
最下面圖這段code是不是因為一制性哈希本身能容納的就是32位的long整數,所以透過這段產生一個３２位的hashcode？重點只是在產生一個３２位的整數？就算想把digest[2]和digest[0]左移的位數互換也ok?
但最下面圖這段code如果是為了產生一個３２位的整數,我有點不太懂,因為我的理解是最高位應該是只有一個char digest[2]的8位再左移16位,也就是24位？
是為了最高位bit不能是1(負數)的關係麼？
這樣做最高位的８bit是不是always是0?
還是這邊是我完全理解錯誤？如果是的話,這邊這樣設計的原因和準則是什麼？再請老師指點一下

hashCode = (() (digest[] & << ))
        | (() (digest[] & << ))
        | (() (digest[] & ))

收起

3回答

zhouywjava 2021-09-06 11:12:22

4. 我也觉得是24位。然后高8位是0 。最后一步与 32个 1 做与操作只是为了将24位格式化为32 位。也就是说这个hash 有参与计算的只是 digest 的前面3个byte。不过我觉得咱们用前面N 个byte 也可以吧,反正最后一句都会格式化为32位。

姚半仙 2020-10-23 23:37:10

*在long hash(String key) function裡

提问者 pinkyTseng #1

十分感謝老師詳細的解答這幾天在趕東西和進度雖然老師回復當天我就看過並想過了但還沒整理回覆先前我說的好像有點錯誤 long應該是64位才對,明白只取３２位的用意,只剩原本的２個問題和新增的小問題再和老師您確認下,萬分感謝老師 *在long hash(String key) function裡３.本來的hashCode是不是可由 long hashCode = ((long) (digest[2] & 0xFF << 16)) | ((long) (digest[1] & 0xFF << 8)) | ((long) (digest[0] & 0xFF)); 改成 long hashCode = ((long) (digest[0] & 0xFF << 16)) | ((long) (digest[1] & 0xFF << 8)) | ((long) (digest[2] & 0xFF)); 也ok? 移動位數一樣只是將位移的２個不同byte互換 4.上面本來的那段code如果是為了產生一個３２位的整數,我有點不太懂,因為我的理解是最高位應該是只有一個char digest[2]的8位再左移16位,也就是24位？是為了最高位bit不能是1(負數)的關係麼？這樣做最高位的８bit是不是always是0? 如果是這樣分布的點應該會全部集中在右半圓？ 5.還有個新增的小問題是 (long) (digest[2] & 0xFF << 16) 是不是該改成 (long) ((digest[2] & 0xFF) << 16)？另外兩個也是要加上（）我跑原本的寫法會顯示 long d2=(long) (digest[2] & 0xFF << 16); Integer.toBinaryString(digest[2] & 0xFF) == 11001010 Long.toBinaryString(d2) == 111111110000000000000000 ＝> 預期應該是 110010100000000000000000才對吧？

2020-11-01 12:00:33