MySQL——辅助工具之hash

字符集和校验码没有什么可说的，这都是成熟的东西。今天看看哈希表，哈希表在数据库中使用非常频繁，所以其效率直接影响数据库的整体性能。

哈希表管理结构一般需要下面属性：

1. 存放Hash项的数组

2. Hash键偏移

3. Hash键长度

4. 计算Hash值的函数

Mysql的Hash表管理结构如下：

typedef struct st_hash {

size_t      key_offset; 关键字偏移

size_t      key_length; 关键字长度

size_t      blength;   大于Hash表中项数的最小的2^n

ulong       records;   hash表中的项数

uint       flags;     hash表标识

DYNAMIC_ARRAY array;     保存hash键的动态数组

my_hash_get_key get_key;  获取Hash键值的方法，如果不给就用key_offset计算    

void       (*free)(void *); 释放Hash项的方法

CHARSET_INFO  *charset;  字符集

} HASH;

Hash表一般还应该有下列方法：

1. 创建(Create)

2. 插入(Insert)

3. 删除(Delete)

4. 查找(Find/Search)

5. 遍历(Scan)

6. 销毁(Destroy)

Hash项管理结构：

typedef structst_hash_info {

uint next;  冲突链的索引编号

uchar *data; 当前记录的首地址

} HASH_LINK;

Mysql的Hash表利用了单数组实现法，双数组实现方法如下图所示：

单数组就是将first和next合并为同一个数组，并且将values和hash表的item项进行了合并，另外Mysql支持了动态扩展功能。Mysql的Hash表结构如下：

_my_hash_init(Create)

该函数用于初始化一个Hash表管理结构HASH。

参数：

HASH  *hash       hash表指针

uint  growth_size  动态数组的扩展大小，如果不允许扩展，这里设置为0

CHARSET_INFO *charset 字符集

ulong  size      hash表entry个数

size_t  key_offset 关键字偏移

size_t  key_length,关键字长度

my_hash_get_keyget_key, 获取关键字的方法

void  (*free_element)(void*)释放空间的方法

uint  flags  hash表标识

功能：

该函数只是将传入的参数都设置到HASH结构体上，并且将records字段设置为0，将blength字段设置成1。其实类似于创建了一个Hash表。

my_hash_key

获取关键字的方法：

if (hash->get_key)

return (char*)(*hash->get_key)(record,length,first);

*length=hash->key_length;

return (char*)record+hash->key_offset;

如果给了获取关键字的方法，就调用给定的方法获取关键字首地址和长度。否则就用key_offset来计算关键字的首地址，key_length作为关键字长度。

calc_hash

计算Hash值的方法，直接调用对应字符集的Hash计算函数。

ulong nr1=1, nr2=4;

hash->charset->coll->hash_sort(hash->charset,(uchar*) key,length,&nr1,&nr2);

return(my_hash_value_type)nr1;

这里的nr1和nr2是给定的两个种子，可能字符集的hash函数会同时计算出hash值，供解决冲突使用。

my_hash_mask

根据hash值计算Hash项的位置：

if ((hashnr &(buffmax-1)) < maxlength)

return (hashnr &(buffmax-1));

return (hashnr &((buffmax >> 1) -1));

my_hash_rec_mask

根据数据和hash表的信息，计算记录应该放的位置：

1. 调用my_hash_key计算出Hash键所在的位置

2. 调用calc_hash根据Hash键计算出Hash值

3. 调用my_hash_mask根据Hash值计算出记录的偏移

rec_hashnr

根据record计算hash值：

1. 调用my_hash_key计算Hash键所在的位置

2. 调用calc_hash计算Hash值

my_hash_insert

给Hash表插入一条记录。

1. 如果是一个唯一hash表

1. 根据record计算Hash键地址

2. 调用my_hash_search在Hash表上查找该记录，my_hash_search后面再说明

1. 找到就直接返回，否则就继续插入

2. 申请一个空的Hash节点，如果申请不到，说明没有更多的空间，直接返回失败

3. 从records减去blength/2的位置开始，递归的遍历此冲突链，将此冲突连上的数据进行重新Hash(因为Hash表扩展以后Hash表的前半部分应该做二次Hash，这个二次Hash的动作Mysql不是一次性完成，而是碰到那个就重新Hash那个的方式。)，在此过程中可能会将空的hash节点置换掉，换成以前存储过数据的位置，原来的数据被存放到空的hash节点上。

4. 计算得到记录应该插入的位置，判断该位置是否已经插入记录：

1. 如果该位置没有记录，则直接插入该位置；

2. 如果该位置已经有记录存在，则将该位置的数据移动到空的hash节点上；

3. 如果该位置是空的，则直接插入新纪录

5. 修改records和blength 

由于时间原因，先写这么多，delete、update等操作大家应该可以自己分析清楚了。