実例！キャッシュの仕組み
ハッシング＋リンクトリスト 「第3回：ソースでわかる！ハッシング」でハッシングとリンクトリストを組み合わせたものを紹介しました。今回はそのプログラムを紹介しますが、実はその本体はこれまでに紹介したものばかりです。1本のリンクトリストを扱うプログラムは第1回に紹介しました。これをハッシュ値が同じもの同士をひとつのリストにするようにして、複数のリストを作って管理するのがこの方法です。 第3回の最後にハッシングとリンクトリストを使ったプログラムのinsert()関数を紹介しましたが、ハッシング機能のモジュールの全体を図1-1に示します。ハッシュ関数h()のほかに、このハッシュテーブル＋リンクトリストの構造を使った登録insert()、検索search()および削除delete()の機能を加えています。 テストプログラムを含めたプログラム全体はこちら（http://www.thinkit.co.j
ソースでわかる！ハッシング
これまでの2回で、増減するデータを格納して検索するための方法を2つ紹介しました。1つはリスト構造（linked list）、もう1つは二分探索木（binary search tree）です。 この2つは、配列に対する線形探索（linear search）と二分探索（binary search）と同様の探索性能があることを示しました。アルゴリズム性能を表すオーダーＯで表すと、それぞれＯ(n)とＯ(log2(n))です。 今回は、Ｏ(1)である方法を紹介します。今回もプログラムを使いながら見てみましょう。プログラムはこちら（http://www.thinkit.co.jp/images/article/159/3/15931.zip）からダウンロードできます（15931.zip/2 KB）。 アルゴリズム性能がＯ(1)であるとは、「いつでも一定の時間でアルゴリズムが停止する」ということです。探
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
Matzにっき(2008-03-04)
<< 2008/03/ 1 1. [Ruby] Ruby 1.9.0-1 snapshot released 2. 高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんと 3. [Ruby] Lisa Awards: Biggest Hack for a Language Runtime on Dion Almaer's Blog 2 1. [教会] 第一安息日 3 1. [言語] CS 11: Python track: python idioms 2. [Ruby] Binary search algorithm - Wikipedia, the free encyclopedia 3. [OSS] Theological Cultural Analysis of the Free Software Movement 4. 小寺信良：正直、テレビはもうダメかも
mixi Engineers’ Blog » スマートな分散で快適キャッシュライフ
今日は以前のエントリーで書くと述べたConsistent Hashingに関して語らせて頂こうかと思います。ただしConsistent Hashingはセミナーやカンファレンスなどでかなり語られていると思いますので、コンセプトに関しては深入りせず、実用性に着目したいと思います。 問題定義 分散されたキャッシュ環境において、典型的なレコードを適切なノードに格納するソリューションはkeyのハッシュ値に対しmodulo演算を行い、その結果を基にノードを選出する事です。ただし、このソリューションはいうまでもなく、ノード数が変わるとキャッシュミスの嵐が生じます。つまり実世界のソリューションとしては力不足です。 ウェブサイトのキャッシュシステムの基本はキャッシュがヒットしなかったらデータベースにリクエストを発行し、レコードが存在したらキャッシュしてクライエントに返すという流れです。ここで問題なのが一瞬
DO : Bep: 最小完全ハッシュ関数を用いた連想配列
Bepという連想配列のライブラリを公開しました。BSDライセンスです． キーは文字列限定で，前もって大量のキーと値のペアが前もって分かっている場合（１千万個とか）、使ってもらえるよう最適化しています。（一応、アドホックな方法で一個ずつキーを登録する方法もサポートしています） 特徴は内部に最小完全ハッシュ関数を利用しており少ない作業領域量でありながらそこそこ高速に動くところです．今のところ１千万キーぐらいで動作するのは確認しています．１キーあたり必要な作業領域量は大体3bit + キー自体の長さになります． 最小完全ハッシュ関数の構築自体も面白い問題です．最小完全ハッシュ関数はキー同士が衝突せず、さらにキーの数がn個のときハッシュ値は[0...n-1]が返されるもので、ぎっしり詰まった連番が返されると思ってもよいです。この実現には以下の論文での手法を使いました．3-ハイパーグラフの頂点割り当
Matzにっき(2007-08-17)
<< 2007/08/ 1 1. [言語] 連載：C# 2.0入門 第3回 新しい繰り返しのスタイル − yield return文とForEachメソッド − ＠IT 2. [Ruby] Shoes, a Tiny Toolkit for Making Browser-like Things 2 1. [OSS] Download Hadoop at OSCON (Yahoo! Developer Network blog) 2. ウェブキャリアでWebエンジニアとしてのキャリアを磨こう 株式会社ウェブキャリア 3. 先達の業界に学ぶプロジェクトマネジメント 第1回 20年は遅れているITプロマネ：ITpro 4. 横浜 3 1. [OSS] 特別講演：「オープンソース・ソフトウェア開発思想とリアルな地域ネットワークの連 2. [Ruby] トークセッション-5：「世界に広がるオブジェク
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
yebo blog: 新しいハッシュ関数「Skein」