communauté Apprendre Bibliothèque d'outils Loisirs
recherche
Français
Maison > base de données > tutoriel mysql > 《Redis设计与实现》[第一部分]数据结构与对象-C源码阅读（一）

《Redis设计与实现》[第一部分]数据结构与对象-C源码阅读（一）

WBOY
Libérer： 2016-06-07 14:49:39
original
1040 Les gens l'ont consulté

一、简单动态字符串SDS 关键字：空间预分配，惰性空间释放，二进制安全 C字符串不易更改，所以Redis中把C字符串用在一些无须对字符串值进行修改的地方，作为字符串字面量（String literal），比如打印日志： redisLog(REDIS_WARING, “Redis is now ready to

一、简单动态字符串SDS

关键字：空间预分配，惰性空间释放，二进制安全

C字符串不易更改，所以Redis中把C字符串用在一些无须对字符串值进行修改的地方，作为字符串字面量（String literal），比如打印日志：
redisLog(REDIS_WARING, “Redis is now ready to exit, bye bye…”);

在Redis数据库中，包含字符串的键值对在底层都是由SDS实现的。

SDS还被用作缓冲区（buffer）：AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是SDS实现的。

源码

SDS结构的定义在sds.h中：

<code class="language-C hljs cpp">    <span class="hljs-comment">/*
     * 保存字符串对象的结构
     */</span>
    <span class="hljs-keyword">struct</span> sdshdr {     
        <span class="hljs-comment">// buf 中已占用空间的长度</span>
        <span class="hljs-keyword">int</span> len;
        <span class="hljs-comment">// buf 中剩余可用空间的长度，即未使用空间</span>
        <span class="hljs-keyword">int</span> <span class="hljs-built_in">free</span>;
        <span class="hljs-comment">// 数据空间</span>
        <span class="hljs-keyword">char</span> buf[];
    };</code>
Copier après la connexion

获取一个SDS长度的复杂度为O(1)，由SDS的API在执行时自动设置和更新SDS长度，使用SDS无须进行任何手动修改长度的工作。

空间分配

SDS的空间分配策略是：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，若不满足，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，杜绝了发生缓冲区溢出的可能性。

通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略：

  • 空间预分配

空间预分配用于减少连续执行字符串增长操作所需的内存分配次数。
通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。
其中额外分配的未使用空间数量由以下公式决定： 

<code>1. 如果对SDS进行修改后，SDS的长度（即len属性的值）小于1MB，就分配和len属性同样大小的未使用空间，即len属性的值和free属性的值相同   
2. 如果对SDS进行修改之后，SDS的长度大于等于1MB，就分配1MB的未使用空间。  
</code>
Copier après la connexion
  • 惰性空间释放

惰性空间释放用于优化SDS字符串缩短操作的内存重分配操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。

SDS的API都是二进制安全的（binary-safe），所有SDS API都会以二进制的方式处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，被读取时就是什么样。

Redis用SDS的buf数组保存二进制数据而不是字符。

SDS可以兼容部分C字符串函数。

二、链表

关键字：多态

当一个列表键包含了数量比较多的元素，或是列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

integers列表键的底层实现就是一个链表，链表中的每个结点都保存了一个整数值。

除了链表之外，发布与订阅、慢查询、监视器等功能也用到了链表，Redis服务器本身还使用链表保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区（output buffer）。

源码

链表结构的定义在adlist.h中： 

<code class="language-C hljs cpp">    <span class="hljs-comment">/*
     - 双端链表节点
     */</span>
    <span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> listNode {
        <span class="hljs-comment">// 前置节点</span>
        <span class="hljs-keyword">struct</span> listNode *prev;
        <span class="hljs-comment">// 后置节点</span>
        <span class="hljs-keyword">struct</span> listNode *next;
        <span class="hljs-comment">// 节点的值</span>
        <span class="hljs-keyword">void</span> *value;
    } listNode;
    <span class="hljs-comment">/*
     *双端链表迭代器
     */</span>
    <span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> listIter {
        <span class="hljs-comment">// 当前迭代到的节点</span>
        listNode *next;
        <span class="hljs-comment">// 迭代的方向</span>
        <span class="hljs-keyword">int</span> direction;
    } listIter;
    <span class="hljs-comment">/*
     - 双端链表结构
     */</span>
    <span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> <span class="hljs-built_in">list</span> {
        <span class="hljs-comment">// 表头节点</span>
        listNode *head;
        <span class="hljs-comment">// 表尾节点</span>
        listNode *tail;
        <span class="hljs-comment">// 节点值复制函数</span>
        <span class="hljs-keyword">void</span> *(*dup)(<span class="hljs-keyword">void</span> *ptr);
        <span class="hljs-comment">// 节点值释放函数</span>
        <span class="hljs-keyword">void</span> (*<span class="hljs-built_in">free</span>)(<span class="hljs-keyword">void</span> *ptr);
        <span class="hljs-comment">// 节点值对比函数</span>
        <span class="hljs-keyword">int</span> (*match)(<span class="hljs-keyword">void</span> *ptr, <span class="hljs-keyword">void</span> *key);
        <span class="hljs-comment">// 链表所包含的节点数量</span>
        <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> len;
    } <span class="hljs-built_in">list</span>;  
</code>
Copier après la connexion

list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，dup、free和match成员则是用于实现多态链表所需的类型特定函数：

  • dup函数用于复制链表结点所保存的值
  • free函数用于释放链表结点所保存的值；
  • match函数则用于对比链表结点所保存的值和另一个输入值是否相等。

Redis的链表实现的特性如下：

  • 双端、无环、带表头指针和表尾指针、带链表长度计数器、多态

三、字典

关键字：多态，渐进式rehash，murmurhash2

Redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、改、查也是构建在对字典的操作之上的。

字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，或是键值对中的元素都是比较长的字符串时，Redis就使用字典作为哈希键的底层实现。

Redis的字典使用哈希表作为底层实现，一个哈希表里可以有多个哈希表结点，每个哈希表结点就保存了字典中的一个键值对。

源码

字典所使用的哈希表在dict.h中定义：

<code class=" hljs objectivec">    <span class="hljs-comment">/*
     * 哈希表
     * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
     */</span>
    <span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> dictht {    
        <span class="hljs-comment">// 哈希表数组，数组中的每个元素都是一个指向dictEntry结构的指针</span>
        dictEntry **table;
        <span class="hljs-comment">// 哈希表大小</span>
        <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> size;      
        <span class="hljs-comment">// 哈希表大小掩码，用于计算索引值</span>
        <span class="hljs-comment">// 总是等于 size - 1</span>
        <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> sizemask;
        <span class="hljs-comment">// 该哈希表已有节点的数量</span>
        <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">long</span> used;

    } dictht;</code>
Copier après la connexion
  • table属性是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存着一个键值对。
  • size属性记录了哈希表的大小，即是table数组的大小。
  • used属性则记录了哈希表目前已有结点（键值对的数量）
  • sizemask属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面 
<code class=" hljs d">    <span class="hljs-comment">/*
     * 哈希表节点
     */</span>
    <span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> dictEntry {      
        <span class="hljs-comment">// 键</span>
        <span class="hljs-keyword">void</span> *key;
        <span class="hljs-comment">// 值</span>
        <span class="hljs-keyword">union</span> {
            <span class="hljs-keyword">void</span> *val;
            uint64_t u64;
            int64_t s64;
        } v;
        <span class="hljs-comment">// 指向下个哈希表节点，形成链表</span>
        <span class="hljs-keyword">struct</span> dictEntry *next;

    } dictEntry;</code>
Copier après la connexion
  • key属性保存着键值对中的键
  • v属性保存键值对中的值，其中键值对中的值可以是一个指针，或是一个uint64_t整数，或是一个int64_t整数
  • next属性指向另一个哈希表结点的指针，使用链地址法解决键冲突问题。 
<code class=" hljs d">    <span class="hljs-comment">/*
     * 字典
     */</span>
    <span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> dict {
        <span class="hljs-comment">// 类型特定函数</span>
        dictType *type;

        <span class="hljs-comment">// 私有数据</span>
        <span class="hljs-keyword">void</span> *privdata;

        <span class="hljs-comment">// 哈希表</span>
        dictht ht[<span class="hljs-number">2</span>];

        <span class="hljs-comment">// rehash 索引</span>
        <span class="hljs-comment">// 当 rehash 不在进行时，值为 -1</span>
        <span class="hljs-keyword">int</span> rehashidx; <span class="hljs-comment">/* rehashing not in progress if rehashidx == -1 */</span>

        <span class="hljs-comment">// 目前正在运行的安全迭代器的数量</span>
        <span class="hljs-keyword">int</span> iterators; <span class="hljs-comment">/* number of iterators currently running */</span>

    } dict;</code>
Copier après la connexion

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的：

  • type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
  • privdata属性保存了需要传给那些类型特定函数的可选参数。
<code class=" hljs objectivec"><span class="hljs-comment">/*
 * 字典类型特定函数
 */</span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> dictType {

    <span class="hljs-comment">// 计算哈希值的函数</span>
    <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> (*hashFunction)(<span class="hljs-keyword">const</span> <span class="hljs-keyword">void</span> *key);

    <span class="hljs-comment">// 复制键的函数</span>
    <span class="hljs-keyword">void</span> *(*keyDup)(<span class="hljs-keyword">void</span> *privdata, <span class="hljs-keyword">const</span> <span class="hljs-keyword">void</span> *key);

    <span class="hljs-comment">// 复制值的函数</span>
    <span class="hljs-keyword">void</span> *(*valDup)(<span class="hljs-keyword">void</span> *privdata, <span class="hljs-keyword">const</span> <span class="hljs-keyword">void</span> *obj);

    <span class="hljs-comment">// 对比键的函数</span>
    <span class="hljs-keyword">int</span> (*keyCompare)(<span class="hljs-keyword">void</span> *privdata, <span class="hljs-keyword">const</span> <span class="hljs-keyword">void</span> *key1, <span class="hljs-keyword">const</span> <span class="hljs-keyword">void</span> *key2);

    <span class="hljs-comment">// 销毁键的函数</span>
    <span class="hljs-keyword">void</span> (*keyDestructor)(<span class="hljs-keyword">void</span> *privdata, <span class="hljs-keyword">void</span> *key);

    <span class="hljs-comment">// 销毁值的函数</span>
    <span class="hljs-keyword">void</span> (*valDestructor)(<span class="hljs-keyword">void</span> *privdata, <span class="hljs-keyword">void</span> *obj);

} dictType;</code>
Copier après la connexion
  • ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
  • rehashidx属性记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1. 
<code class=" hljs d">    <span class="hljs-comment">/*
     * 字典迭代器
     *
     - 如果 safe 属性的值为 1 ，那么在迭代进行的过程中，
     - 程序仍然可以执行 dictAdd 、 dictFind 和其他函数，对字典进行修改。
     *
     - 如果 safe 不为 1 ，那么程序只会调用 dictNext 对字典进行迭代，
     - 而不对字典进行修改。
     */</span>
    <span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> dictIterator {            
        <span class="hljs-comment">// 被迭代的字典</span>
        dict *d;

        <span class="hljs-comment">// table ：正在被迭代的哈希表号码，值可以是 0 或 1 。</span>
        <span class="hljs-comment">// index ：迭代器当前所指向的哈希表索引位置。</span>
        <span class="hljs-comment">// safe ：标识这个迭代器是否安全</span>
        <span class="hljs-keyword">int</span> table, index, safe;

        <span class="hljs-comment">// entry ：当前迭代到的节点的指针</span>
        <span class="hljs-comment">// nextEntry ：当前迭代节点的下一个节点</span>
        <span class="hljs-comment">//             因为在安全迭代器运作时， entry 所指向的节点可能会被修改，</span>
        <span class="hljs-comment">//             所以需要一个额外的指针来保存下一节点的位置，</span>
        <span class="hljs-comment">//             从而防止指针丢失</span>
        dictEntry *entry, *nextEntry;

        <span class="hljs-built_in">long</span> <span class="hljs-built_in">long</span> fingerprint; <span class="hljs-comment">/* unsafe iterator fingerprint for misuse detection */</span>
    } dictIterator;</code>
Copier après la connexion

哈希

Redis计算哈希值和索引值的方法如下：

<code class=" hljs lasso">    <span class="hljs-comment">// 使用字典设置的哈希函数，计算键key的哈希值</span>
    hash <span class="hljs-subst">=</span> dict<span class="hljs-subst">-></span><span class="hljs-keyword">type</span><span class="hljs-subst">-></span>hashFunction(key);

    <span class="hljs-comment">// 使用哈希表的sizemask属性和哈希值，计算出索引值</span>
    <span class="hljs-comment">// 根据情况不同，ht[x]可以是ht[0]或ht[1]</span>
    index <span class="hljs-subst">=</span> hash <span class="hljs-subst">&</span> dict<span class="hljs-subst">-></span>ht<span class="hljs-preprocessor">[</span>x<span class="hljs-preprocessor">]</span><span class="hljs-markup">.sizemask;</span></code>
Copier après la connexion
<code class=" hljs cpp"><span class="hljs-comment">/* ------------------------- hash functions ------------------------------ */</span>

<span class="hljs-comment">/* Thomas Wang's 32 bit Mix Function */</span>
<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> dictIntHashFunction(<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> key)
{
    key += ~(key << <span class="hljs-number">15</span>);
    key ^=  (key >> <span class="hljs-number">10</span>);
    key +=  (key << <span class="hljs-number">3</span>);
    key ^=  (key >> <span class="hljs-number">6</span>);
    key += ~(key << <span class="hljs-number">11</span>);
    key ^=  (key >> <span class="hljs-number">16</span>);
    <span class="hljs-keyword">return</span> key;
}

<span class="hljs-comment">/* Identity hash function for integer keys */</span>
<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> dictIdentityHashFunction(<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> key)
{
    <span class="hljs-keyword">return</span> key;
}

<span class="hljs-keyword">static</span> uint32_t dict_hash_function_seed = <span class="hljs-number">5381</span>;

<span class="hljs-keyword">void</span> dictSetHashFunctionSeed(uint32_t seed) {
    dict_hash_function_seed = seed;
}

uint32_t dictGetHashFunctionSeed(<span class="hljs-keyword">void</span>) {
    <span class="hljs-keyword">return</span> dict_hash_function_seed;
}

<span class="hljs-comment">/* MurmurHash2, by Austin Appleby
 * Note - This code makes a few assumptions about how your machine behaves -
 * 1. We can read a 4-byte value from any address without crashing
 * 2. sizeof(int) == 4
 *
 * And it has a few limitations -
 *
 * 1. It will not work incrementally.
 * 2. It will not produce the same results on little-endian and big-endian
 *    machines.
 */</span>
<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> dictGenHashFunction(<span class="hljs-keyword">const</span> <span class="hljs-keyword">void</span> *key, <span class="hljs-keyword">int</span> len) {
    <span class="hljs-comment">/* 'm' and 'r' are mixing constants generated offline.
     They're not really 'magic', they just happen to work well.  */</span>
    uint32_t seed = dict_hash_function_seed;
    <span class="hljs-keyword">const</span> uint32_t m = <span class="hljs-number">0x5bd1e995</span>;
    <span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> r = <span class="hljs-number">24</span>;

    <span class="hljs-comment">/* Initialize the hash to a 'random' value */</span>
    uint32_t h = seed ^ len;

    <span class="hljs-comment">/* Mix 4 bytes at a time into the hash */</span>
    <span class="hljs-keyword">const</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> *data = (<span class="hljs-keyword">const</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> *)key;

    <span class="hljs-keyword">while</span>(len >= <span class="hljs-number">4</span>) {
        uint32_t k = *(uint32_t*)data;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += <span class="hljs-number">4</span>;
        len -= <span class="hljs-number">4</span>;
    }

    <span class="hljs-comment">/* Handle the last few bytes of the input array  */</span>
    <span class="hljs-keyword">switch</span>(len) {
    <span class="hljs-keyword">case</span> <span class="hljs-number">3</span>: h ^= data[<span class="hljs-number">2</span>] << <span class="hljs-number">16</span>;
    <span class="hljs-keyword">case</span> <span class="hljs-number">2</span>: h ^= data[<span class="hljs-number">1</span>] << <span class="hljs-number">8</span>;
    <span class="hljs-keyword">case</span> <span class="hljs-number">1</span>: h ^= data[<span class="hljs-number">0</span>]; h *= m;
    };

    <span class="hljs-comment">/* Do a few final mixes of the hash to ensure the last few
     * bytes are well-incorporated. */</span>
    h ^= h >> <span class="hljs-number">13</span>;
    h *= m;
    h ^= h >> <span class="hljs-number">15</span>;

    <span class="hljs-keyword">return</span> (<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span>)h;
}

<span class="hljs-comment">/* And a case insensitive hash function (based on djb hash) */</span>
<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> dictGenCaseHashFunction(<span class="hljs-keyword">const</span> <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">char</span> *buf, <span class="hljs-keyword">int</span> len) {
    <span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span> hash = (<span class="hljs-keyword">unsigned</span> <span class="hljs-keyword">int</span>)dict_hash_function_seed;

    <span class="hljs-keyword">while</span> (len--)
        hash = ((hash << <span class="hljs-number">5</span>) + hash) + (<span class="hljs-built_in">tolower</span>(*buf++)); <span class="hljs-comment">/* hash * 33 + c */</span>
    <span class="hljs-keyword">return</span> hash;
}</code>
Copier après la connexion

当字典被用作数据库的底层实现，或是哈希键的底层实现时，Redis使用MurmurHash2算法计算键的哈希值:

  • 该算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。

为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或太少时，程序需要对哈希表的大小进行相应的扩展或收缩。

  • 哈希表的负载因子计算公式：load_factor = ht[0].used/ht[0].size

rehash

扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作来完成，Redis对字典的哈希表执行rehash的步骤如下：

  • 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（即ht[0].used属性的值）

    1. 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n（2的n次方幂）；
    2. 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n。

  • 将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。

  • 当ht[0]包含的所有键值对都迁移到ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

  • 服务器目前没有在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
  • 服务器目前正在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子大于等于5

在执行BGSAVE命令或BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这避免了不必要的内存写入操作，最大限度地节约内存。

当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。

渐进式rehash

为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢rehash到ht[1]。

以下是哈希表渐进式rehash的详细步骤：

  1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。

  2. 在字典中维持一个索引计数器变量rehashidx，值设置为0，表示rehash工作正式开始

  3. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以为，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。

  4. 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]上，这是程序将rehashidx属性的值设为-1，表示rehash操作已完成

