MySQL动态hash删除操作

      前一篇文章介绍了这种没有浪费空间的动态hash结构，介绍了复杂的插入过程，总体思想就是，对一个元素的掩码，如果超过了当前数组的范围，就把它暂时放到低位，等到数组的规模到达了可以放下原来那个掩码的元素的时候，这时把原来暂时放在低位的元素，重新放到属于这个元素掩码的高位，并且重新调整相同掩码的元素的next指针链表。

      说一下删除元素的过程，释放这个元素占有的空间，hash结构的实现是一个数组，一段连续的内存空间，所以删除元素只能删除这个数组的最后一个元素。删除某个hash表中的元素，首先要找到这个元素，通过元素的hash掩码和next指针找到这个元素，同时为了删除这个元素，如果这个元素有前一个元素（冲突链表中不是第一个元素），那么就把前一个元素的next指向当前元素的下一个，从而从冲突链表中去掉删除的元素。如果这个元素是冲突链表的第一个元素，就把next的数据copy到当前元素中，同时把链表中删除第二个元素。

      如图所示，hash中，a,b,c元素拥有相同的hash掩码，组成了冲突链式结构，如果删除的目标元素是b，那么需要把b的前一个元素a的next指针指到c元素，b标志为空闲位；如果删除的目标元素是a，那么就需要把b元素的数据移动到a的位置，同时标志原来b的位置为空闲位。

删除元素的过程分为几种情况：

case1：如果空闲位置就是hash数组中的最后的一个位置，那么直接释放数组的最后一个位置的空间即可

case2：如果空闲位置不是数组的最后一个元素，计算一下数组最后一个元素的hash掩码，有可能这个掩码等于当前空闲位的掩码，出现这种情况的原因是，这个元素在空闲位的元素冲突，被移动到了数组的最后以为，这种情况，只需要把数组最后一个位置的数据移动到当前的空闲位置即可，然后释放数组最后一个元素占有的空间

case3：数组最后一个元素的hash掩码不等于空闲位置的位置，那么需要想办法把一些元素移动到empty的位置上，空出数组的最后一个元素。如果最后一个元素掩码所对应的hash数组中的元素掩码不相同，那么数组最后一个元素找到这个元素掩码的起点，所以这个掩码的元素不需要在重新设置next指针，原来这个位置的元素被放到了空闲的位置，这个元素需要被前一个元素的next指针指到empty的位置，这样数组的最后一个位置就被释放出来了，直接释放数组的最后一个位置的空间即可。

case4：这种情况如果case3中数组的最后一个元素的掩码相对位置的元素，这个元素记作a，a和最后一个元素的掩码相同，这里掩码相同会有两种情况，一种可能是，无论records或者是records+1（删除操作的一开始records就减一了），最后一个元素拥的掩码和a都有相同掩码，另一种可能是a元素的掩码是这个元素的掩码加上blength/2，原因见文章1

case4-1:如果是第一种情况，就是records或者records+1都拥有相同的掩码，那么在records的时候，数组的最后一个元素掩码和pos位置的元素拥有相同的掩码，可以知道他们冲突队列是连在一起的，这时就需要把数组的最后一个元素移动到empty的位置，同时修正next指针，冲突队列连接到empty位置。这里有个特殊情况，就是records+1时，如果掩码就是records，就是对应数组的最后的一个位置，可以知道如果按照刚才的只修正next指针是不行的，因为这个冲突链表的起点就是数组的最后一位，这里如果按照records计算掩码，就会找不到pos之前的冲突链表，所以这种情况直接进入case4-2。

上图所示，这种特殊情况，需要删除的元素是a，冲突链表的结构是a->b->pos->d,如果是简单的将a换到empty的位置，那么通过pos的next指针是找不到a，b元素的，那么这时需要将pos的next指针指向a，b链表，同时在结束时把b指向post->next,这样冲突链表就完整了。

case4-2：这种情况是在hash数组最后一个元素的掩码在records和records+1时不一样，这时，可以想到hash结构在records+1时和records时是两个不同的冲突链表，在删除一个元素后，冲突链表变为了一个，需要把records+1时剩下的冲突链表后面的元素merge到pos处的链表中，处理方法就是，把hash结构最后一个元素依然是移动到empty的位置，同时把pos的next指向最后一个元素的冲突链表，这个链表最后在链接在pos的next元素上，过程类似于上图调整后的结构。

