検索

ホームページ  >  に質問  >  本文

redis字典的内部实现方式

最近在看redis的设计与实现一书,看到字典这一章节时,发现redis字典的增删改查操作的复杂度都是O(1):

对此不太懂,看了它的数据结构,感觉不应该是O(1)的复杂度,给定一个key,去查value的话如果不是定长并且有序的储存结构,怎么可能是O(1)的复杂度?

高洛峰高洛峰2868日前846

全員に返信(4)返信します

  • 伊谢尔伦

    伊谢尔伦2017-04-24 16:02:29

    下の写真はハッシュテーブルの概略図です:

    主に最適化によるもの Hash Function,尽可能的减少冲突。也就是防止不同的key映射到相同的value ですが、競合があっても問題ありません。 。 。

    参考:
    http://www.tutorialspoint.com/data_ Structures_algorithms/hash_data_structor.htm ファイアウォールを回避する必要があるかどうかはわかりません。

    追記: アルゴリズムの概要を読むことができます。 。 。

    返事
    0
  • 仅有的幸福

    仅有的幸福2017-04-24 16:02:29

    質問者はハッシュとは何かを知らないようです。最初にデータ構造の基礎を築き、それからデータ構造に基づいてredisの応用を勉強することをお勧めします。

    もちろん、ハッシュの複雑さ O(1) は平均複雑さを指し、これは最良のケースでもあり、最悪のケースも O(n) です

    返事
    0
  • 習慣沉默

    習慣沉默2017-04-24 16:02:29

    よくわかりませんが、リンクされたリストを走査する複雑さはどのようにして 1 になるのでしょうか?

    返事
    0
  • 某草草

    某草草2017-04-24 16:02:29

    いわゆる辞書はハッシュテーブルであり、ハッシュマップの追加、削除、変更の複雑さはあまり衝突することなく線形です。 ~~

    返事
    0
  • キャンセル返事