マークルツリー入門 - Git・証明書の透明性・データ同期を支えるハッシュの木
約12分
データの塊をハッシュの木にまとめるマークルツリーの仕組みを、ブラウザで動くデモ付きで説明します。根のハッシュ1つで全体を表せる理由、log2(n)個のハッシュで済む包含証明、RFC 9162の0x00/0x01によるドメイン分離、Bitcoinの奇数個の扱いが招いたCVE-2012-2459、Git・Certificate Transparency・Cassandraでの使われ方までまとめます。
アルゴリズム23 件の記事
アルゴリズム の記事
CRDT と OT 入門 - 共同編集が衝突せずに収束する仕組み
約39分
Google ドキュメントや Figma のような同時編集を支える2つの考え方、Operational Transformation（OT）と Conflict-free Replicated Data Types（CRDT）を解説します。transform 関数、半束とマージの性質、G-Counter・LWW-Register・OR-Set、テキスト用の RGA・YATA・Fugue、Yjs・Automerge・Loro、トゥームストーンの注意点まで、TypeScript の動く実装付きで追います。
diff アルゴリズム徹底解説 - Myers・patience・histogram は何が違うのか
約36分
git diff の裏で動く diff アルゴリズムを、LCS と編集距離、編集グラフ、Myers の O(ND) アルゴリズム、patience diff、histogram diff の順に解説します。Python のミニ実装と、git diff --diff-algorithm の実測で「最小」と「読みやすい」が別物であることを確かめます。
LSM-Tree と B-Tree 徹底解説 - 書き込み最適化ストレージエンジンの仕組み
約41分
データベースがディスクへ書く経路を B+Tree と LSM-Tree で比較します。ページ分割・WAL・MemTable・SSTable・コンパクション・Bloom filter・RUM 予想を、RocksDB / LevelDB / PostgreSQL / Cassandra の公式ドキュメントと原論文から整理しました。
乱数の仕組み - 疑似乱数（PRNG）と暗号論的乱数（CSPRNG）を実装して確かめる
約73分
コンピュータが乱数を作る仕組みを、動くコードと実測値で解説します。線形合同法の下位ビットが周期2で交互に並ぶこと、RANDUの3点組が15枚の平面にしか乗らないこと、Mersenne Twisterの624語の出力から内部状態を復元して以降10万個の出力を完全に予測できることを実際に走らせて確かめます。V8のソースからMath.random()がxorshift128+で2の53乗通りの値を返すことを読み、ECMAScript仕様が品質を規定していないことを確認し、getrandom(2)とLinuxカーネルのChaCha20ベースCSPRNG、RDRANDとRDSEEDの違いを一次ソースで整理。sortによるシャッフルの71%の偏り、モジュロバイアス、棄却法での直し方まで実測しました。
全文検索エンジンの仕組み - 転置インデックスとBM25を実装して確かめる
約41分
全文検索エンジンの内部を、動くPythonコードと実測値で解説します。転置インデックスとposting listの構造、アナライザによるトークナイズ、TF-IDFの限界とBM25のk1・bが持つ意味、Lucene BM25Similarityの実装上の式、delta+VByteによるposting list圧縮の効果、Luceneのセグメント不変性とマージ・近リアルタイム検索、日本語における形態素解析とN-gramのトレードオフ、位置情報を使ったフレーズ検索、そしてPostgreSQL・MySQL InnoDB FULLTEXT・SQLite FTS5とLIKEの違いまで、Apache Lucene公式javadocと各DBの公式ドキュメントを一次ソースに整理します。
論理クロック入門 - Lamport クロックとベクタークロックで分散システムの順序を理解する
約40分
Lamportの1978年論文のhappens-before関係から、ベクタークロック、バージョンベクタ、HLC、SpannerのTrueTimeまで、動く実装付きで解説します。
二分探索木と平衡二分探索木 入門 - AVL木・赤黒木がなぜ必要かを実装で理解する
約45分
二分探索木（BST）と、その平衡版であるAVL木・赤黒木を解説します。左部分木は小さく右部分木は大きいという不変条件、探索・挿入・削除（子なし/子1つ/子2つの3ケース）の実装、中順走査でソート順に取り出せる性質、昇順データを入れると高さが n-1 まで退化する最悪ケースの実測、左回転と右回転、AVL木の平衡因子とLL/LR/RR/RLの4ケース、赤黒木の5つの性質と高さの上界、C++のstd::mapやJavaのTreeMap・Linuxカーネルのrbtreeといった実務での使われ方まで、実際に動かして確認したPythonコードで整理します。
トライ木（Trie）入門 - 接頭辞検索とオートコンプリートを支えるデータ構造
約31分
文字列の集合を扱うデータ構造トライ木（Trie / prefix tree）を解説します。ノードと子への枝、終端フラグという構造、挿入・検索・接頭辞検索の素朴な実装、文字列長Lに比例するO(L)という計算量とハッシュテーブルとの違い、オートコンプリート・T9予測変換・IPルーティングの最長prefix一致・スペルチェッカー・辞書式順序での列挙といった応用、圧縮トライ（radix tree / PATRICIA trie）とAho-Corasickアルゴリズムとの関係、各言語の標準ライブラリ事情まで、実際に動くPythonコードで整理します。
LRUキャッシュ入門 - ハッシュマップ+双方向連結リストでget/putをO(1)にする仕組み
約20分
LRU(Least Recently Used)キャッシュのアルゴリズムを解説。ハッシュマップと双方向連結リストを組み合わせてget/putを両方O(1)にする仕組みをPythonの自作実装で示し、Redisのeviction policyやPython標準のfunctools.lru_cache、LFU/FIFO/CLOCKとの比較まで整理します。
文字列検索アルゴリズム入門 - KMP・Boyer-Moore・Rabin-Karpを動くコードで理解する
約41分
文字列検索アルゴリズムを動くPythonコードで解説します。素朴な全探索が最悪O(nm)に落ちる理由、Rabin-Karpのローリングハッシュと衝突検証、KMPのLPS配列がテキストのポインタを戻さない仕組み、Boyer-Mooreのbad character rule・good suffix ruleとHorspool版、Z配列の線形構築とパターン検索への応用、そして前処理と検索の計算量比較表まで整理し、CPythonのstr.findが使うCrochemore-Perrinのtwo-wayアルゴリズムやgrep・ripgrepの実装事情、複数パターンのAho-Corasickにも触れます。
Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する
約32分
要素のグループ分けを管理するUnion-Find（素集合データ構造 / DSU）を解説します。find・union・sameという3つの基本操作、森による表現、素朴な実装がO(n)に劣化する理由、経路圧縮とunion by sizeという2つの最適化、Tarjanが示したならしO(α(n))という計算量、クラスカル法・連結成分の数え上げ・グリッドの島の数・サイクル検出・重み付きUnion-Findといった応用、各言語の標準ライブラリ事情まで、実際に動くPythonコードで整理します。
ヒープと優先度付きキュー入門 - O(log n)で最小・最大を取り出すデータ構造
約18分
優先度付きキューという抽象データ型と、その代表的な実装である二分ヒープを解説。完全二分木の配列表現、sift-up/sift-down、push/popがO(log n)・build-heapがO(n)といった計算量、ヒープソート、各言語の標準ライブラリ、Dijkstraやハフマン符号化・Top-K・中央値の2ヒープ法まで、Pythonコードで整理します。
二分探索(バイナリサーチ)入門 - O(log n) で探索範囲を半分ずつ狭める
約22分
二分探索(バイナリサーチ)の仕組みと、JavaScriptやPythonでの実装、無限ループやオーバーフローの落とし穴、境界を求める応用や各言語の標準ライブラリまでを、O(log n)の探索を正しく書くために解説します。
動的計画法（DP）入門 - メモ化とテーブル化で解く定番アルゴリズム
約17分
動的計画法(DP)を、部分問題の重なりと最適部分構造という2条件から解説。メモ化(トップダウン)とテーブル化(ボトムアップ)の違い、フィボナッチ・コイン・0-1ナップサック・編集距離の実装と計算量、状態と遷移の設計手順まで、初学者向けにPythonコードで具体的に整理します。
グラフ探索アルゴリズム入門 - BFS・DFS・ダイクストラと最短経路
約19分
グラフの基礎用語と表現（隣接リスト/隣接行列）から、幅優先探索(BFS)・深さ優先探索(DFS)、トポロジカルソート、重み付き最短経路（ダイクストラ・ベルマン–フォード・A*）までを、それぞれの計算量と実務での使い所を添えてPythonコード例で丁寧に解説します。
データ圧縮の仕組み 入門 - ハフマン符号・LZ77・gzip/Brotli/Zstandard
約15分
なぜデータは圧縮できるのか（冗長性とシャノンのエントロピー）から、可逆と非可逆の違い、ハフマン符号・算術符号・ANS などのエントロピー符号化、LZ77/LZ78/LZW の辞書式圧縮、DEFLATE/gzip/zlib/PNG・Brotli・Zstandard・bzip2・xz といった実世界のフォーマット、HTTP コンテンツ圧縮（gzip/br/zstd）の実務、JPEG/MP3 など非可逆の仕組み、そして「すべては縮められない」という圧縮の限界まで、RFC と原論文に沿って整理します。
ロードバランシングのアルゴリズム入門 - ラウンドロビンから最少コネクション・P2Cまで
約14分
負荷分散(ロードバランシング)の基礎を実務目線で整理します。L4とL7の違い、ラウンドロビン・加重ラウンドロビン・最少コネクション・最短応答時間・IPハッシュ・Power of Two Choices・Maglevといった主要アルゴリズムの挙動と向き不向き、nginx/HAProxy/Envoyの既定、ヘルスチェックやスティッキーセッションまで、公式ドキュメントを出典にまとめます。
ブルームフィルタとは - 少ないメモリで「たぶん在る・確実に無い」を判定する確率的データ構造
約15分
ブルームフィルタ（Bloom filter）を基礎から解説します。偽陽性はあるが偽陰性は無い性質、mビット配列とk個のハッシュ関数によるadd/query、偽陽性率と最適kの導出、O(k)の計算量、Cassandra/RocksDBなどの実運用、Counting/Scalable/Cuckooといった変種までを一次ソースで整理します。
コンシステントハッシュ法とは - 分散システムでノードを増減してもキャッシュが崩れない仕組み
約14分
コンシステントハッシュ法（Consistent Hashing）を基礎から解説します。単純な mod N ハッシュがノード数変更でほぼ全キー再配置になる問題、ハッシュリングと時計回り割り当て、仮想ノードによる負荷平準化、再配置がなぜ平均 K/N で済むのか、そして Jump Consistent Hash・Rendezvous(HRW)・Maglev といった発展、DynamoDB/Cassandra/memcached(ketama) での実運用まで、原論文を一次ソースに整理します。
ハッシュテーブルの仕組み - 衝突解決・負荷率・各言語の実装から理解する
約14分
ハッシュテーブル（連想配列・ハッシュマップ）が平均O(1)で読み書きできる仕組みを、ハッシュ関数とバケット、衝突解決（チェイン法・オープンアドレス法）、負荷率とリハッシュの順で整理します。Python・Java・Go・C++・Rustの実装の違いや、ハッシュ衝突を悪用したDoSとSipHashによる緩和まで、公式ドキュメントを一次ソースにまとめます。
ソートアルゴリズム 入門 - 計算量・安定性・実際の標準ライブラリまで
約13分
バブル・選択・挿入・マージ・クイック・ヒープソートの仕組みと計算量を、初中級エンジニア向けに整理します。安定ソートとは何か、比較を使わない計数・基数ソート、そしてPython・Java・Rust・JavaScriptの標準ライブラリが実際に採用しているTimsortやpdqsort系のアルゴリズムまで、一次情報をもとに解説します。
計算量とBig-O記法 入門 - アルゴリズムの速さを見積もる基礎
約15分
計算量（time/space complexity）とBig-O記法を、初中級エンジニア向けに直感・定義・代表オーダーの順で整理します。O(1)からO(n!)までをコード例と早見表で解説し、二分探索、最悪・平均・償却計算量、空間計算量、実務での使いどころまで、WikipediaやBig-O Cheat Sheetを一次ソースにまとめます。