skillup

技術ブログ

プログラミング全般

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

投稿日:2016年3月24日 更新日:

前回の続きです。

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

ハッシュとは?

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

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

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

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

ここの説明がわかりやすい
わわわIT用語辞典 ハッシュテーブル (hash table)

メリット

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

デメリット

順番が保持されない

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

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

-プログラミング全般

執筆者:


comment

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

関連記事

no image

バッチスクリプトで気をつけたい点

実務でバッチ処理を作る際に気をつけるべきと思ったこと。 基本的にエラーをいかに捉えていかにログに吐くかを最初に考える。まずはエラーありき。失敗するもの、想定した値がこない、あるいは値がないを前提として …

no image

自動テストをやる上で今まで障害だったこと

自動テストについて、考え方自体は5年以上前から知っていましたが、プロジェクトで実際に使われているのを見たのは今年4月になってからでした・・・ 自動テスト完備なんて昔は夢物語だと思ってたんですけどね・・ …

no image

データ構造の基礎知識 前編 メモリとポインタ、配列と連結リスト

WEB+DB(vol91)で使えそうな連載記事がありますのでブログにメモリます。 テーマはデータ構造です。 Contents1 データ構造とは?2 計算量3 プログラムとメモリ4 配列について4.1 …

no image

JWT(ジョット)の認証に関して

セッションやtokenを使った、認証について色々書いてきましたが、今回はJWTを使った認証について。 Contents1 以前の認証がらみの記事2 JWT(ジョット)とは?2.1 ヘッダー2.2 クレ …

no image

制御フローについて

リーダブルコード 7章。制御フロー(if文などの条件分岐)について ここらへんは個人個人癖がついているとおもいますが、確かに読みやすい、読みにくいというのはあるのでなるべく汎用性のある規則を身につけた …

アーカイブ