Hash链表的应用比较常见，其目的就是为了将不同的值映射到不同的位置，查找的时候直接找到相应的位置，而不需要传统的顺序遍历或是二分查找，从而达到减少查询时间的目的。常规的hash是预定义一定的桶(bucket)，规定一个hash函数，然后进行散列。然而Mysql中的hash没有固定的bucket，hash函数也是动态变化的，本文就进行非深入介绍。
基本结构体
Hash的结构体定义以及相关的函数接口定义在include/hash.h和mysys/hash.c两个文件中。下面是HASH结构体的定义。
typedef struct st_hash {
size_t key_offset,key_length; /* Length of key if const length */
size_t blength;
ulong records;
uint flags;
DYNAMIC_ARRAY array; /* Place for hash_keys */
my_hash_get_key get_key;
void (*free)(void *);
CHARSET_INFO *charset;
} HASH;
| 成员名 | 说明 |
| key_offset | hash时key的offset，在不指定hash函数的情况下有意义 |
| key_length | key的长度，用于计算key值 |
| blength | 非常重要的辅助结构，初始为1，动态变化，用于hash函数计算，这里理解为bucket length（其实不是真实的bucket数） |
| records | 实际的记录数 |
| flags | 是否允许存在相同的元素，取值为HASH_UNIQUE(1)或者0 |
| array | 存储元素的数组 |
| get_key | 用户定义的hash函数，可以为NULL |
| free | 析构函数，可以为NULL |
| charset | 字符集 |
HASH结构体里面包含了一个动态数组结构体DYNAMIC_ARRAY，这里就一并介绍了。其定义在include/my_sys.h中。
typedef struct st_dynamic_array
{
uchar *buffer;
uint elements,max_element;
uint alloc_increment;
uint size_of_element;
} DYNAMIC_ARRAY;
| 成员名 | 说明 |
| buffer | 一块连续的地址空间，用于存储数据，可以看成一个数组空间 |
| elements | 元素个数 |
| max_element | 元素个数上限 |
| alloc_increment | 当元素达到上限时，即buffer满时，按照alloc_increment进行扩展 |
| size_of_element | 每个元素的长度 |
初始化函数
Hash初始化函数对外提供两个，my_hash_init和my_hash_init2，其区别即是否定义了growth_size（用于设置DYNAMIC_ARRAY的alloc_increment）。代码在mysys/hash.c中。
#define my_hash_init(A,B,C,D,E,F,G,H) \
_my_hash_init(A,0,B,C,D,E,F,G,H)
#define my_hash_init2(A,B,C,D,E,F,G,H,I) \
_my_hash_init(A,B,C,D,E,F,G,H,I)
/**
@brief Initialize the hash
@details
Initialize the hash, by defining and giving valid values for
its elements. The failure to allocate memory for the
hash->array element will not result in a fatal failure. The
dynamic array that is part of the hash will allocate memory
as required during insertion.
@param[in,out] hash The hash that is initialized
@param[in] charset The charater set information
@param[in] size The hash size
@param[in] key_offest The key offset for the hash
@param[in] key_length The length of the key used in
the hash
@param[in] get_key get the key for the hash
@param[in] free_element pointer to the function that
does cleanup
@return inidicates success or failure of initialization
@retval 0 success
@retval 1 failure
*/
my_bool
_my_hash_init(HASH *hash, uint growth_size, CHARSET_INFO *charset,
ulong size, size_t key_offset, size_t key_length,
my_hash_get_key get_key,
void (*free_element)(void*), uint flags)
{
DBUG_ENTER("my_hash_init");
DBUG_PRINT("enter",("hash: 0x%lx size: %u", (long) hash, (uint) size));
hash->records=0;
hash->key_offset=key_offset;
hash->key_length=key_length;
hash->blength=1;
hash->get_key=get_key;
hash->free=free_element;
hash->flags=flags;
hash->charset=charset;
DBUG_RETURN(my_init_dynamic_array_ci(&hash->array,
sizeof(HASH_LINK), size, growth_size));
}
可以看到，_my_hash_init函数主要是初始化HASH结构体和hash->array（DYNAMI