redisについての混乱SISMEMBERの複雑さ

Question

redisコマンドはどのようにして "member1"を識別するためにセット全体をスキャンする必要があるので、複雑さO（1）はどれくらい複雑ですか？

Answer 1

ハッシュテーブルを使用しているためです。

セットのすべての要素は、fc5e038d38a57032085441e7fe7010b0のような32ビットの文字列にハッシュされます。 32ビットの文字列は、異なる文字列に対して常に異なっています。そして、元の文字列の長さに関わらず、ハッシュされた文字列は常に32ビット長になります。

文字列がセットに含まれているかどうかを知りたい場合は、最初に元の文字列をハッシュしてから、その32ビット文字列がそのセットに含まれているかどうかを確認します。

たとえば、 "helloworld"の32ビット文字列がfc5e038d38a57032085441e7fe7010b0である場合、 "helloworld"がセットに含まれているかどうかを確認したい場合は、fc5e038d38a57032085441e7fe7010b0がセットになっているかどうかを確認します。

辞書の中の単語を探すのと同じです。

1. Redisのf
2. RedisのをSTARTSWITHすべての文字列は、その第二チャーステップ1
3. Redisの結果からcあるステップ2の結果から、第チャー5ているすべての文字列を検索し、すべての文字列を検索し発見
4. 繰り返して繰り返します。

元の文字列の長さにかかわらず、redisは最大で32回のクエリで、元の文字列がセットに含まれているかどうかを知ることができます。

したがって、複雑さはO（1）