MYSQL INNODB中hash查找表的实现

灰太狼 2022-01-31 07:25 94阅读 0赞

原创有误请指出：  
  
版本：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函数的呢？很简单如下：

点击(此处)折叠或打开

1.  ulint  
    
2.  ut\_hash\_ulint(  
    
3.  /\*==========\*/  
    
4.  ulint key, /\*!< in: value to be hashed \*/  
    
5.  ulint table\_size) /\*!< in: hash table size \*/  
    
6.  \{   
    
7.  ut\_ad(table\_size);  
    
8.  key = key ^ UT\_HASH\_RANDOM\_MASK2;  
    
9.  return(key % table\_size);  
    
10. \}

上层调用为

点击(此处)折叠或打开

1.  ulint  
    
2.  hash\_calc\_hash(  
    
3.  /\*===========\*/  
    
4.  ulint fold, /\*!< in: folded value \*/  
    
5.  hash\_table\_t\* table) /\*!< in: hash table \*/  
    
6.  \{   
    
7.  ut\_ad(table);  
    
8.  ut\_ad(table\->magic\_n == HASH\_TABLE\_MAGIC\_N);  
    
9.  return(ut\_hash\_ulint(fold, table\->n\_cells));  
    
10. \}

可以看到这里实际上和你的键值和你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中如下，我去掉了一些用处不大的：

点击(此处)折叠或打开

1.  struct hash\_table\_t \{   
    
2.  enum hash\_table\_sync\_t type; /\*<! type of hash\_table. \*/  
    
3.  ulint n\_cells;/\* number of cells in the hash table \*/  
    
4.  hash\_cell\_t\* array; /\*!< pointer to cell array \*/  
    
5.  mem\_heap\_t\* heap;  
    
6.  \};

可以看到hash\_cell\_t\* array;就是这样一个元素，他实际上就是hash\_cell\_t就是  
一个元素void\*。

点击(此处)折叠或打开

1.  typedef struct hash\_cell\_struct\{   
    
2.  void\* node; /\*!< hash chain node, NULL if none \*/  
    
3.  \} 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为列子画一张展示图如下：  
![img_7f135c247a2e0dd65fcc9f2263072cd0.png][]  
四、hash表的建立  
这里主要涉及到cell的计算，计算函数为ut\_find\_prime，这里不用太多解释

点击(此处)折叠或打开

1.  hash\_create(  
    
2.  /\*========\*/  
    
3.  ulint n) /\*!< in: number of array cells \*/  
    
4.  \{   
    
5.  hash\_cell\_t\* array;  
    
6.  ulint prime;  
    
7.  hash\_table\_t\* table;  
    
8.    
    
9.    
    
10. prime = ut\_find\_prime(n);//计算cell桶的数量  
    
11.   
    
12.   
    
13. table = static\_cast<hash\_table\_t\*>(mem\_alloc(sizeof(hash\_table\_t)));//为hash表头分配内存  
    
14.   
    
15.   
    
16. array = static\_cast<hash\_cell\_t\*>(  
    
17. ut\_malloc(sizeof(hash\_cell\_t) \* prime));//为hash表分配内存  
    
18.   
    
19.   
    
20. /\* The default type of hash\_table is HASH\_TABLE\_SYNC\_NONE i.e.:  
    
21. the caller is responsible for access control to the table. \*/  
    
22. table\->type = HASH\_TABLE\_SYNC\_NONE;  
    
23. table\->array = array;//hash表头指向hash表  
    
24. table\->n\_cells = prime;//设置  
    
25. table\->heap = NULL;  
    
26. ut\_d(table\->magic\_n = HASH\_TABLE\_MAGIC\_N);  
    
27.   
    
28. /\* Initialize the cell array \*/  
    
29. hash\_table\_clear(table); //memset 0x00整个hash表  
    
30.   
    
31. return(table);  
    
32. \}

注意：下面都是通过LOCK部分hash表的实现来注释的，其他其实也是一样的。  
五、插入一个元素  
这部分是通过宏定义来做的如下，我写了详细的解释

点击(此处)折叠或打开

1.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*//\*\*  
    
2.  Inserts a struct to a hash table. \*/  
    
3.  /\*  
    
4.  HASH\_INSERT(lock\_t, hash, lock\_sys\->rec\_hash,lock\_rec\_fold(space, page\_no), lock);  
    
5.    
    
6.    
    
7.  TYPE=lock\_t:代表数据类型  
    
8.  NAME=hash:代表lock\_t下面有一个hash元素指针，其实这个指针和我们平时用的链表的struct\* NEXT没什么区别  
    
9.  唯一区别就是他是void\*的  
    
10. (hash\_node\_t hash;  
    
11. typedef void\* hash\_node\_t;)  
    
12. TABLE=lock\_sys\->rec\_hash:代表hash表的地址指针,输入参数  
    
13. (hash\_table\_t\* rec\_hash;)  
    
14. FOLD=lock\_rec\_fold(space, page\_no):函数lock\_rec\_fold通过表空间和页号得到一个unsigned long数字  
    