504 my_bool my_hash_delete(HASH *hash, uchar *record)
505 {
506   uint blength,pos2,idx,empty_index;
507   my_hash_value_type pos_hashnr, lastpos_hashnr;
508   HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
509   DBUG_ENTER("my_hash_delete");
510   if (!hash->records)
511     DBUG_RETURN(1);
512
513   blength=hash->blength;
514   data=dynamic_element(&hash->array,0,HASH_LINK*); //取得hash结构的第一个元素的地址
515   /* Search after record with key *///取得record的掩码
516   pos= data + my_hash_mask(rec_hashnr(hash, record), blength, hash->records);
517   gpos = 0;
518
519   while (pos->data != record)//从冲突链中查询record
520   {
521     gpos=pos;
522     if (pos->next == NO_RECORD)
523       DBUG_RETURN(1);                   /* Key not found */
524     pos=data+pos->next;
525   }
526 //records减一
527   if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1;
528   lastpos=data+hash->records;//取得hash结构中最后一个元素的位置
529
530   /* Remove link to record */
531   empty=pos; empty_index=(uint) (empty-data);//记录empty的位置
532   if (gpos)
533     gpos->next=pos->next;               /* unlink current ptr */ //从冲突链表中删除record
534   else if (pos->next != NO_RECORD)
535   {
536     empty=data+(empty_index=pos->next);
537     pos->data=empty->data;
538     pos->next=empty->next;
539   }
540 //如果空闲位就是最后一位，直接释放数组最后一个地址空间就可以，case1
541   if (empty == lastpos)                 /* last key at wrong pos or no next link */

541   if (empty == lastpos)                 /* last key at wrong pos or no next link */
542     goto exit;
543
544   /* Move the last key (lastpos) */
545   lastpos_hashnr=rec_hashnr(hash,lastpos->data);//重新计算最后一个位置的hash值
546   /* pos is where lastpos should be */
547   pos= data + my_hash_mask(lastpos_hashnr, hash->blength, hash->records);//计算掩码//如果空闲位是最后以为掩码的位置，case2
548   if (pos == empty)                     /* Move to empty position. */
549   {
550     empty[0]=lastpos[0];
551     goto exit;
552   }
553   pos_hashnr=rec_hashnr(hash,pos->data);
554   /* pos3 is where the pos should be */  //计算pos位的hash掩码
555   pos3= data + my_hash_mask(pos_hashnr, hash->blength, hash->records);
556   if (pos != pos3)//如果pos位的元素掩码不等于pos，case3
557   {                                     /* pos is on wrong posit */
558     empty[0]=pos[0];                    /* Save it here */
559     pos[0]=lastpos[0];                  /* This should be here */
560     movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
561     goto exit;
562   }//计算数组最后一位的掩码（records等于减一之前的值），case4
563   pos2= my_hash_mask(lastpos_hashnr, blength, hash->records + 1);
564   if (pos2 == my_hash_mask(pos_hashnr, blength, hash->records + 1))
565   {                                     /* Identical key-positions */
566     if (pos2 != hash->records)//进入case4-1
567     {
568       empty[0]=lastpos[0];
569       movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
570       goto exit;
571     }
572     idx= (uint) (pos-data);             /* Link pos->next after lastpos */
573   }
          //case4-2
574   else idx= NO_RECORD;          /* Different positions merge */
575
576   empty[0]=lastpos[0];
577   movelink(data,idx,empty_index,pos->next);
578   pos->next=empty_index;
579
580 exit:

总结：动态hash结构删除元素，总体目标就是，找到删除的元素，然后删除它所在冲突链表的位置，移动一些元素，想办法将数组最后一个元素移动到刚才删除元素的地方，同时还要保持冲突链表的完整性，比较重要的一点就是由于records的减小，一些元素的掩码在原来不同的情况下，现在变成掩码相同了，这时候需要合并冲突链表。