MySQL 内置结构 hash 表的使用

888 阅读4分钟

最近实现的两个patch都使用到了MySQL内置的hash结构。这个结构在MySQL框架层中被多处使用,理解它可以方便代码阅读。

    1、  总体

InnoDB中也有自带的HASH表, 本文中介绍的是MySQL框架层的hash表。 其定义的头文件在include/hash.h,实现位置mysys/hash.c。内部存储数据使用了动态数组DYNAMIC_ARRAY。

这个hash表实现了插入、删除、修改、查找接口,也提供了遍历接口。在打patch时会发现很好用。

2、初始化 _my_hash_init

a) 声明 

参数表

HASH *hash

欲初始化的hash表地址

uint growth_size

Hash表空间不够时再次申请的个数

CHARSET_INFO *charset

系统字符集

ulong default_array_elements

初始容量

size_t key_offset

Key在data中的偏移量

size_t key_length

Key的长度

my_hash_get_key get_key

获取key的回调函数

void (*free_element)(void*)

析构回调

uint flags

hash表类型

b) 说明:

1) 调用时growth_size一般取值为0,内部会根据初始值和每个HASH_LINK大小得到一个合理的值(./mysys/array.c), sizeof(HASH_LINK)=sizeof(int)+sizeof(char*);

2)hash表类型目前只有0和1(HASH_UNIQUE), 为1表示key值不允许重复;

3) 析够回调中,对于传入的元素指针,需要自定义一个合适的删除方法。

4)特别说明typedef uchar *(*my_hash_get_key)(const uchar *,size_t*,my_bool)。 若该回调函数不为NULL, 则通过该函数的size_t*传出key的长度, 返回值为key在data中的起始地址; 若为NULL,则偏移量为key_offset,key长度为key_length。

从init的声明中可以看到,这个hash表中存的是全数据(data), 也包含了key的内容。Key作为data的一部分,通过my_hash_get_key告诉hash表key的获取方式(当然获取到key之后,最终还是签名后决定hash位置)。

3、插入元素 my_hash_insert

a) 声明 

参数表

HASH *info

hash表地址

const uchar *data

插入的数据地址

b)说明

1)可以看到,插入的参数只有一个datakey的获取方式即为init时指定的my_hash_get_key或 key_offset& key_length;

2) 需要注意,hash中存的只是data的地址,因此data不能为栈变量。且需要在free_element中自定义删除方法。

3)返回值为TRUE时,表示插入失败,为0时表示插入成功。

4、查找元素 my_hash_search

a) 声明 

参数表

const HASH *info

hash表地址

const uchar *key

查找的key

size_t length

Key长度

b)说明:

1)返回值为查找到的data的地址,若查找不到,返回NULL

2)由于直接返回data的地址,因此如果要修改data中的key字段,可以直接指针操作。

5、删除/修改元素

a) 删除my_hash_delete

参数表

const HASH *info

hash表地址

const uchar *data

删除的数据地址

说明注意这里是按照地址比较的,非key

b) 修改my_hash_update

参数表

const HASH *info

hash表地址

const uchar *data

修改的数据地址

uchar *old_key

原key

size_t old_key_length

原key长度

说明: 该函数的功能是,当data内容有涉及到key的修改时,修改key,及其在hash表的位置。效果上等效于delete+insert,但效率更高。

6、遍历

遍历功能使得这个数据结构非常好用。看下面的代码就知道用法了。

说明:其中hash_item_thash表中的元素――我们自定义的类型。

7、一个例子

用一个例子来简要说明用法,只需要演示init部分就可以了。

初始化语句

说明:MySQL代码中多使用这个宏,其中growth_size在替换中默认使用0;


说明:

1)我们使用字符串的key,因此在hash_item_t中有key_lenkey[]。配合hash_item_get_key提供根据输入的data,获取key_lenkey的方法。

2)由于inserthash表的数据是通过new hash_item_t的方法得到的,因此在free_entry中直接使用delete回收。

关于阿里百川

阿里百川(baichuan.taobao.com)是阿里巴巴集团“云”+“端”的核心战略是阿里巴巴集团无线开放平台,基于世界级的后端服务和成熟的商业组件,通过“技术、商业及大数据”的开放,为移动创业者提供可快速搭建App、商业化APP并提升用户体验的解决方案;同时提供多元化的创业服务-物理空间、孵化运营、创业投资等,为移动创业者提供全面保障。