15. DATA=lock:这实际上就是你的数据的指针，当然这里就是lock\_t\* 输入参数  
    
16. \*/  
    
17.   
    
18.   
    
19. \#define HASH\_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\\  
    
20. do \{ \\  
    
21. hash\_cell\_t\* cell3333;\\//实际上就是void\*  
    
22. TYPE\* struct3333;\\ //lock\_t\* struct3333;  
    
23. \\  
    
24. HASH\_ASSERT\_OWN(TABLE, FOLD)\\//断言不考虑  
    
25. \\  
    
26. (DATA)\->NAME = NULL;\\//lock\->hash = NULL;  
    
27. \\  
    
28. cell3333 = hash\_get\_nth\_cell(TABLE, hash\_calc\_hash(FOLD, TABLE));\\  
    
29. \\  
    
30. if (cell3333\->node == NULL) \{ \\ //如果为NULL没有元素挂载到这个cell下  
    
31. cell3333\->node = DATA;\\ //则我们挂载到这个cell下  
    
32. \} else \{ \\  
    
33. struct3333 = (TYPE\*) cell3333\->node;\\ //否则说明有元素了取到这个元素的指针 lock\_t\* struct3333 = (lock\_t\*)cell3333\->node;  
    
34. \\  
    
35. while (struct3333\->NAME != NULL) \{ \\ //如果struct3333\->hash 不等于NULL 说明他下面有元素了  
    
36. \\  
    
37. struct3333 = (TYPE\*) struct3333\->NAME;\\ //那么我们需要做的是指针像链表下一个元素移动  
    
38. \}\\  
    
39. \\  
    
40. struct3333\->NAME = DATA;\\ //最后找到链表末尾 将数据节点挂载到下面 struct3333\->hash = lock(lock是lock\_t\*)  
    
41. \}\\  
    
42. \} while (0)

六、删除一个元素  
这部分也是通过宏定义来做的如下，我写了详细的解释

点击(此处)折叠或打开

1.  /\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*//\*\*  
    
2.  Deletes a struct from a hash table. \*/  
    
3.  /\*  
    
4.  有了上面基础也就比较简单了，这里直接在代码进行注释  
    
5.  HASH\_DELETE(lock\_t, hash, lock\_sys\->rec\_hash,lock\_rec\_fold(space, page\_no), in\_lock);  
    
6.  \*/  
    
7.  \#define HASH\_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\\  
    
8.  do \{ \\  
    
9.  hash\_cell\_t\* cell3333;\\//实际上就是void\*  
    
10. TYPE\* struct3333;\\ //lock\_t\* struct3333;  
    
11. \\  
    
12. HASH\_ASSERT\_OWN(TABLE, FOLD)\\//断言不考虑  
    
13. \\  
    
14. cell3333 = hash\_get\_nth\_cell(TABLE, hash\_calc\_hash(FOLD, TABLE));\\//通过函数hash\_get\_nth\_cell计算这个值在哪个cell也就是hash 桶中  
    
15. \\  
    
16. if (cell3333\->node == DATA) \{ \\ //地址比较，如果地址相同其地址必然相同  
    
17. HASH\_ASSERT\_VALID(DATA\->NAME);\\//断言不考虑  
    
18. cell3333\->node = DATA\->NAME;\\//如果找到 将指针移动到下一个元素 言外之意这里去掉了一个内存单元就是找到的那个  
    
19. \} else \{ \\  
    
20. struct3333 = (TYPE\*) cell3333\->node;\\ //链表循环找  
    
21. \\  
    
22. while (struct3333\->NAME != DATA) \{ \\  
    
23. \\  
    
24. struct3333 = (TYPE\*) struct3333\->NAME;\\  
    
25. ut\_a(struct3333);\\  
    
26. \}\\  
    
27. \\  
    
28. struct3333\->NAME = DATA\->NAME;\\ //最终找到 就做 链表去掉这个内存元素动作  
    
29. \}\\  
    
30. //最终这里涉及到一个问题就是释放问题，但是注意虽然这个数据的指针在链表中去掉了，但是指针本身还在，可以拿到做free即可  
    
31. HASH\_INVALIDATE(DATA, NAME);\\ //debug版本使用不考虑  
    
32. \} while (0)

七、其他  
其他函数还包含：  
HASH\_SEARCH\_ALL:宏实现在整个hash表中查找一个元素，相当于真个cell个链表查找  
HASH\_SEARCH:宏实现在有建值的情况下查找一个元素、言外之意cell(桶)确定了，相当于链表查找  
hash\_table\_clear: 清空一个hash表  
就不详细解释了，当然我只是对基本实现和常用的方法进行了描述，其他方面遇到再说吧。  
  
作者微信:  
  
![img\_4166a896a28155d27307bf8bdad181d5.jpg][img_4166a896a28155d27307bf8bdad181d5.jpg]

[img_7f135c247a2e0dd65fcc9f2263072cd0.png]: /images/20220131/8370f5c96a524da2a909b26b210c7145.png
[img_4166a896a28155d27307bf8bdad181d5.jpg]: /images/20220131/5cdf6b09f4c344cea709d2cff583ca51.png