Shulou(Shulou.com)06/01 Report--

If the original is wrong, please point out:

Version: 5.7.14

Source code location is hash0hash.h hash0hash.cc

As a data structure with optimal time complexity of O (1), but with the worst time complex alignment O (n), but in

The performance is very good in the case of good design of hash function. The diagram of the hash table is given at the end. All kinds of data in innodb

Structures use hash table lookups such as LOCK_T structures, as well as adaptive hash indexes that we are particularly familiar with. Let's do some

Discuss.

1. Innodb hash function

First of all, we have to study the hash function of innodb. The design of hash function has at least two requirements.

1. The calculation is simple, otherwise your hash lookup table will not be successful if it takes too much time.

2. the calculation can disperse the value as much as possible.

So how does innodb design this hash function? It is very simple as follows:

Click (here) to collapse or open

Ulint

Ut_hash_ulint (

/ * /

Ulint key, / *! heap = NULL

Ut_d (table- > magic_n = HASH_TABLE_MAGIC_N)

/ * Initialize the cell array * /

Hash_table_clear (table); / / memset 0x00 entire hash table

Return (table)

}

Note: the following are annotated through the implementation of some of the hash tables in LOCK, and the rest are the same.

Insert an element

This part is done through the macro definition as follows, I wrote a detailed explanation

Click (here) to collapse or open

/ * /

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: represents the data type

NAME=hash: there is a hash element pointer under the lock_t. In fact, this pointer is no different from the struct* NEXT of the linked list that we usually use.

The only difference is that he belongs to void*.

(hash_node_t hash

Typedef void* hash_node_t;)

TABLE=lock_sys- > rec_hash: address pointer that represents the hash table, input parameters

(hash_table_t* rec_hash;)

FOLD=lock_rec_fold (space, page_no): the function lock_rec_fold gets a unsigned long number from the table space and page number

DATA=lock: this is actually the pointer to your data, and of course here are the lock_t* input parameters

, /

# define HASH_INSERT (TYPE, NAME, TABLE, FOLD, DATA)\

Do {\

Hash_cell_t* cell3333;\ / / is actually void*.

TYPE* struct3333;\ / / lock_t* struct3333

\

HASH_ASSERT_OWN (TABLE, FOLD)\ / / assertion does not consider

\

(DATA)-> NAME = NULL;\ / / lock- > hash = NULL

\

Cell3333 = hash_get_nth_cell (TABLE, hash_calc_hash (FOLD, TABLE);\

\

If (cell3333- > node = = NULL) {\ / / if there are no elements mounted to this cell for NULL

Cell3333- > node = DATA;\ / / then we mount to this cell

} else {\

Struct3333 = (TYPE*) cell3333- > node;\ / / otherwise, it means there is an element. The pointer to this element is lock_t* struct3333 = (lock_t*) cell3333- > node.

\

While (struct3333- > NAME! = NULL) {\ / / if struct3333- > hash is not equal to NULL, it means there is an element below it.

\

Struct3333 = (TYPE*) struct3333- > NAME;\ / then all we need to do is move the pointer like the next element in the linked list

}\

\

Struct3333- > NAME = DATA;\ / / finally find the end of the linked list and mount the data node below struct3333- > hash = lock (lock is lock_t*)

}\

} while (0) VI. Delete an element

This part is also done through the macro definition as follows, I wrote a detailed explanation

Click (here) to collapse or open

/ * /

Deletes a struct from a hash table. , /

/ *

With the above foundation, it is relatively simple. Here, comment directly in the code.

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;\ / / is actually void*.

TYPE* struct3333;\ / / lock_t* struct3333

\

HASH_ASSERT_OWN (TABLE, FOLD)\ / / assertion does not consider

\

Cell3333 = hash_get_nth_cell (TABLE, hash_calc_hash (FOLD, TABLE));\ / / calculate which cell, that is, hash bucket, this value is in through the function hash_get_nth_cell.

\

If (cell3333- > node = = DATA) {\ / / address comparison, if the address is the same, the address must be the same

HASH_ASSERT_VALID (DATA- > NAME);\ / / assertions are not considered

Cell3333- > node = DATA- > NAME;\ / / if you find it, move the pointer to the next element, implying that one memory unit is removed, which is the one you found.

} else {\

Struct3333 = (TYPE*) cell3333- > node;\ / / linked list Loop search

\

While (struct3333- > NAME! = DATA) {\

\

Struct3333 = (TYPE*) struct3333- > NAME;\

Ut_a (struct3333);\

}\

\

Struct3333- > NAME = DATA- > NAME;\ / / finally find it and make a linked list to remove the memory element.

}\

/ / finally, one problem involved here is the release problem, but note that although the pointer of this data has been removed from the linked list, the pointer itself is still there and can be used as a free.

HASH_INVALIDATE (DATA, NAME);\ / / debug version is not considered

} while (0) VII. Other

Other functions include:

HASH_SEARCH_ALL: Acer now looks for one element in the entire hash table, which is equivalent to a real cell linked list lookup.

HASH_SEARCH: Acer now has a value to find an element, and the implication cell (bucket) is determined, which is equivalent to a linked list lookup.

Hash_table_clear: clear a hash table

I won't explain it in detail. Of course, I just describe the basic implementation and common methods, and we'll talk about it when we encounter other aspects.

Author Wechat:

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.