Mysql源码学习——没那么简单的Hash(7)

    你可能要问我怎么有两个？其实这和我们平时使用的差不多，第一个函数my_hash_key是根据我们的值进行Hash Key计算，一般我们在计算后，会对hash key进行一次模运算，以便计算结果在我们的bucket中。即my_hash_key的结果作为my_hash_mask的第一个输入参数。其实到这里都是非常好理解的，唯一让我蛋疼的是my_hash_mask的实现，其计算结果是和第二和第三个参数有关，即Hash结构体中的blength和records有关。动态变化的，我去..

看到这里我迷惑了，我上网经过各种百度，谷歌，终于让我找到了一封Mysql Expert的回信：

Hi!

"Yan" == Yan Yu <yan2...@facebook.com> writes:

Yan> Dear MySQL experts:

Yan>      Thank you so much for your reply to my previous Qs, they are very 

Yan> helpful!

Yan>      Could someone please help me understand function my_hash_insert() 

Yan> in mysys/hash.cc?

Yan> what are lines 352 -429 trying to achieve?  Are they just some 

Yan> optimization to shuffle existing

Yan> hash entries in the table (since the existing hash entries may be in 

Yan> the wrong slot due to chaining

Yan> in the case of hash collision)?

<strong><font color="#ff0000">The hash algorithm is based on dynamic hashing without empty slots.</font></strong>

This means that when you insert a new key, in some cases a small set

of old keys needs to be moved to other buckets.  This is what the code

does.

Regards,

Monty

      红色注释的地方是重点，dynamic hash，原来如此，动态hash，第一次听说，在网上下了个《Dynamic Hash Tables》的论文，下面图解下基本原理。

<a href=http://www.2cto.com/uploadfile/2011/1214/20111214021339214.png"><img title="image" style="border-top-width: 0px; display: block; border-left-width: 0px; float: none; border-bottom-width: 0px; margin-left: auto; margin-right: auto; border-right-width: 0px" height="910" alt="image" src=http://www.2cto.com/uploadfile/2011/1214/20111214021339854.png" width="570" border="0"></a>