時間の複雑度

 ここまでできれば、一致性ハッシュはすでに完璧に見えるようだが、我々はもう一つの問題を見落とした、それは一致性ハッシュの時間をサーチする複雑度である。一致性ハッシュは一般ハッシュと違って、時間の複雑度は0(1)で、これは普通のハッシュは数値グループに基づいており、一方、一致性ハッシュは伸縮性に満足するためにチェーンテーブルを選択して基礎データの構造とするのが一般的である。そうすると時間の複雑度が0(N)になる。

最適化方案

 ここでは0(N)の時間の複雑度はハッシュアルゴリズムにとって堪えられないことである、なので我々はジャンプテーブルと呼ばれる技術を使用してこの問題を解決する。

clip_image0021.jpg
上記図のように、このジャンプテーブルの中に、各ノードは自分に1、2、4の距離に離れている数字が保存されるノードを記録する、そうするとサーチがどのノードに落ちても、全体のハッシュリングに対するあらゆるサーチは最低でも半分のサーチスペースが省けられる、こうのように再帰すればすぐにデータがどのノードに保存されているかが追跡できる。そうすれば、時間複雑度が0(LogN)まで下がる。ただし、この方法は同様にサーバーの保存スペースを占用する問題を齎すことがある。

 第二種の解決方案は、チェーンテーブルを基礎のデータ構造として使用せず、バイナリサーチツリー構造に変える。ハッシュサーチのプロセスは実際バイナリサーチツリーの中でサーチ数値以上の最小数値をサーチする過程である、なので我々は需要に基づいてAVLツリーを選択して、レッドブラックツリーを基礎データ構造とする。そうすることによって、時間複雑度を0(logN)まで下げることができる。