MYSQL INNODB中hash查询表的实现

发布时间：2023-04-28 10:21:36 所属栏目：MySql教程来源：

导读：作为一种时间复杂度最优为O(1)的数据结构，但是最坏时间复杂对位O(n)的一种数据结构，但是在良好的设计hash函数的情况下性能还是非常好的。关于hash表的图在最后给出。在innodb中各种数据结构都使用hash表查找比如LO

作为一种时间复杂度最优为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的地址了，后面的只是地址指针++就可以了。

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)

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!