共计 4818 个字符，预计需要花费 13 分钟才能阅读完成。
MySQL 版本：5.7.14
源码位置为 hash0hash.h hash0hash.cc
作为一种时间复杂度最优为 O(1)的数据结构，但是最坏时间复杂对位 O(n)的一种数据结构，但是在良好的设计 hash 函数的情况下性能还是非常好的。关于 hash 表的图在最后给出。在 innodb 中各种数据结构都使用 hash 表查找比如 LOCK_T 结构，还有我们特别熟悉的自适应 hash 索引等等，下面我们进行一些探讨。
一、innodb hash 函数
首先我们不得不研究一下 innodb 的 hash 函数,hash 函数的设计至少有 2 个要求
1、计算简单，否则如果计算花费了太多时间你的 hash 查找表也是不成功的
2、计算能够尽可能的分散值
那么 innodb 是如何设计这个 hash 函数的呢？很简单如下：
ulint
ut_hash_ulint(
/*==========*/
ulint key, /*!< in: value to be hashed */
ulint table_size) /*!< in: hash table size */
{
ut_ad(table_size);
key = key ^ UT_HASH_RANDOM_MASK2;
return(key % table_size);
}
上层调用为
ulint
hash_calc_hash(
/*===========*/
ulint fold, /*!< in: folded value */
hash_table_t* table) /*!< in: hash table */
{
ut_ad(table);
ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
return(ut_hash_ulint(fold, table->n_cells));
}
可以看到这里实际上和你的键值和你 hash 的 cells(桶数量)，我们看到这里做了一个异或操作然后和 cells(桶数量)进行取模操作，非常简单实用。
二、处理冲突
hash 表避免不了冲突，而数据库中往往也利用这一点，将多个链表合并起来，innodb 当然也就采用了链表的方式来处理冲突。那么言外之意每一个数据结构中必须包含一个如普通链表中 data_struct* next 的指针，当然这里也可以用 void* 泛型指针，我们来看看 lock_t 结构体中：
hash_node_t hash; /*!< hash chain node for a record lock */
确实如此。这也是单项链表实现的基础。
三、HASH 表头
一个 hash 表当然需要一个 hash 表头这个表头指向了具体的 cell 数组(内存相似但在 heap 空间不再栈上)，
innodb 中如下，我去掉了一些用处不大的：
struct hash_table_t {
enum hash_table_sync_t type; /*<! type of hash_table. */
ulint n_cells;/* number of cells in the hash table */
hash_cell_t* array; /*!< pointer to cell array */
mem_heap_t* heap;
};
可以看到 hash_cell_t* array; 就是这样一个元素，他实际上就是 hash_cell_t 就是一个元素 void*。
typedef struct hash_cell_struct{
void* node; /*!< hash chain node, NULL if none */
} hash_cell_t;
那么通过这个元素他能够指向具体的 hash 表了。那么 user_str(用户自己的结构体)->array->node 就指向了一个
具体 cell 的地址了，后面的只是地址指针 ++ 就可以了。那么我们 user_str 也至少包含这样一个
hash_table_t* 的指针来指向整个 hash 表，确实如此在 innodb lock_sys_t 中包含了
hash_table_t* rec_hash
那么我们可以 lock_sys_t 和 lock_t 为列子画一张展示图如下：
四、hash 表的建立
这里主要涉及到 cell 的计算，计算函数为 ut_find_prime，这里不用太多解释
hash_create(
/*========*/
ulint n) /*!< in: number of array cells */
{
hash_cell_t* array;
ulint prime;
hash_table_t* table;
prime = ut_find_prime(n);// 计算 cell 桶的数量
table = static_cast<hash_table_t*>(mem_alloc(sizeof(hash_table_t)));// 为 hash 表头分配内存
array = static_cast<hash_cell_t*>(
ut_malloc(sizeof(hash_cell_t) * prime));// 为 hash 表分配内存
/* The default type of hash_table is HASH_TABLE_SYNC_NONE i.e.:
the caller is responsible for access control to the table. */
table->type = HASH_TABLE_SYNC_NONE;
table->array = array;//hash 表头指向 hash 表
table->n_cells = prime;// 设置
table->heap = NULL;
ut_d(table->magic_n = HASH_TABLE_MAGIC_N);
/* Initialize the cell array */
hash_table_clear(table); //memset 0x00 整个 hash 表
return(table);
}
注意：下面都是通过 LOCK 部分 hash 表的实现来注释的，其他其实也是一样的。
五、插入一个元素
这部分是通过宏定义来做的如下，我写了详细的解释
/*******************************************************************//**
Inserts a struct to a hash table. */
/*
HASH_INSERT(lock_t, hash, lock_sys->rec_hash,lock_rec_fold(space, page_no), lock);
TYPE=lock_t: 代表数据类型
NAME=hash: 代表 lock_t 下面有一个 hash 元素指针，其实这个指针和我们平时用的链表的 struct* NEXT 没什么区别
唯一区别就是他是 void* 的
(hash_node_t hash;
typedef void* hash_node_t;)
TABLE=lock_sys->rec_hash: 代表 hash 表的地址指针, 输入参数
(hash_table_t* rec_hash;)
FOLD=lock_rec_fold(space, page_no): 函数 lock_rec_fold 通过表空间和页号得到一个 unsigned long 数字
DATA=lock: 这实际上就是你的数据的指针，当然这里就是 lock_t* 输入参数
*/
#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
do {\
hash_cell_t* cell3333;\// 实际上就是 void*
TYPE* struct3333;\ //lock_t* struct3333;
\
HASH_ASSERT_OWN(TABLE, FOLD)\// 断言不考虑
\
(DATA)->NAME = NULL;\//lock->hash = NULL;
\
cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
\
if (cell3333->node == NULL) {\ // 如果为 NULL 没有元素挂载到这个 cell 下
cell3333->node = DATA;\ // 则我们挂载到这个 cell 下
} else {\
struct3333 = (TYPE*) cell3333->node;\ // 否则说明有元素了取到这个元素的指针 lock_t* struct3333 = (lock_t*)cell3333->node;
\
while (struct3333->NAME != NULL) {\ // 如果 struct3333->hash 不等于 NULL 说明他下面有元素了
\
struct3333 = (TYPE*) struct3333->NAME;\ // 那么我们需要做的是指针像链表下一个元素移动
}\
\
struct3333->NAME = DATA;\ // 最后找到链表末尾 将数据节点挂载到下面 struct3333->hash = lock(lock 是 lock_t*)
}\
} while (0)
六、删除一个元素
这部分也是通过宏定义来做的如下，我写了详细的解释
/*******************************************************************//**
Deletes a struct from a hash table. */
/*
有了上面基础也就比较简单了，这里直接在代码进行注释
HASH_DELETE(lock_t, hash, lock_sys->rec_hash,lock_rec_fold(space, page_no), in_lock);
*/
#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
do {\
hash_cell_t* cell3333;\// 实际上就是 void*
TYPE* struct3333;\ //lock_t* struct3333;
\
HASH_ASSERT_OWN(TABLE, FOLD)\// 断言不考虑
\
cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\// 通过函数 hash_get_nth_cell 计算这个值在哪个 cell 也就是 hash 桶中
\
if (cell3333->node == DATA) {\ // 地址比较，如果地址相同其地址必然相同
HASH_ASSERT_VALID(DATA->NAME);\// 断言不考虑
cell3333->node = DATA->NAME;\// 如果找到 将指针移动到下一个元素 言外之意这里去掉了一个内存单元就是找到的那个
} else {\
struct3333 = (TYPE*) cell3333->node;\ // 链表循环找
\
while (struct3333->NAME != DATA) {\
\
struct3333 = (TYPE*) struct3333->NAME;\
ut_a(struct3333);\
}\
\
struct3333->NAME = DATA->NAME;\ // 最终找到 就做 链表去掉这个内存元素动作
}\
// 最终这里涉及到一个问题就是释放问题，但是注意虽然这个数据的指针在链表中去掉了，但是指针本身还在，可以拿到做 free 即可
HASH_INVALIDATE(DATA, NAME);\ //debug 版本使用不考虑
} while (0)
七、其他
其他函数还包含：
HASH_SEARCH_ALL: 宏实现在整个 hash 表中查找一个元素，相当于真个 cell 个链表查找
HASH_SEARCH: 宏实现在有建值的情况下查找一个元素、言外之意 cell(桶) 确定了，相当于链表查找
hash_table_clear: 清空一个 hash 表
就不详细解释了，当然我只是对基本实现和常用的方法进行了描述，其他方面遇到再说吧。
本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-07/145474.htm
