コンシステントハッシュ法 - Wikipedia
コンピュータ科学の分野で、コンシステントハッシュ法（Consistent hashing）とは、ハッシュテーブルのサイズが変更された時、をキーの数、をスロット数とすると、平均個のキーのマッピングの変更のみでハッシュテーブルの機能を提供することのできる、特殊なハッシュ法である。それに対して、その他の多くのハッシュ法では、キーとスロット間のマッピングがモジュラ演算によって定義されているため、ハッシュテーブルのスロット数が変化するとほぼすべてのキーが再マッピングされてしまう。分散システムの一形態である分散キャッシュなどで利用されている。 コンシステントハッシュは、ランデブーハッシュ（英語版）（HRWハッシュとも呼ばれる）と同じ目的を達成するハッシュ法であるが、2つの手法は異なるアルゴリズムを使用しており、同時に独立して開発された。 スロットのハッシュ値をソートしてリストに管理する。前提条件として
Linear hashing - Wikipedia
Linear hashing (LH) is a dynamic data structure which implements a hash table and grows or shrinks one bucket at a time. It was invented by Witold Litwin in 1980.[1] [2] It has been analyzed by Baeza-Yates and Soza-Pollman.[3] It is the first in a number of schemes known as dynamic hashing[3] [4] such as Larson's Linear Hashing with Partial Extensions, [5] Linear Hashing with Priority Splitting,[6
Java8 で java.lang.Object#hashCode() の生成アルゴリズムが変更されていました。 - 地平線に行く
java.lang.Object#hashCode()の性質という記事で書いたのですが、Java の Object#hashCode() の値はただの乱数となっています。 この乱数のアルゴリズムが、Java SE 8 で「線形合同法」から「XORシフト方式」に変更になっていました。 といっても、変更されたのはたった1文字。 VMオプションのデフォルト設定が -XX:hashCode=0 から -XX:hashCode=5 に変わっただけでした。 hotspot-rt Udiff hotspot/src/share/vm/runtime/globals.hpp どういうこと？ もともと、Java の以前の実装*1 *2から、Object#hashCode() のアルゴリズムはVMオプション -XX:hashCode=? で選べるようになっていました。 ですが、デフォルトは長いこと 0(=線形
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
ハッシュ法
ハッシュ法（hashing）は、メモリ上でデータを高速に検索するための手法である。各種のツリー構造とは異なり、静的な配列だけで簡単に実装でき、効率も極めて高い。このため、非常に実用的な手法として重宝である。 配列上でデータを検索する手法には、ハッシュの他いくつかある。以下、単純な手法から順に説明していき、ハッシュ法の説明に至ることにしよう。 ある小さな会社の社員情報をメモリ上で処理する場合を考えてみよう。社員情報のキーとして社員番号（整数）を用いることだけを決めておき、その他については考えないことにする。 （１）単純配列 データの出現順に配列につめていく。もっとも単純かつ基本的な方法。 データの挿入は高速だが、検索は端から順に見ていく（リニアサーチという）しかないため、平均するとデータ件数（社員数）の半分について処理が必要となる。 この手法は遅いので、データ件数が多い場合には使われない・・
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
