連想リストやハッシュテーブルを連想配列の実装に用いた場合は、要素の追加はo(1)であるが、要素の削除や先頭の参照にはすべてのキーを探索しなければならないのでo("n")かかる。