skillup

技術ブログ

プログラミング全般

データ構造の基礎知識 中編 ハッシュ

投稿日:

前回の続きです。

前回は配列、連結リストについて学習したので今回はハッシュについて学習します。

ハッシュとは?

key-value型のデータ構造であり、以下のような特徴を持ちます。

  • 引数を1つ与えると数値の戻り値を1つ返す
  • 同じ引数を与えた場合は必ず同じ値を返す
  • 別の引数を与えた場合はなるべく違う値を返す(理論上、同じ値をとる可能性がある)

どのようにkeyと値を管理するのか?

  1. あらかじめ配列を用意する
  2. keyを入れるとある数字を返す関数を内部で用意する
  3. keyによって変換された数字(例えば8)と対応する配列の場所(8番目)に値を入れる

ここの説明がわかりやすい
http://wa3.i-3-i.info/word11947.html

ここはかなり専門的
http://tokyo-ct.net/usr/kosaka/for_students/jissen1/akiyojissen1/kougi22.html

メリット

ある値への計算量がO(1)になる※厳密には違うが大体O(1)

デメリット

順番が保持されない

対策としてはkey自体が格納される連結リストを作っておき、順番を保持する。

衝突があり、再計算の必要がある。(リンク参照)

-プログラミング全般

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

no image

1度に1つのことを

今回のリーダブルコードの概念はやや抽象的。 要は一度に行うタスクは1つにする、というところがポイントになります。 そのための手法として下記のようなことを上げています。 コードが行っているタスクをすべて …

no image

オブジェクト指向について その2

前回のエントリーのように、データとロジックを一体で考えるのは、処理状の有効性のみならず、よりユーザー側に近い処理をかくということにもつながります。 日付の問題に関してもintやshortよりはLoca …

no image

OSコマンドインジェクション

Contents1 OSコマンドインジェクションとは?2 被害3 対策4 参考リンク OSコマンドインジェクションとは? OSに対する命令文を不正に紛れ込ませて攻撃させる手法。 被害 サーバー内のファ …

no image

変数の役割について

前回のエントリーの主眼は変数を置くことで、適切な情報量に分割し、コードを読みやすくしよう、ということでした。 今回はそれとは少し逆の観点でして、不要な変数を削除して、コードを読みやすくしよう、というこ …

no image

Webの高速化に関して

Webの高速化に関してメモ。 高速化って言っても幅広いんですけどね。自分が行なっている対策に関して。 一応LAMP環境を前提にしてます。 Contents1 一番大事なのは測定2 DB対策3 フロント …