ハッシュテーブル
追加した順序で要素を列挙する実装方法として、各エントリに追加順を保持するリンクリストのポインタを別に持たせ、列挙する際はそちらのポインタをたどる方法がある。検索・追加操作のみならば単方向リストで実現可能だが、削除操作もサポートする場合は双方向リストで実装しなければO(1)での操作を実現できない。JavaのLinkedHashMapはこの実装であり、その他言語でも利便性からハッシュテーブルが標準で追加順を保証している事がある。欠点として、各エントリに別のリンクリスト用ポインタが必要なためにメモリ消費量が増加する。
ハッシュテーブルはエントリの数が配列のサイズに近づくほど衝突の確率が高くなり、性能が悪化してしまう。この比率をload factor(座席利用率)と呼び、n/Nの形で表す。nはエントリの数、Nは配列のサイズを指す。
連鎖法の場合はload factorの増加に対して線形に性能が悪化する。しかし開番地法の場合は衝突したキーが配列の空いた番地に格納されるため、load factorが0.8を超える付近で性能が急激に悪化する。
この問題を回避するため、load factorが一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。この操作はすべての要素のハッシュ値を再計算して新たなハッシュテーブルに格納するためO(n)であるが、配列のサイズを指数的に拡張する事で、動的配列の末尾追加操作と同様に償却解析によって計算量をO(1)とみなす事ができる。
より単純な回避方法として、あらかじめ想定されるエントリの数に対して十分に大きなサイズの配列を用意する方法もあるが、エントリの数を事前に想定できない場合には適用できない。