精华内容
下载资源
问答
  • 哈希表扩容
    2019-06-15 17:53:18

    (1)为什么需要扩容?
    因为常用的链地址法,loadFactor可以大于1,所以此时设计的哈希表可以无限的插入数据,但是随着数据量的增加,每一个index对应的bucket会越来越长,也就是造成了效率的降低。所以在适当的情况下需要对数组进行扩容,比如2倍。
    (2)如何进行扩容?
    可以简单的将之前的容量扩大两倍,但是在这种情况下,所有的数据项一定要同事修改(重新调用哈希函数,获取不同的位置),比如hashCode为12的数据项的时候,在length为8的时候,index=5,在长度为16的时候,index=12。这是一个耗时的过程,但是如果数组需要扩容,那么这个过程是必要的。
    (3)什么情况进行扩容?
    当loadFactor>0.75的时候,比如加吧的哈希表家室在填充因子大于0.75的时候就对哈希表进行扩容。
    (4)哈希表扩容的代码实现

    HashTable.prototype.resize=function(newlimit){
        // 先保存就得数据
        var oldStorage = this.storage
        // 重置属性
        this.storage = []
        this.count = 0
        this.limit = newlimit
    
        // 遍历
        for(var i =0;i<oldStorage.length;i++){
            var bucket = oldStorage[i]
            if(!bucket){
                continue
            }else{
                for(var j=0;j<bucket.length;j++){
                    var tuple = bucket[i]
                    this.put(tuple[0],tuple[1])
                }
            }
        }
    }
    

    在元素进行插入的时候,需要进行判断是否需要进行扩容操作

    if(this.count >  this.limit * 0.75){
        this.resize(this.limit * 2)
    }
    
    
    // 优化原本的put的实现
        HashTable.prototype.put=function(key,value){
           // 1.根据key获取index
           var index = this.hashFunc(key,this.limit)
    
           // 根据index取出对应的桶
           var bucket = this.storage[index]
           // 如果对应的位置没有桶那么就进行新创建
           if(!bucket){
             bucket = []
             this.storage[index] = bucket
           }
           // 判断是否是修改数据
           for(var i=0;i<bucket.length;i++){
             var tuple = bucket[i]  //此时bucket的每一个元素也是数组的形式
             if(tuple[0] == key){
               tuple[1] = value
               return 
             }
           }
    
           // 进行添加
           bucket.push([key,value])
           this.count += 1
    
           if(this.count >  this.limit * 0.75){
               this.resize(this.limit * 2)
           }
         }
    

    (4)哈希表缩容,在删除操作的时候,

    if(this.limit >7 && this.count < this.limit * 0.25 ){
        this.resize(Math.floor(this.limit/2))
    }
    

    优化原本的删除操作

    HashTable.prototype.remove=function(key){
        var index = this.hashFunc(key,this.limit)
        var bucket = this.storage[index]
        if(!bucket){
            return null
        }else{
            for(var i=0;i<bucket.length;i++){
                var tuple = bucket[i]
                if(tuple[0] == key){
                    // 从bucket数组中删除当前元素i
                    bucket.splice(i,1)
                    // 总数减少
                    this.count--
                    // 缩容
                    if(this.limit >7 && this.count < this.limit * 0.25 ){
                        this.resize(Math.floor(this.limit/2))
                    }
                    // 返回当前删除的元素
                    return tuple[1]
                }
            }
            return null
        }
    }
    

    对扩容进行优化,判断扩容之后是不是一个质数,如果不是质数的话,就需要寻找一个接近于2 被的质数,将这个新的质数作为新的容量。
    面试题:如何判断一个数是不是质数?
    第一种实现:通过循环,但是效率不是很高。

     function judeNum(num){
       if(typeof num != 'number'){
         return '请输入一个数字'
       }else{
         // 循环输出
         for(var i=2;i<num;i++){
           if(num % i == 0) return `${num}不是质数`
         }
         return `${num}是质数`
       }
     }
    

    第二种实现:
    如果一个数字能够被分解,那么它分解的因子一个会大于等于它本身的开平方根,一个小于等于它本身的开平方根。

    function judeNum2(num){
      if(typeof num != 'number'){
        return '请输入一个数字'
      }else{
        var temp = parseInt(Math.sqrt(num))
        for(var i=2;i<=temp;i++){
          if(num % i == 0) return `${num}不是质数`
        }
        return `${num}是质数`
      }
    }
    

    如何岁哈希表的扩容进行优化?

      // 判断当前传入数字是否是质数
      HashTable.prototype.isPrime=function(num){
        var temp = parseInt(Math.sqrt(num))
        for(var i=2;i<=temp;i++){
          if(num % i == 0) return false
        }
        return true
      }
      // 获取质数的方法
      HashTable.prototype.getPrime=function(num){
        while(!this.isPrime(num)){
          num ++
        }
        return num
      }
    

    getPrime函数的调用是在改变数组容量的地方,即是元素添加和操作删除的地方,优化原本的代码为

    if(this.count > this.limit * 0.75){
      var newSize = this.getPrime(this.limit * 2)
      this.resize(newSize)
    }
    
    更多相关内容
  • redis7.0源码阅读(三):哈希表扩容、缩容以及rehash一、哈希冲突二、哈希表扩容1.定位到相应的代码部分2.扩容条件写时复制(copy on write):fork持久化3.扩容大小三、哈希表缩容(resize)1.缩容的条件 `...

    一、哈希冲突

    当哈希值相同的时候会发生哈希冲突,可以通过拉链法,将将他们通过链表连接起来,链式哈希会产生一个问题,随着哈希表数据越来越多,哈希冲突越来越多,单个哈希桶链表上数据越来越多,查找时间复杂度退化到 O(n),查找耗时增加,效率降低
    在这里插入图片描述

    可以通过负载因子(used/size)来表述哈希冲突的激烈程度,负载因子越大,冲突越激烈。
    size表示哈希表的大小,也就是哈希桶的个数
    used表示有多少个 键值对实体(dictEntry),used越多,哈希冲突的情况越多
    在这里插入图片描述
    因此在必要时对哈希表进行扩容,将新添加的键值对,放入新的哈希桶,从而减少哈希冲突的情况

    二、哈希表扩容

    1.定位到相应的代码部分

    首先要,找到对应代码,在setCommand中主要是设置string,在这里面可以找到。
    _dictKeyIndex是为了获取要添加dict的索引位置,会出现扩容的情况
    在这里插入图片描述
    里面有_dictExpandIfNeeded这个函数,进行扩容判断和扩容

    2.扩容条件

    _dictExpandIfNeeded中判断扩容可分为3个情况

    情况1:
    rehash的时候,是不能扩容的

    情况2:
    如果第一张哈希表的大小是0,就根据初始值DICT_HT_INITIAL_SIZE(默认为4)给它扩容

    情况3:
    条件1:负载因子大于1(d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0]))
    条件2:允许扩容dict_can_resize(没有写时复制的时候)或者负载因子大于指定阈值dict_force_resize_ratio(默认为5)
    当两条件都满足,才会进行扩容

    static int _dictExpandIfNeeded(dict *d)
    {
        /* Incremental rehashing already in progress. Return. */
        if (dictIsRehashing(d)) return DICT_OK;
    
        /* If the hash table is empty expand it to the initial size. */
        if (DICTHT_SIZE(d->ht_size_exp[0]) == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    
        /* If we reached the 1:1 ratio, and we are allowed to resize the hash
         * table (global setting) or we should avoid it but the ratio between
         * elements/buckets is over the "safe" threshold, we resize doubling
         * the number of buckets. */
        if (d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0]) &&
            (dict_can_resize ||
             d->ht_used[0]/ DICTHT_SIZE(d->ht_size_exp[0]) > dict_force_resize_ratio) &&
            dictTypeExpandAllowed(d))
        {
            return dictExpand(d, d->ht_used[0] + 1);
        }
        return DICT_OK;
    }
    

    上述条件2中可以看到dict_can_resize,那什么时候会修改dict_can_resize呢?

    void dictEnableResize(void) {
        dict_can_resize = 1;
    }
    
    void dictDisableResize(void) {
        dict_can_resize = 0;
    }
    

    如果有子进程的情况下,dict_can_resize = 0
    没有子进程的情况下,dict_can_resize = 1

    /* This function is called once a background process of some kind terminates,
     * as we want to avoid resizing the hash tables when there is a child in order
     * to play well with copy-on-write (otherwise when a resize happens lots of
     * memory pages are copied). The goal of this function is to update the ability
     * for dict.c to resize the hash tables accordingly to the fact we have an
     * active fork child running. */
    void updateDictResizePolicy(void) {
        if (!hasActiveChildProcess())
            dictEnableResize();
        else
            dictDisableResize();
    }
    

    为什么会fork子进程?redis有4种持久化方案,其中3种都是通过fork来进行持久化。

    写时复制(copy on write):fork持久化

    父进程由于执行命令对页B1进行修改,指向内存中的原页B。子进程会指向页B副本(对原页B进行拷贝),来保证持久化。
    在这里插入图片描述

    3.扩容大小

    通过<<左移位运算保证是2的n次幂,扩容到大于dictEntry的数量used为止。
    注意下面的size并不是哈希桶的数量,而是d->ht_used[0] + 1,也就是dictEntry的数量

    比如:哈希表(数组)长度为4,但是里面有9个哈希键值对(dictEntry),那么应扩容到16(比9大的最小2的n次幂)

    static signed char _dictNextExp(unsigned long size)
    {
        unsigned char e = DICT_HT_INITIAL_EXP;
    
        if (size >= LONG_MAX) return (8*sizeof(long)-1);
        while(1) {
            if (((unsigned long)1<<e) >= size)
                return e;
            e++;
        }
    }
    

    三、哈希表缩容(resize)

    tryResizeHashTables中通过htNeedsResize判断受否需要缩容,需要的话就重新调整大小(缩容)dictResize

    void tryResizeHashTables(int dbid) {
        if (htNeedsResize(server.db[dbid].dict))
            dictResize(server.db[dbid].dict);
        if (htNeedsResize(server.db[dbid].expires))
            dictResize(server.db[dbid].expires);
    }
    

    1.缩容的条件 htNeedsResize

    负载因子(used/size)小于0.1就会进行缩容,默认HASHTABLE_MIN_FILL=10,把100移过来就是0.1

    比如哈希表size大小是32,那么实际used数量为3的时候,3/32<0.1那么会进行缩容

    int htNeedsResize(dict *dict) {
        long long size, used;
    
        size = dictSlots(dict);
        used = dictSize(dict);
        return (size > DICT_HT_INITIAL_SIZE &&
                (used*100/size < HASHTABLE_MIN_FILL));
    }
    

    2.如何缩容 dictResize

    int dictResize(dict *d)
    {
        unsigned long minimal;
    
        if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
        minimal = d->ht_used[0];
        if (minimal < DICT_HT_INITIAL_SIZE)
            minimal = DICT_HT_INITIAL_SIZE;
        return dictExpand(d, minimal);
    }
    

    3.什么时候需要缩容呢? databasesCron

    Cron表示定时检查的意思
    !hasActiveChildProcess()在没有子进程的时候,会尝试缩容(resize)

    void databasesCron(void) {
        /* Expire keys by random sampling. Not required for slaves
         * as master will synthesize DELs for us. */
        if (server.active_expire_enabled) {
            if (iAmMaster()) {
                activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
            } else {
                expireSlaveKeys();
            }
        }
    
        /* Defrag keys gradually. */
        activeDefragCycle();
    
        /* Perform hash tables rehashing if needed, but only if there are no
         * other processes saving the DB on disk. Otherwise rehashing is bad
         * as will cause a lot of copy-on-write of memory pages. */
        if (!hasActiveChildProcess()) {//没有子进程的时候才会进行缩容
            /* We use global counters so if we stop the computation at a given
             * DB we'll be able to start from the successive in the next
             * cron loop iteration. */
            static unsigned int resize_db = 0;
            static unsigned int rehash_db = 0;
            int dbs_per_call = CRON_DBS_PER_CALL;
            int j;
    
            /* Don't test more DBs than we have. */
            if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;
    
            /* Resize */
            for (j = 0; j < dbs_per_call; j++) {
                tryResizeHashTables(resize_db % server.dbnum);
                resize_db++;
            }
    
            /* Rehash */
            if (server.activerehashing) {
                for (j = 0; j < dbs_per_call; j++) {
                    int work_done = incrementallyRehash(rehash_db);
                    if (work_done) {
                        /* If the function did some work, stop here, we'll do
                         * more at the next cron loop. */
                        break;
                    } else {
                        /* If this db didn't need rehash, we'll try the next one. */
                        rehash_db++;
                        rehash_db %= server.dbnum;
                    }
                }
            }
        }
    }
    

    四、rehash

    1.为什么需要rehash?

    链式哈希会产生一个问题,随着哈希表数据越来越多,哈希冲突越来越多,单个哈希桶链表上数据越来越多,查找时间复杂度退化到 O(n)。
    因此redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量,让逐渐增多的 entry 元素能在更多的桶之间分散保存,减少单个桶中的元素数量,从而减少单个桶中的冲突

    2.dictRehash

    n就是移动的哈希桶是数量(从哈希表1移动到哈希表2),也就是哈希表(数组)移动槽位

    int dictRehash(dict *d, int n) {
        int empty_visits = n*10; /* Max number of empty buckets to visit. */ //最多访问n*10个空桶,否则会阻塞过长时间
        if (!dictIsRehashing(d)) return 0;
    
        while(n-- && d->ht_used[0] != 0) {
            dictEntry *de, *nextde;
    
            /* Note that rehashidx can't overflow as we are sure there are more
             * elements because ht[0].used != 0 */
            assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
            while(d->ht_table[0][d->rehashidx] == NULL) {
                d->rehashidx++;
                if (--empty_visits == 0) return 1;
            }
            de = d->ht_table[0][d->rehashidx];//要移动的哈希桶
            /* Move all the keys in this bucket from the old to the new hash HT */
            while(de) {//遍历ht0中哈希桶中每个k-v对,都进行重新哈希
                uint64_t h;
    
                nextde = de->next;
                /* Get the index in the new hash table */
                h = dictHashKey(d, de->key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
                de->next = d->ht_table[1][h];//如果一个哈希桶有多个元素就将dict接入哈希桶的头部
                d->ht_table[1][h] = de;
                d->ht_used[0]--;
                d->ht_used[1]++;
                de = nextde;
            }
            d->ht_table[0][d->rehashidx] = NULL;//删除哈希桶
            d->rehashidx++;
        }
    
        /* Check if we already rehashed the whole table... */
        if (d->ht_used[0] == 0) {
            zfree(d->ht_table[0]);
            /* Copy the new ht onto the old one */
            d->ht_table[0] = d->ht_table[1];
            d->ht_used[0] = d->ht_used[1];
            d->ht_size_exp[0] = d->ht_size_exp[1];
            _dictReset(d, 1);
            d->rehashidx = -1;
            return 0;
        }
    
        /* More to rehash... */
        return 1;
    }
    

    设置了empty_visits,最多访问n*10个空桶,否则会阻塞过长时间
    移动过来的dictEntry都是往哈希桶的链表头部插入的

    关键部分
    一般情况下, h=hash(key)%size,也就是根据哈希值取余,来确定存放在哪个哈希桶位置上。
    由于新的哈希表size都是2的n次幂,因此可以优化成h=hash(key)&(size-1)(位运算速度更快)
    rehash的时候,将哈希表1中的一个桶的每个键值对dictEntry都通过这种方式,放到哈希表2指定的哈希桶下面。

    h = dictHashKey(d, de->key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
    

    3.渐进式rehash

    如果服务器一口气,将第一个hashtable移动到第二个hashtable上,就会出现等待响应的时间过长,因此可以将一个大的任务拆分成一个个小的任务,一步一步挪,对一个哈希桶(同一个哈希桶中多个元素用一个链表保存)进行挪到第二个哈希table去,也就是每次只挪哈希表中的一个槽位(哈希桶)。

    可以看到dictRehash(d,1),参数1就是挪动的哈希桶个数为1

    static void _dictRehashStep(dict *d) {
        if (d->pauserehash == 0) dictRehash(d,1);
    }
    

    什么时候会进行渐进式rehash呢?
    当有很多命令的时候,比如增删改查的时候,需要渐进式rehash,这样响应时间就比较短。但是当空闲时间的时候,就可以进行大步大步挪了(hashtable1移动到hashtable2上)。

    4.定时任务触发rehash

    当定时任务检测到服务器空闲的时候,就可以大步移动hashtable1到hashtable2

    dictRehashMilliseconds(dict *d, int ms)就是rehash移动指定毫秒时间,dictRehash(d,100)可以看到,一次挪100个槽位(哈希桶)
    因此在指定毫秒时间内,每次挪动100个哈希桶,直到超时了为止。

    /* Rehash in ms+"delta" milliseconds. The value of "delta" is larger 
     * than 0, and is smaller than 1 in most cases. The exact upper bound 
     * depends on the running time of dictRehash(d,100).*/
    int dictRehashMilliseconds(dict *d, int ms) {
        if (d->pauserehash > 0) return 0;
    
        long long start = timeInMilliseconds();
        int rehashes = 0;
    
        while(dictRehash(d,100)) {
            rehashes += 100;
            if (timeInMilliseconds()-start > ms) break;
        }
        return rehashes;
    }
    

    5.rehash未完成的时候如何去查找数据呢

    首先在第一张哈希表查找,如果没有,然后再去第二章哈希表查找

    6.rehash结束后要做的事情

    哈希表1已经搬空了d->ht_used[0] == 0,说明rehash已经结束了
    这一步主要是将哈希表1指向哈希表2,然后将哈希表2指向的清空(也就是说把rehash后的结果全部从哈希表2还给哈希表1了)
    可以理解为哈希表1在rehash过程中,通过哈希表2临时存储rehash还未完成的结果,完成后把结果给哈希表1

    /* Check if we already rehashed the whole table... */
        if (d->ht_used[0] == 0) {
            zfree(d->ht_table[0]);
            /* Copy the new ht onto the old one */
            d->ht_table[0] = d->ht_table[1];
            d->ht_used[0] = d->ht_used[1];
            d->ht_size_exp[0] = d->ht_size_exp[1];
            _dictReset(d, 1);
            d->rehashidx = -1;
            return 0;
        }
    

    五、总结:哈希扩容和rehash

    下图是扩容和rehash的结果
    在这里插入图片描述
    放在哪个哈希桶上,取决于h=hash(key)%size

    比如:原先哈希表大小为4,新的为8
    原先对应索引为0的,新的只可能对应索引0或者4
    原先索引为2的,新的只可能是2或者6

    展开全文
  • 哈希表扩容简述

    千次阅读 2020-10-24 00:52:40
    影响哈希表扩容的因素有两个,本身的容量CapacityCapacityCapacity和负载因子LoadFactorLoadFactorLoadFactor,当前的哈希表大小大于Size>Threshold=Capacity∗LoadFactorSize>Threshold=Capacity*...

    哈希表什么时候扩容?

    影响哈希表扩容的因素有两个,本身的容量 C a p a c i t y Capacity Capacity和负载因子 L o a d F a c t o r LoadFactor LoadFactor,当前的哈希表大小大于 S i z e > T h r e s h o l d = C a p a c i t y ∗ L o a d F a c t o r Size>Threshold=Capacity*LoadFactor Size>Threshold=CapacityLoadFactor的时候,哈希表就需要扩容。
    负载因子好比我们电脑C盘比如100G,实际上在没装满100G的情况下,比如到了80-90G的时候电脑就开始卡顿,这时候就需要扩容。负载因子的值一般为0.75,如果太小,那么哈希表需要不断的扩容,扩容是个耗时的过程;如果太大,那么哈希表放满了也不不会扩容,导致冲突越来越多,解决冲突而起的链表越来越长,效率越来越低,而 0.75 这是一个折中的值,是一个比较理想的值。

    哈希表的容量一定是2^n

    比如table 是一个数组,那么如何最快的将元素 e 放入数组 ? 当然是找到元素 e 在 table 中对应的位置 index ,然后 table[index] = e; 就好了;如何找到 e 在 table 中的位置了 ? 我们知道只能通过数组下标(索引)操作数组,而数组的下标类型又是 int ,如果 e 是 int 类型,那好说,就直接用 e 来做数组下标(若 e > table.length,则可以 e % table.length 来获取下标),可 key - value 中的 key 类型不一定,所以我们需要一种统一的方式将 key 转换成 int ,最好是一个 key 对应一个唯一的 int (目前还不可能, int有范围限制,对转换方法要求也极高),所以引入了 hash 方法。拿到了 key 对应的 哈希值h 之后,我们最容易想到的对 value 的 put 和 get 操作如下:

    # put
    table[h % table.length] = value
    # get
    e = table[h % table.length]
    

    直接取模是我们最容易想到的获取下标的方法,但是最高效的方法吗 ?我们知道计算机中的四则运算最终都会转换成二进制的位运算,如下,只有 & 数是1时,& 运算的结果与被 & 数一致:

    1&1=1
    0&1=0
    1&0=0
    0&0=0
    

    对于多位也是一样:

    1010&1111=1010;      => 10&15=10;
    1011&1111=1011;      => 11&15=11;
    01010&10000=00000;   => 10&16=0;
    01011&10000=00000;   => 11&16=0;
    

    10 & 16 与 11 & 16 得到的结果一样,也就是冲突(碰撞)了,那么 10 和 11 对应的 value 会在同一个链表中,而 table 的有些位置则永远不会有元素,这就导致 table 的空间未得到充分利用,同时还降低了 put 和 get 的效率(对比数组和链表);由于是 2 个数进行 & 运算,所以结果由这两个数决定,如果我们把这两个数都做下限制,那得到的结果是不是可控制在我们想要的范围内了 ? 我们需要利用好 & 运算的特点,当右边的数的低位二进制是连续的 1 ,且左边是一个均匀的数(需要 hash 方法实现,尽量保证 key 的 h 唯一),那么得到的结果就比较完美了。低位二进制连续的 1,我们很容易想到 2 n − 1 2^n - 1 2n1; 而关于左边均匀的数,则通过 hash 方法来实现。到此就清楚了为什么大小是 2 n 2^n 2n

    我们一般扩容为原来的两倍,基本步骤如下:

    1. 创建一个新的数组,创建一个新的数组,长度newCap是原来的2倍。
    2. 遍历oldTab 取出元素的键后,重新进行hash,算出index=i = (newCap - 1) & hash
    3. 重新插入元素。
    展开全文
  • 哈希表hash的扩容

    千次阅读 2022-05-01 21:16:40
    哈希表hash的扩容字典dict的结构哈希表hash的扩容(rehash)渐进式哈希 字典dict的结构 了解hash的扩容之前,需要先了解hash的底层实现:dict。 dict所使用的哈希表由 dict.h/dictht 结构定义: typedef struct dictht...

    字典dict的结构

    了解hash的扩容之前,需要先了解hash的底层实现:dict。

    dict所使用的哈希表由 dict.h/dictht 结构定义:

    typedef struct dictht {
    
        // 哈希表数组
        dictEntry **table;
    
        // 哈希表大小
        unsigned long size;
    
        // 哈希表大小掩码,用于计算索引值
        // 总是等于 size - 1
        unsigned long sizemask;
    
        // 该哈希表已有节点的数量
        unsigned long used;
    
    } dictht;
    
    • table 属性是一个数组, 数组中的每个元素都是一个指向 dictEntry 结构(即哈希表节点)的指针, 每个 dictEntry 结构保存着一个键值对。
    • size 属性记录了哈希表的大小, 也即是 table 数组的大小, 而 used 属性则记录了哈希表目前已有节点(键值对)的数量。
    • sizemask 属性的值总是等于 size - 1 , 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

    下图展示了一个大小为 4 的空哈希表 (没有包含任何键值对)。
    在这里插入图片描述

    哈希表节点使用 dictEntry 结构表示, 每个 dictEntry 结构都保存着一个键值对:

    typedef struct dictEntry {
    
        // 键
        void *key;
    
        // 值
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
        } v;
    
        // 指向下个哈希表节点,形成链表
        struct dictEntry *next;
    
    } dictEntry;
    
    • key 属性保存着键值对中的键, 而 v 属性则保存着键值对中的值, 其中键值对的值可以是一个指针, 或者是一个 uint64_t 整数,又或者是一个 int64_t 整数。
    • next 属性是指向另一个哈希表节点的指针, 这个指针可以将多个哈希值相同的键值对连接在一次,以此来解决键冲突(collision)的问题。

    下图就展示了如何通过 next 指针, 将两个索引值相同的键 k1 和 k0 连接在一起。
    在这里插入图片描述

    Redis 中的字典由 dict.h/dict 结构表示:

    typedef struct dict {
    
        // 类型特定函数
        dictType *type;
    
        // 私有数据
        void *privdata;
    
        // 哈希表
        dictht ht[2];
    
        // rehash 索引
        // 当 rehash 不在进行时,值为 -1
        int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    
    } dict;
    

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

    • type 属性是一个指向 dictType 结构的指针, 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数, Redis会为用途不同的字典设置不同的类型特定函数。
    • privdata 属性则保存了需要传给那些类型特定函数的可选参数。 ht 属性是一个包含两个项的数组, 数组中的每个项都是一个dictht 哈希表, 一般情况下, 字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用

    除了 ht[1] 之外, 另一个和 rehash 有关的属性就是rehashidx,它记录了 rehash 目前的进度, 如果目前没有在进行 rehash , 那么它的值为 -1

    下图表示一个普通状态下的字典:
    在这里插入图片描述

    哈希表hash的扩容(rehash)

    随着操作的不断执行, 哈希表保存的键值对会逐渐地增多或者减少, 为了让哈希表的负载因子(load factor)维持在一个合理的范围之内, 当哈希表保存的键值对数量太多或者太少时, 程序需要对哈希表的大小进行相应的扩展或者收缩。

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

    1. 为字典的 ht[1] 哈希表分配空间, 这个哈希表的空间大小取决于要执行的操作以及 ht[0] 当前包含的键值对数量(也即是ht[0].used 属性的值):如果执行的是扩展操作, 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2n (2 的 n 次方幂);如果执行的是收缩操作, 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的2n
    2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面: rehash 指的是重新计算键的哈希值和索引值,然后将键值对放置到 ht[1] 哈希表的指定位置上。
    3. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 (ht[0] 变为空表), 释放 ht[0] , 将 ht[1] 设置为 ht[0] , 并在 ht[1] 新创建一个空白哈希表, 为下一次 rehash 做准备。

    渐进式哈希

    扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面, 但是, 这个 rehash 动作并不是一次性、集中式地完成的, 而是分多次、渐进式地完成的

    这样做的原因在于, 如果 ht[0] 里只保存着四个键值对, 那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1] ; 但是, 如果哈希表里保存的键值对数量不是四个, 而是四百万、四千万甚至四亿个键值对, 那么要一次性将这些键值对全部 rehash 到 ht[1] 的话, 庞大的计算量可能会导致服务器在一段时间内停止服务。

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

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

    1. 为 ht[1] 分配空间, 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。 在字典中维持一个索引计数器变量 rehashidx, 并将它的值设置为 0 , 表示 rehash 工作正式开始。
    2. 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 程序将 rehashidx 属性的值增一。
    3. 随着字典操作的不断执行, 最终在某个时间点上, ht[0] 的所有键值对都会被 rehash 至 ht[1] , 这时程序将 rehashidx 属性的值设为 -1 , 表示 rehash 操作已完成。

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

    展开全文
  • 2)哈希表往往是固定长度,当容量不够,自动扩容,但是整体上哈希表的操作仍然是o(1)时间复杂度! 3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。
  • 哈希表的扩容实现机制导语哈希表什么是哈希表...我这篇主要是想记录一下自己的学习结果,是关于不同应用情形下实现哈希表扩容的不同方案。 哈希表 什么是哈希表 哈希表是一个散列表,里面存储的是键值对(key-...
  • 哈希表扩容/缩容的实现 //哈希表扩容/缩容 HashTable.prototype.resize = function(newLimit){ //1.保存旧的数组内容 var oldStorage = this.storage //2.重置所有的属性 this.storage =[] this.count = 0 this....
  • 关于哈希表扩容的一点思考

    千次阅读 2019-01-06 20:47:20
    我们知道,选定合适的哈希表 sizesizesize 值,将会使得元素尽可能均匀的分布在哈希表上,从而减少碰撞的发生和提升哈希表的空间利用率,相反,如果选择的哈希表 sizesizesize 值不恰当,将会增加碰撞和空间利用率...
  • C++哈希表理论基础

    2022-01-09 20:38:37
    数组: 优点:已知某元素的下标值时,通过下标值的方式获取到数组中对应的元素,这种获取元素的速度是非常快的。 缺点:如果某个元素的下标值未知,而只是知道该元素在...哈希表,也称散列表,是一种以 键-值(key...
  • 哈希表实现原理、扩容机制c++

    千次阅读 2020-09-17 10:28:40
    哈希表概念和实现,C/C++实现 总结: 哈希表通过散列表实现,在存储位置和关键字之间建立一个确定的关系f,使得每个关键字key对饮一个存储位置f(key),查找时,通过这个确定的关系f,根据给定的key找到映射的位置f...
  • 哈希表的理论讲解

    2022-05-23 16:21:38
    无序关联容器:unordered_set和unordered_map,底层用链式哈希表哈希表增删查效率非常高,趋近于O(1),但是没有办法达到绝对的O(1)。 哈希表在进行大量的查询会用到,只要是有速度比较快的查询的需求,都可以...
  • 哈希表的容量为16时,那么它的threshold应该为12,当达到此阈值的时候就会扩容(但这阈值表示的是哪个我还有些疑惑,具体体现在以下问题中) 问题1:如果0、1、2、3这四个位置下面都链接了3个key指,那么此时一共...
  • 哈希表 1. 哈希表的定义 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做...
  • 文章目录前言1、哈希表与哈希函数的引入2、哈希表一、设计1、一般、通用哈希函数的设计2、默认哈希函数二、哈希冲突1、链地址法。(seperate chaining )1、1实现1.2、测试2、哈希表的动态空间优化参考 前言 1、哈希...
  • 哈希表的介绍_以Python为例

    千次阅读 2021-05-24 20:44:10
    数据结构篇——哈希表(以Python为例) 一、哈希表介绍 ​散列表(Hash table(英译), 也称哈希表(音译)),是根据关键码值(Key Value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个...
  • redis中hash扩容过程

    千次阅读 2021-06-25 07:45:59
    Redis一共支持5种数据结构,hash是其中的一种,在hash扩容的时候采用的是渐进式rehash的方式。要想深入理解渐进式rehash,首先要了解以下Redis中hash的数据结构。 哈希表节点 typedef struct dictEntry { void *key...
  • HashMap的扩容原理

    千次阅读 2021-08-08 15:24:44
    如果哈希表中的链太长,也就是哈希冲突比较高的时候,hash表的变量就会变成单链表,效率很低, 所以我们要对哈希桶/哈希表进行适当的扩容。 2.5、负载因子的作用 哈希表容易产生两种问题 ① 如果空间利用率高,那么...
  • 哈希表是一个散列表,存储着Key-Value键值对,插入和查找的复杂度均为O(1)。 java中在创建哈希表时会创建一个默认大小的数组。...在java中当实际负载因子大于默认的负载因子(0.75)时会触发扩容机制,变为原来的两倍。
  • 【HashMap扩容机制】

    千次阅读 多人点赞 2021-11-28 22:35:34
    文章目录HashMap扩容机制 本文的大概内容: HashMap扩容机制 将(k1,v1)直接放入Node类型的数组中,这个数组初始化容量是16,默认的加载因子是0.75。 HashMap有两个参数影响其性能:初始容量和加载.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 53,684
精华内容 21,473
关键字:

哈希表扩容