原创有误请指出:
版本: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; /*
-
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为列子画一张展示图如下:
![MYSQL INNODB中hash查找表的实现](/upload/otherpic73/23130.png)
四、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(mem_alloc(sizeof(hash_table_t)));//为hash表头分配内存
-
-
-
array = static_cast(
-
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表
就不详细解释了,当然我只是对基本实现和常用的方法进行了描述,其他方面遇到再说吧。
作者微信:
网页标题:MYSQLINNODB中hash查找表的实现
链接URL:
http://bjjierui.cn/article/pigogh.html