MYSQL INNODB中hash查找表的實現
原創有誤請指出：
版本：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; /*<! 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的地址了，后面的只是地址指針++就可以了。那么我們user_str也至少包含這樣一個
hash_table_t*的指針來指向整個hash表，確實如此在innodb lock_sys_t中包含了
hash_table_t* rec_hash
那么我們可以lock_sys_t和lock_t為列子畫一張展示圖如下：
四、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)
六、刪除一個元素
這部分也是通過宏定義來做的如下，我寫了詳細的解釋
-
/*******************************************************************//**
-
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表
就不詳細解釋了，當然我只是對基本實現和常用的方法進行了描述，其他方面遇到再說吧。
作者微信:
