T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS ハッシュ関数

<<   作成日時 : 2016/01/20 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

次の話題である掲題のハッシュ関数なんですが、どうもピンと来ません。ここでは検索手法として説明されているようです。

まず最初のプログラムです。
画像

\(create(smallest,largest)\) は最小値と最大値を与えて、その \(index\) の付いたリストを生成して、初期値として各要素を \(None\) で埋めるものです。
この例では、\(最小値 = 0\)、\(最大値 = 9\) としました。
次の \(insert(intSet,e)\) は、引数で指定されたリスト中の \(index\) を指定すると、その要素を \(1\) とするものですね。
最後の はリスト中に \(index\) に相当するデータが \(1\) かどうか?を確認するプログラムです。
ここの例では、 \(5\) を \(insert\) して、 \(member\) で、\(True\) が返ってくることを確認しています。
 
ここで何を言いたいのかというと、今まではリスト中にあるデータを検索するために、ソートしたり、バイナリーサーチしていましたが、リストを作る際に、対応する \(index\) の要素を \(1\) とすることが有効であるということです。こうしておけば、リスト内に探索データがあるかどうかは、そのデータに起因する \(index\) の要素を確認すれば良いのですから、手数は \(定数\) ということになります。このような方法をハッシュ法というようです。

上の例ではデータ型が整数なので、 \(index\) に使うことが出来ましたが、文字でも出来るというのが次の例です。
画像

ここでのミソは、\(ord('single-char')\)という \(Python\) の予約関数です。
この関数は1文字のキャラクタを与えると、そのASCIIコードの十進表現を与えるものです。これを使って \(文字 → 整数\) の変換を行って、\(0〜255\) の \(index\) を持ったリストに \(1\) を埋め込んだもので、ロジックは整数型のものと同じです。

えーと、ここで出した例はハッシュ法・ハッシュ関数のとても簡単な例を示してあります。実際はもっと奥の深いものであることに注意して下さい。

今日はこの辺で。。
 

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
ハッシュ関数 T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる