思考mysql内核之初级系列7---innodb的hash表实现

《思考mysql内核之初级系列7---innodb的hash表实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、思考mysql内核之初级系列7™innodb的hash表实现在上一篇里面，bingxi和alex谈到了文件系统管理，在结构体里面出现了两个常用的结构：hash_table_t>UT_LIST_N0DE_To这两个结构比较常用，在本篇里面，bingxi和alex聊了下关于hash_table_t的内容。对应的文件为：D:mysql-5.1_7-betastorageinnobasehahash0hash.cD:mysql-5.1.7-betastorageinnobaseincludehash0hash.h1)常用结构体Bingxi

2、：“alex,我们今天聊下hash表，所谓hash表，常用的就是通过key,然后取模然后丢到相应的bucket一里面。假设bucket的数量是13个，key值对应的bucket就是key%13,相同bucket值的放在一个链表里面。这里需要注意一点的是，1和27具有相同的bucket值，会放在同一个bucket里面，因此查找的时候，首先找到对应的桶(bucket),然后对该桶的链表进行遍历，每个成员里面记录了原始的key,1对应的结构里面有一个字段表示1,27对应的一个结构里面有一个字段表示27,这样就能找到对应的成员。alex：“嗯，是的，bing

3、xio我们来看下hash表结构。同样地，我们将结构定义的其他元素先忽略，直接看其中的主要成员。如果需要了解其它的成员，则推荐设置debug断点进行调试。/*Thehashtablestructure*/structhash_table_struct{ulintn_cells;//hash表的成员数量，也可以称为bucket的数量hash_cell_t*array;〃指I句桶的数组}；结构中，就是成员的数量，以及一个数组。因为使用hash表的结构是多种多样的，比如前几篇文章中提到过的buf_pool_t>fil_system_to这两者都使用到了has

4、h,并口成员结构不一样。对于每个桶对应的指针类型是不确定，因此bucket中记录的指针是void*类型的。structhash_cell_struct{void*node;/*hashchainnode,NULLifnone*/};Bingxi：“alex,是这样的，这里带来两个问题：1、hash表的n_cells是个素数用于做模操作，在创建的时候提供…个准确的素数是有难度的，2、对应整型的key可以通过key%n_cells的方法来获得对应的桶，那么对于字符串型的如何处理？Alex：“嗯，好吧。在说这两个问题之前，我们先看下hash表的创建过程。我

5、们在函数fil_system_create如下面所示的行中设置一个断点。system->spaces=hash_create(hash_size);//在此行设置断开system->name_hash=hash_create(hash_size);然后启动mysql,执行到该断点处我们可以发现对应的hash_size为50。F11进入该函数体，看看具体是怎么执行的。/★*************沃****************************************Createsahashtablewith>=narraycells.The

6、actualnumberofcellsischosentobeaprimenumberslightlybiggerthann.*/hash_table_t*hash_create(/*out,own:createdtable*/ulintn)/*in:numberofarraycells*/hash_cell_t*array;ulintprime;hashtablet*table;ulinti;hashcellt*cell;〃在该例中，我们根据输入值50(n的取值)，得到一个素数151prime=ut_find_prime(n);table=mem_

7、alloc(sizeof(hash_table_t));//sizeof(hash_cell_t)的值为4〃生成一个有151(prime)个桶的数组array=ut_malloc(sizeof(hash_cell_t)*prime);〃初始化结构成员table->adaptive=FALSE;table->array=array;table->n_cells=prime;table->n_mutexes=0;table->mutexes=NULL;table->heaps=NULL;table->heap=NULL;table->magic_n=HA

8、SH_TABLE_MAGIC_N;/*Initializethecellarray*/〃取得每一个bucke