发布于 2年前

Redis内部数据结构——dict词典概览

了解词典

在了解Redis如何实现dict之前,先梳理下dict特征以及使用。

词典数据结构通常用于以键值对的方式存储数据。词典存放了一组键,每个键关联一个值。词典存放的键是唯一的,通过查询词典里的键,可以获取键对应的值。如果存储重复的键,会导致新值覆盖键关联的旧值。

词典数据结构支持以下几种操作:

  • addOrUpdate(K key, V v):以键值对的形式插入数据,如果key在词典中存在,会用新值覆盖旧值。
  • search(K key):传入搜索的键作为参数,返回此键关联的值。
  • delete(K key):删除指定键的条目。

词典的实现

根据词典的特征,有哪些实现方案呢。通常的实现方法有:

  • 简单实现:以直接寻址的方式存放在有序或无序的序列中。
  • Hash Table:对词典的key做哈希,存放在哈希表中。
  • Tree:以树状数据结构实现,例如:
    • 二叉查找树
    • AVL树
    • 红黑树
    • B树
    • 平衡树

Redis词典是基于Hash Table实现,Hash Table在增删查的平均时间复杂度是O(1),只有在发生了hash code碰撞差的情况才会到O(n)。但Hash Table需要预分配存储的空间,是以空间换时间的一种方案。

大部分的编程语言也比较常用Hash Table作为词典的内部实现。

Hash Table实现词典需要考虑的要点

Hash,中文称为散列,或音译为“哈希”,它会把任何长度的输入,通过哈希算法计算得到固定长度的hash值。相同的输入通过相同的哈希算法得到的hash值是相同,且通常hash值所占用的空间比输入值要小。

Hash Table把Hash的这个特点应用到存储上,这个过程简化是:使用hash算法计算输入hash值,再把hash值映射为存储的某个位置进行存储。

如图:

<figure class="image"></figure>要高效存储查询,需要我们在这个映射的过程中考虑几点:

  1. 评估哈希算法的效率以及均衡性
    1. 哈希算法Hash Function计算要快,否在会影响存储以及查找效率
    2. 哈希算法计算得到的hash值,通过索引映射后,能够比较均匀的分配在存储上。
  2. 如何解决Hash碰撞:不同的输入计算得到的hash值可能是相同的,这种情况称为Hash碰撞。需要解决hash碰撞导致的存储位置冲突问题。
  3. 如何解决Hash Table的扩容:Hash Table一般会预分配好固定大小的存储空间,当存储不够时如何扩容。

带着这几个问题有助于我们去理解Redis的词典的实现。

Redis实现词典的数据结构

整个Redis实现词典的数据结构如图:

<figure class="image"></figure>各个数据结构说明:

  • dict:词典数据结构,它包含了两个哈希表,其中ht[0]存放数据,ht[1]用于扩容的rehash(重新hash分配空间)。reshashidx存放rehash的索引。
  • dictht:哈希表,实现了哈希的数据结构,包含用于存散列节点的数组table,数组大小size以及数组已使用索引数used。
  • dictEntry:哈希表的节点,它存放了key-value的数据以及相同存储位置索引的链表的下一节点。

在后面章节带着问题再进一步了解Redis对词典的实现。

©2020 edoou.com   京ICP备16001874号-3