連想配列
連想配列の実装に使われるデータ構造としては、主に平衡2分探索木(赤黒木やAVL木など)やハッシュテーブルがある。ほかにはB木や連想リスト、トライ木、基数木などが利用されることもある。純粋な連想配列においてはキーの重複があってはならない。マップ(連想配列)を拡張したマルチマップはキーが重複したデータも上書きせずに保持できるデータ構造である。
連想配列を一般化したデータ構造のひとつにマルチマップ(英語: multimap)があり、一つのキーに対して複数の値を格納することができる。また別の一般化である双方向マップ(英語: bidirectional map、bidimap、double ordered map)はバインディング操作を双方向で行う(キーと値に全単射関係をもたせる)データコンテナである。双方向マップの値それぞれが重複のないキーに関連付けられなければならない。キーを引数に取る通常の連想配列におけるlookup操作の他に値を引数にとるlookup操作が追加され、この操作は引数として与えられた値に関連付けられたキーを検索する。
既存のキー–値対の値を書き換え、キーからの古い参照を新たな値への参照に再生成する。引数は元のキーと新たな値である。