ChainedHashTable

リストの配列を使う。配列のそれぞれの要素がリストになってる。配列にはハッシュを使ってアクセスする。

新幹線が0~15号車まであって、「田中さん？田中さんなら8号車にいますよ」がすぐに分かったら、あとは8号車を探すだけで目的の田中さんが見つかる…みたいな仕組み

ハッシュテーブルに追加する要素の数をnとするとき、配列の長さをn以上にすると、一つのリストに含まれる要素の平均個数は1以下になるので、追加する時のハッシュ計算がうまくいけば（全要素が均等にそれぞれのリストに追加されれば）計算量がO(1)になる。すごい

でもハッシュが最悪で一つのリストに集中するとO(N)になる

配列の長さをn以上にするといいことが多いので、実装等では「配列の長さ>要素数か？」を確認しつつ、もしそうでなければ配列の長さを2倍にして再構成する…みたいにすると良い 拡張にかかる償却実行時間は定数になります