ハッシュ表– tag –
-
コンピュータ科学 深掘り
自作KVストアで理屈を実測する — CSの到達作品
コンピュータ科学深掘りコースの到達作品です。新しい知識は足しません。これまで別々に書いてきた計算量・線形探索・ハッシュ表・衝突・LRUを、1つの小さなKVストア(キーと値の入れ物)に束ねて、自分の手で作ります。まず配列に持って線形探索する遅い版を書き、10万件で1回引くのに何マイクロ秒かかるかを実測します。次にハッシュ索引を自作して桁違いに速くなることを測り、衝突とリサイズを扱い、最後にLRUで容量を守りながらヒット率を測ります。締めは1枚の表で「計算量の予想と実測の数字が一致する」ことを確かめます。RedisやMapの中で起きているのは、これと同じことです。 -
プログラム
配列は先頭への挿入が遅い — データ構造を自作する
配列と Map があれば大抵のプログラムは書けます。それなのに教科書には連結リスト・ハッシュ表・木が必ず出てくる。理由は「それぞれ何が速くて何が遅いかが違う」からです。まず配列の先頭挿入が遅いことを10万件で実測し、連結リストを書いて逆転させ、次にハッシュ表を40行で書いて Map の中身を開け、バケツを4つに減らして衝突が O(n) に近づくところを測ります。最後に二分探索木を書き、昇順に入れると一直線に潰れて再帰が Maximum call stack size exceeded で落ちるところまで実際に起こします。OS自作のフリーリストも、自作データベースの索引も、この3つのどれかでできていました。
1