連想配列

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

連想配列(れんそうはいれつ、英語: associative array)とは、コンピュータプログラミングにおいて、添え字にスカラー数値以外のデータ型(文字列型等)も使用できる配列である。抽象データ型のひとつ。連想リスト連想コンテナ辞書(あるいはカタカナでディクショナリ 英語: dictionary)、ハッシュ英語: hash)、マップ英語: map)とも呼ばれる。

歴史的には、最初に LISP の連想リストとして広く認知された。その後、SNOBOLtable として、AWK で連想配列として実装したことで、その潜在能力がさらに広く知られるようになった。現在、Ruby など一部の言語では、添え字にはどのようなデータでも使えるものもある。

概要[編集]

プログラミングにおける単純な配列は、特定のアドレスからのオフセット(ずれ)をインデックスとして、アドレスとオフセットによって目的の値を得る。これに対し連想配列では、要素とそれを紐付けできるような値(キーと呼ぶ)のペアで表され、キーによって目的の値を求める。辞書ディクショナリという呼び方は、要素を本文、キーを見出しになぞらえたものと言える。ハッシュハッシュテーブルによって実装されることによる。

データ構造[編集]

連想配列の実装に使われるデータ構造としては、主に平衡2分探索木赤黒木AVL木など)やハッシュテーブルがある。ほかにはB木や連想リスト、トライ木基数木などが利用されることもある。純粋な連想配列においてはキーの重複があってはならない。マップ(連想配列)を拡張したマルチマップはキーが重複したデータも上書きせずに保持できるデータ構造である。

連想配列を一般化したデータ構造のひとつにマルチマップ英語: Multimap)があり、一つのキーに対して複数の値を格納することができる[1]。また別の一般化である双方向マップ(英語: Bidirectional mapBidimapdouble ordered map)はバインディング操作を双方向で行う(キーと値に全単射関係をもたせる)データコンテナである。双方向マップの値それぞれが重複のないキーに関連付けられなければならない。キーを引数に取る通常の連想配列におけるlookup操作の他に値を引数にとるlookup操作が追加され、この操作は引数として与えられた値に関連付けられたキーを検索する。

よく用意される命令[編集]

純粋な連想配列でのキー–値間の参照を束縛(またはバインディングとも)と呼ぶ。「束縛」という語は新たな参照を作る過程に対しても用いられる。

しばしば定義される操作は以下のようなものが挙げられる:[2][3]

追加・挿入
新しいキー–値対を配列に追加し、キーと値の間への新たな参照を生成する。この操作(を行なう関数)の引数はキーとそれに紐付くべき値である。
再配置・置換
既存のキー–値対の値を書き換え、キーからの古い参照を新たな値への参照に再生成する。引数は元のキーと新たな値である。
除去・削除
キー–値対を配列から削除し、キーから値への参照を消去する。引数は配列から削除するキー。
検索・参照
キーに束縛されている値を取り出す。引数はキーであり、キー束縛された値が戻り値となる。紐付いた値が見付からない場合に例外を投げる実装もある。

また、連想配列はここで上げた以外の操作も含む。それは例えばキーの束縛数を特定したりすべてのキーを調べるための反復子を作成したりといったものである。この反復子によって得られる参照の順序はしばしば不定となる。

連想配列を標準で提供する主な言語[編集]

  • AWK — array["idx1"] = "val1"; array["idx2"] = "val2"のような形式で宣言し,print array["idx1"]のようにアクセスする[4]
  • GNU Bash — declare -A array=(["idx1"]="val1" ["idx2"]="val2")のような形式で宣言し,echo ${array["idx1"]}のようにアクセスする。[5]
  • C++ — 標準ライブラリのクラスstd:mapとして提供されている。これはハッシュではなく二分木により実装されている。ハッシュを使いた std::unordered_map も提供される。
  • D言語
  • ECMAScript (JavaScript) — すべてのオブジェクトが、文字列が添え字の連想配列として扱われる。MapとWeakMap型だと添え字を任意のオブジェクトにすることができる。
  • Go — map[keytype]valtype
  • korn
  • Icon
  • Java — Java Platform, Standard Edition標準パッケージのMap, HashMap, TreeMap, LinkedHashMap, Hashtable で提供。その他 Apache Commons Collections などでも提供。
  • LISP — キーとデータで構成された cons セル[6]のリストを連想配列として(car部をキーにcdr部をデータ、またはその逆)として使う関数(assoc, rassoc)が提供されている。
  • Lua — テーブルtbl = {idx1 = "val1", idx2 = "val2"}として宣言し,print(tbl["idx1"])のようにアクセスする[7]
  • .NET Framework (C#,VB.NET,F#) - System.Collections.Hashtable, System.Collections.Specialized.ListDictionary, System.Collections.Specialized.HybridDictionary, System.Collections.Generic.Dictionaryにて提供。(ただし Dictionary は CLR 2.0 以降)
  • PL/SQL — 結合配列 (Oracle Database 9i 以降)
  • PHP - 配列と連想配列の区別がない
  • Python — 辞書dict = {"idx1": "val1", "idx2": "val2"}として宣言し,print(dict["idx1"])のようにアクセスする[8]
  • Perl — %ではじまる変数が連想配列。要素には$hash{$key}としてアクセスする(通常の配列は@で宣言し、要素へは$array[$index]としてアクセス)。同言語で連想配列を(その実装から)「ハッシュ」と呼び始めたことから、「ハッシュ」が連想配列の別名として定着した。
  • REXX
  • Ruby — 組み込みのクラス Hash で提供
  • Smalltalk
  • SNOBOL
  • Swift
  • Visual Basic
  • Visual Basic for Applications

脚注[編集]

  1. ^ Goodrich & Tamassia (2006), pp. 389–397.
  2. ^ Goodrich, Michael T.; Tamassia, Roberto (2006), “9.1 The Map Abstract Data Type”, Data Structures & Algorithms in Java (4th ed.), Wiley, pp. 368–371 .
  3. ^ Mehlhorn, Kurt; Sanders, Peter (2008), “4 Hash Tables and Associative Arrays”, Algorithms and Data Structures: The Basic Toolbox, Springer, pp. 81–98 .
  4. ^ awk”. IEEE and The Open Group (2017年). 2018年11月2日閲覧。
  5. ^ Bash Reference Manual: Arrays”. LFree Software Foundation, Inc. (2008年). 2018年11月2日閲覧。
  6. ^ car, cdrと呼ばれる二つデータが組になった、2-タプルのデータ構造
  7. ^ Lua 5.3 Reference Manual”. Lua.org, PUC-Rio. (2018年). 2018年11月2日閲覧。
  8. ^ 5. データ構造 — Python 3.7.1 ドキュメント”. Python Software Foundation (2018年). 2018年11月2日閲覧。

関連項目[編集]