Abstract: Benchmark program for hash tables and comparison of 15 popular hash functions. Created 16 years ago by Peter Kankowski Last changed 4 years ago Contributors: Nils, Ace, Won, Andrew M., and Georgi 'Sanmayce' Filed under Algorithms Hash tables are popular data structures for storing key-value pairs. A hash function is used to map the key value (usually a string) to array index. The functio
クラステンプレート: unordered_set TR1にはハッシュ表を使った4種のコンテナが定義されています。 unordered_set : 要素の重複を許さない集合 unordered_multiset : 要素の重複を許す集合 unordered_map : 要素の重複を許さない辞書 unordered_multimap : 要素の重複を許す辞書 これらを代表してunordered_setについて、その概要を説明します。 namespace std { namespace tr1 { // [6.3.4.3] Class template unordered_set template <class Value, class Hash = hash<Value>, class Pred = std::equal_to<Value>, class Alloc = std::alloca
形態素の頻度をカウントするというシンプルなタスクで std::tr1::unordered_map の性能について実験してみました．std::string より const char * の方がメモリを節約できるというような軽い内容です． 実験概要 実験環境は以下のとおりです． 実験環境 CPU：Core 2 Duo U9600 1.60GHz コンパイラ：gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) 入力として使用したのは，ウェブコーパスから抽出した形態素を改行区切りで保存したファイルです． 入力 サイズ：815,793,701 bytes 形態素数：133,940,786 異なり数：516,612 形態素の入力については，std::ios::sync_with_stdio(false) を呼び出した後で std::getline() を使うようにし
今回は小ネタのmikioです。key/valueのレコードを高速に格納・参照・削除する仕組みが連想配列とかマップとか呼ばれて親しまれていますが、Tokyo Cabinetのオンメモリマップの性能をC++の各種実装と比較してみました。 以下の実装を対象として、100万レコードの格納と検索にかかる時間を計測します。キーと値は各8バイトの文字列とします。 Tokyo Cabientのオンメモリマップ（TCMAP） STL（C++の標準テンプレートライブラリ）のmapとmulti mapとset GNU拡張テンプレートのハッシュマップ Googleのdense hashおよびsparse hash テストコードはこちらに挙げておきます。具体的な操作としては、マップオブジェクトを生成し、バケット配列の要素数をレコード数と同じにチューニングし、ループを回してレコード群を格納します。なお、STLのマップ
とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、
1.ハッシュへ値を代入 ハッシュ変数は、配列のインデックスが文字列となったもので、このインデックスを『キー』と呼びます。ハッシュの場合は要素の値がキーによって管理されます。 ハッシュの宣言 ハッシュへ値を代入 ハッシュの宣言 ハッシュを宣言するときは変数名の前にパーセント（ % ）を付けます。 %hash; ハッシュへ値を代入 配列では、[ ] でインデックスを囲みましたが、ハッシュは、 { }でキーを囲みます。例えば社員の名前とメールアドレスを管理する場合、次のような方法でハッシュを使った管理ができます。 $hash{'Akai'} = 'akai@domain.com'; $hash{'Ishikawa'} = 'ishi@domain.com'; $hash{'Ueda'} = 'ueda@domain.com'; 複数の値を一度にハッシュへ代入するには、キー、値の順番で記述します。
約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。 DBMとは TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。 プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッ
ハッシュテーブルは、中級の基本技である。「ハッカー」と呼ばれる程のプログラマならば、使いなれた自作ハッシュライブラリを持っていて当然である。また、これは非常に検索が速く便利なために、awk から Perl に至るスクリプト言語で、言語仕様に採り入れられてよく「連想配列」などと呼ばれている。要するに、 $List{'http'} = 80; のように、配列なのに文字列を添字として取るような書き方をするアレである。これは「キー」である文字列に対して、「値」である何かのオブジェクトを返すという動作であり、そういう動作こそが「ハッシュテーブル」以外の何者でもない。ものすごく便利なので、ぜひマスターされたい。→ Java 講座の「ハッシュテーブル」 準備～リスト版線形探査 ハッシュテーブルの原理 ライブラリの実装 他の応用 Java の Hashtable クラス 準備～リスト版線形探査 ハッシュテ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
