「データ構造」の記事
8件 RSS で購読
8件
Jump Consistent Hash：表を持たずにシャード番号を決めるコンシステントハッシュと、その前提条件
シャードを10個から12個に増やすとき、hash mod n はキーの5/6を動かしますが、本当に動かす必要があるのは1/6です。Lamping・Veach の論文のコード、仕組み、バケットを増減したときに起きることをまとめました。
Union-Find の経路圧縮とサイズによる重み付け：α(n) はどの実装に付く計算量か
Union-Find でサイズによる重み付け、経路圧縮、経路半減が parent 配列をそれぞれどう変えるかを小さな例で追い、最悪 Θ(log n) と操作列全体の O(m α(n)) がどの実装に当てはまるかを Princeton の algs4 の資料に沿って整理しました。
Linux カーネルの rbtree：比較関数を保持せず、ノードを構造体に埋め込む赤黒木
Linux の赤黒木は比較関数を保持しません。ノードの埋め込み、自分で書く探索・挿入ループと呼び出しごとに比較関数を受け取るヘルパー、色ビット、cached・augmented 木、ロックなし探索の限界を v6.17 のソースで整理します。
スキップリスト：コイン投げで決めたレベルが O(log n) の探索を生む仕組み
ソート済み連結リストにランダムなレベルのポインタを足すと、なぜ探索が期待 O(log n) になるのか。Pugh の報告書のアルゴリズム、「期待」時間の範囲、Java ConcurrentSkipListMap のドキュメントが約束することを整理します。
ハッシュテーブルが O(1) でなくなるとき：衝突、O(n²) の挿入、ハッシュフラッディング
dict や HashMap の O(1) は期待値です。全キーのハッシュ値が同じだと n 個の挿入に少なくとも n(n−1)/2 回の比較が要る理由と、Python のハッシュランダム化と PYTHONHASHSEED、Rust の SipHash、Java の Comparable による対策をまとめました。
ブルームフィルタが「ない」ときだけ断言できる理由
ブルームフィルタが「確実にない」か「あるかもしれない」でしか答えない理由、偽陰性が出ないという保証が成り立つ条件、偽陽性の確率の式、ビットを消すと保証が崩れる理由を整理します。
ヒープはソート済みリストではない：優先度付きキューの並び順とインデックスの式
heapq や PriorityQueue を出力すると、なぜ並んでいないのか。ヒープが守る条件、0始まりの親子インデックスの式、ソート済みリストとの計算量の違い、同じ優先度の扱いを公式ドキュメントで整理します。
配列の末尾への追加はなぜ O(1) なのか：動的配列と償却計算量
満杯になると全要素をコピーすることがあるのに append が O(1) とされる理由を、容量と償却解析で説明し、Java・C++・Rust・Go のドキュメントが保証する範囲と実装が決める増加率、容量を先に確保する方法をまとめました。
該当する記事がありません。別の言葉で検索してみてください。