2019-12-04 22:30:37
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。
実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。
ハッシュテーブル
ハッシュ値を添え字とした配列
ハッシュの衝突処理
開番地法
衝突が生じた際に、ハッシュ関数とは別の関数を使って別の番地を求める方法。
連鎖法
衝突が生じても新しい番地を求めずに、衝突した番地に衝突したキー同士をポインタでつないだリンクリストを格納することで対応する方式。
計算時間データへのアクセス
O(1)
添字を使ってランダムアクセスが可能。
データの追加
O(1)
配列の場合は、線形探...
アルゴリズムとデータ構造
ハッシュテーブル