2

プロジェクトのヴォルデモートのデザインページ：

http://project-voldemort.com/design.php

ハッシュリングは区間[0、2^31-1]をカバーすると述べられています。

ここで、間隔[0、2^31-1]は2^31の総数を表し、最大数の2 ^ 31-1はすべて1に設定された31ビットです（これを納得させるために、2 ^3-を検討してください）。 1. 2 ^ 3=8で0x1000です。2^3-1= 7で0x111です）。

したがって、通常の32ビットアドレスワードを使用して値を格納する場合、1ビットの空き容量があります。

では、なぜ2 ^ 31-1が上限なのですか？その余分なビットは、ある種のシステム簿記に使用されていますか？

（たとえば、1ビット余分に1ビット追加すると、オーバーフローすることなく2つの有効なハッシュアドレスを安全に追加するためのスペースが提供されます）。

そして最後に、この選択はヴォルデモートに固有のものですか、それとも他のコンシステントハッシュスキームで見られますか？

4

2 に答える 2

1

2ではなく1ビットしか空いていないと思います。-1は、1ではなく「0」という数字で始まるという事実を説明しています（同じ理由で、ループは0からカウント-1までカウントされます）。2^32ではなく2^31を使用している理由は、符号付き整数を使用しているため、最後のビットが符号ビットであるため使用できないためだと思います。

編集：リンクしたページから：

コンシステントハッシュ法を視覚化するために、可能な整数ハッシュ値を0で始まり、2^31-1まで循環するリングとして見ることができます。

整数を指定するため、負のハッシュ値が必要な場合を除いて、2^32ではなく2^31でスタックします。

于 2011-08-18T18:37:19.363 に答える
0

質問に答えるのが少し遅く、わずか4年です:)

その理由は、ヴォルデモートが Java で書かれており、Java には unsigned int がないからです。パーティションの 2^31 はすでに非常に高くなっています。通常、数千のパーティションのみで実行することをお勧めします。

于 2015-10-29T02:04:38.297 に答える