渐进式rehash采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除、查找、更新会在两个哈希表上进行，比如现在ht[0]中查找，没找到再去ht[1]查找

在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这样保证了ht[0]包含的键值对数量只减不增，随着rehash操作的执行最终变成空表。

Étiquettes associées：
对象 数据结构 源码 阅读
source：php.cn
Article précédent：Hibernate关联映射 Article suivant：网易视频云技术分享：HBase高可用原理与实践
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Derniers numéros
Doctrine Manager tente de mettre à jour l'entité utilisateur sans aucune modification de ma part J'ai une méthode de contrôleur et je crée une méthode d'insertion pour mon entité Order qu...
Depuis 2024-04-03 14:04:06
0
1
385
Créez diverses mises en page de cartes à l'aide d'une seule grille ou de Flex : un guide pratique J'essaie de créer une mise en page de carte réactive comme celle illustrée. Ce que je fais...
Depuis 2024-04-02 21:07:36
0
2
377
Déployer Django en utilisant la base de données MySQL sur un serveur personnel J'essaie de déployer mon projet Django sur Linode. La base de données MySQL que j'utilise ...
Depuis 2024-03-31 14:44:26
0
1
371
Rubriques connexes
Plus>
Recommandations populaires
Tutoriels populaires
Plus>
Tutoriels associés
Recommandations populaires
Derniers cours
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal