- [[Redis]]は分離連鎖法によるハッシュテーブルを利用していて、計算量は$O(1+n/k)$（$n$はアイテム数、$k$はバケットの個数）$n/k$ は小さく保たれるので実質$O(1)$に近似する。 - 他のディスクベースストアはディスク上のランダムI/Oを最小化する必要があることから、ランダムアクセスを要するハッシュテーブルはあまりよい構造ではない。[[B-tree]]の変種か[[LSM-tree]]の変種を利用する [How does redis claim O(1) time for key lookup?](https://stackoverflow.com/questions/15216897/how-does-redis-claim-o1-time-for-key-lookup) > To implement dictionaries (used for the main dictionary, but also for hash and set objects, and in conjunction with a skip list for zset objects), Redis use separate chaining hash tables, whose access complexity is O(1+n/k) where n is the number of items and k the number of buckets. > Redis makes sure the number of buckets grows with the number of items so that in practice n/k is kept low. This rehashing activity is done incrementally in background. When the number of items is significant, the complexity is close to O(1) (amortized). > Other stores (Cassandra for instance) are designed to store data on disk while minimizing the number of random I/Os for performance reasons. A hash table is not a good data structure for this, because it does not enforce the locality of the data (it does not benefit from buffer caching very well). So disk based stores usually use B-tree variants (most RDBMS) or log-structured merge (LSM) trees variants (Cassandra), which have O(log n) complexity. [A little internal on Redis hash table implementation | by Kousik Nath | Medium](https://kousiknath.medium.com/a-little-internal-on-redis-key-value-storage-implementation-fdf96bac7453)