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

ファジープロジェクト対策 その1

5月ぐらいから着手していたプロジェクト(顧客管理ソフト)が終焉を迎え、検証段階に入ったので、記して置きたいことなど。 数ヶ月程度ですが、自分が携わったプロジェクトの中では過去最大クラスのものでした。 …

no image

シェルスクリプト ファイル読み込み・switchなど

以前のエントリーに引き続き、シェルスクリプトでログを解析する処理があってそこで覚えたことなどをまとめておきます。 Contents1 ファイル読み込み2 switch文2.1 基本パターン2.2 条件 …

no image

データのシリアライズ

おととしにJavaをやったときにでてきましたがSessionに情報を格納するときにでてきたシリアライズについて。 セッションはステートフルな状態を実現するための便利なデータの保存方法ですが、値をオブジ …

no image

ポート解放(CentOS7)

新サーバー構築をしていたときにwebサーバーとしてnginxを立てましたが、外部から接続ができません。 500エラーすら吐かれず、ログも残っていません。 こんな時はホスト自体にアクセスが届いていない可 …

no image

アプリケーションアーキテクチャについて 〜既存のMVCに関して〜

今回はアプリケーションのルーター以降のアーキテクチャに関して。主にMVCなどについて説明したいと思います。 Contents1 MVC(Model,Controller,View)1.1 トランザクシ …