あなたの知らないハッシュテーブルの世界Please select the category that most closely reflects your concern about the presentation, so that we can review it and determine whether it violates our Terms of Use or isn't appropriate for all viewers.
基本情報技術者Web学習室(データ構造とアルゴリズム)
これは、「整数型」「実数型」「文字型」があります。その他として以下のものがあります。 ●論理型 論理演算に使用される変数の型で「True」と「False」の2値をとります。 ●列挙型 要素に順序をつけたものです。例えば、「CPU」「メモリ」「HDD」の場合 1番目：CPU 2番目：メモリ 3番目：HDD のように順序付けたものです。 一般的には、(CPU、メモリ、HDD)と表現します。 ●ポインタ型 「ポインタ」というのは、「データが格納されているメモリのアドレス」を格納します。通常、変数には、値が格納されていますが、それがメモリ上のどの番地(アドレス)かをポインタが格納することが出来ます。例えば変数「a」が100という値が格納されていて、アドレスが10番地の時、ポインタ型の変数には、「10」が格納されています。 ●構造型 「レコード型」とも言います。これは、「複
ハッシュテーブル入門
近頃，分散コンピューティングの世界では分散ハッシュテーブル(Distributed Hash Table)なるものが広く認知されつつありますが，このページではこれから順をおって分散ハッシュテーブルの説明をしていこうと思います．いつ完成するか分かりませんが気長に見てくださいませ． 1, ハッシュテーブル 1.1 ハッシュテーブルとはなんぞや？ 何のために存在するのか？（前編） ではまず分散ハッシュテーブルにいくまえに，ハッシュテーブルとは何なんでしょうか？ハッシュテーブルを辞書的に説明するとこんな感じになるでしょう． "ハッシュテーブルとはキーと値のペアを格納し，一つ以上のハッシュ関数によってアクセスできるデータ構造のことである" 全く意味分かりませんね．キーって？値って？ハッシュ関数って？という感じです． では，少し噛み砕いて説明しましょう． [例1] 太郎さんは
第7回 性能改善の鍵、インデックスの特性を知る～B-treeとハッシュ （2）ハッシュ | gihyo.jp
SQLアタマアカデミー 第7回性能改善の鍵、インデックスの特性を知る～B-treeとハッシュ （2）ハッシュ ハッシュ 概要 チューニング技術としてB-treeの次に重要なのは、ハッシュ（hash）です。ハッシュとは「ごちゃまぜ」とか「細切れ」という意味で、ハッシュドビーフとかハッシュポテトなどの料理名にも使われています。 ハッシュのポイントは分散です。キー値に対して適当な関数を適用して、データを格納する先のアドレスを割り当てるのですが、このときポイントなのは、異なる値のキーに対しては、異なるアドレス（それもなるべく離れた）を割り振れるかどうかです。これができるほど、ハッシュ関数として優れているということになります（図6）。 図6 ハッシュのイメージ図（ハッシュパーティションの場合） なおハッシュは、Postgre SQLやMy SQLのようにインデックスとして実装しているDBのほか、
ハッシュ法
ハッシュ法（hashing）は、メモリ上でデータを高速に検索するための手法である。各種のツリー構造とは異なり、静的な配列だけで簡単に実装でき、効率も極めて高い。このため、非常に実用的な手法として重宝である。 配列上でデータを検索する手法には、ハッシュの他いくつかある。以下、単純な手法から順に説明していき、ハッシュ法の説明に至ることにしよう。 ある小さな会社の社員情報をメモリ上で処理する場合を考えてみよう。社員情報のキーとして社員番号（整数）を用いることだけを決めておき、その他については考えないことにする。 （１）単純配列 データの出現順に配列につめていく。もっとも単純かつ基本的な方法。 データの挿入は高速だが、検索は端から順に見ていく（リニアサーチという）しかないため、平均するとデータ件数（社員数）の半分について処理が必要となる。 この手法は遅いので、データ件数が多い場合には使われない・・
インメモリー・データベースの注意点
インメモリー・データベースの仕組み メモリーにデータを展開するインメモリー・データベースでは、基本的にディスク・アクセスは存在しません。十分なメモリーを確保することで、劇的なパフォーマンスを得ることができます。 また、従来のデータベースとは異なり、単にクエリーのキャッシュ用途や、インデックスの展開用にメモリーを利用しているわけではありません。 従来のディスクI/Oを使うデータベースは、B+ツリー索引でインデックスを付けています。ディスクI/Oを減らして、より多くのデータを取得できるように設計されています。これに対して、インメモリー・データベースは、インデックス構造をTツリー索引と呼ばれる方法に切り替えているものがあります。 Tツリー索引は、B+ツリー索引に比べて、消費するメモリーがより少なくなっています。具体的な例を挙げると、MySQLのオンメモリー・モードがB+ツリー索引を使っており、O
第5回 転置索引の実装 | gihyo.jp
はじめに 前回、前々回と転置索引の論理的構造について見てきました。今回は、転置索引の具体的なデータ構造や実装について説明していきます。 辞書の実装 辞書は通常、単語に対応した情報を高速に取得するために、ハッシュや木構造などのデータ構造を取ります。現在は, 安定した性能や単語の順序関係を利用したいなどの理由で、木構造のデータ構造が使われることが多いと思います。最も単純な場合、2分探索木（Binary Search Tree）や2分探索（Binary Search）の実装が考えられます。 2分探索（木）による辞書の実装 では、辞書の具体的なデータ構造について、図を交えて解説していきましょう。 前回も触れましたが、辞書には単語とその単語に対応するポスティングリストの位置情報のペア（のリスト）が格納されています。単語で検索をするので、ペア自体は単語をキーとして並び換えられます。 たとえば, 前回の
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
algorithm - 基数木 + 平衡二分探索木 = 三分探索木 : 404 Blog Not Found
2012年01月22日16:36 カテゴリアルゴリズム百選翻訳/紹介 algorithm - 基数木 + 平衡二分探索木 = 三分探索木 珠玉のプログラミング Jon Bentley /小林健一郎訳 最有力候補は、これかも。 Ternary search tree - Wikipedia, the free encyclopedia 三分探索木 - Wikipedia 404 Blog Not Found:algorithm - Patricia Trie (Radix Trie) を JavaScript で最近のTrie研究の傾向は、要素の動的変更が自在にできる一般向けのものではなく、一旦作成したら要素の追加と削除が困難な代わりにものすごくコンパクトになる、簡潔データ構造の応用手段の方に偏っていると素人目に感じるのですが、そろそろJudyたんのごとくハッシュテーブルとガチで闘うとか、逆
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
2分探索木
概要 一般に木構造というと、循環のない有向グラフのことなんですが、 そういう一般論はまた別の機会に話をしましょう。 ここでは、要素の挿入・削除・検索を高速に行うことの出来るコレクションのデータ構造として、 2分探索木（binary search tree）というものを紹介します。 2分探索木は、以下のような特徴を持つ木構造です（図1）。 2分木（各ノードは最大で2本の子を持つ）。 全ての要素が「左の子＜親≦右の子」（あるいは「左の子≦親＜右の子」）という大小関係を満たす。 2分探索木 要素の挿入・削除・検索は、 木の根から葉までの経路を1つ探索することになるので、 木の高さ分に比例する計算量が必要です。 理想的には、木のバランスが均等に整っていれば、 要素数を n として計算量は O(log n) になります。 しかしながら、逆に、 図2に示すように、木が左右どちらかに偏っている場合、 計
ハッシュテーブル
概要 ハッシュテーブル（hash table）は、 「ハッシュ値」という物を使うことによって、 要素の挿入・削除・検索を非常に高速に行うことの出来るコレクションです。 挿入する要素の数よりも、余裕を見て大きめのメモリを確保して置くならば、 要素の挿入・削除・検索をほぼ O(1) （要素数によらず一定時間）で行うことができます。 ハッシュ値 ハッシュ（hash）というのは、 文字列などの任意のデータから、そのデータを要約して得られる固定長の値のことです。 得られた値のことをハッシュ値（hash value）、 値を得る操作をハッシュ関数（hash function）といいます。 ネットワークなどを通してメッセージを送る際、 通信路でエラーが混入していないかどうかを確かめるために、 送信元と受信先の双方でハッシュ値を計算し、値を比較するのに使われたりします。 hash という言葉は、料理のハッ
ハッシュは二分木（ツリー）より速い（ハッシュとツリーの速度比較） - プログラマはサイコロを振らない
ハッシュは遅いという意見があるようだが、実装や使い方を誤らなければ、基本的にツリーよりハッシュの方が速い。 （この記事は以前書いた「ハッシュは本当に遅いのか？いや、遅くない（反語）」を簡潔にまとめたものです） ハッシュとツリーの速度を比較した結果が次のグラフだ（ハッシュはパラメータを適切に設定（後述））。挿入、参照（検索）、削除の合計時間を測定した。（横軸は要素数、縦軸は時間、横軸は対数スケール） 「ハッシュは本当に速いのか?」の検証 速いはずのハッシュが二分木にはかないません。ハッシュは速いという常識をくつがえす結果となりました。 http://www.s34.co.jp/cpptechdoc/article/hash/:itle=ハッシュは本当に速いのか? Googleで「ハッシュ 速い」で検索すると上記のページが一番上に表示される（2008-08-04現在）。しかし、このページに掲載
404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根本的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1
書評 - Programming Pearls : 404 Blog Not Found
2007年05月26日00:00 カテゴリ書評/画評/品評Code 書評 - Programming Pearls これを見たら、むしょうに紹介したくなってきたので。 Programming Pearls Jon Bentley [邦訳:珠玉のプログラミング] アンカテ(Uncategorizable Blog) - 「問題 VS. 私たち」で考える人たちソフトウエア技術者は、コンピュータを相手にするのだから、0か1か、YesかNoか、はっきり答が出る問題を扱っているのではないあと思われがちである。しかし、実はぜんぜんそうではない。本書"Programming Pearls"は、文字通り真珠のようなプログラムたちをそのまま集めた本。厳密には、私が読んだのは1st Ed.なのでこれとは微妙に異なる可能性がある(More Programming Pearlsと異なる点があることをまずお断りして
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
二分木
サービス終了のお知らせ