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

This article mainly introduces how to achieve hash in redis, which is very detailed and has certain reference value. Friends who are interested must read it!

0. Preface

Redis is a KV-type in-memory database, and the core of database storage is Hash table. After we execute the select command to select a stored db, all operations are based on hash table. The following will analyze the hash data structure and implementation of redis.

1.hash data structure / * Hash table A node contains Key,Value data pairs * / typedef struct dictEntry {void * key; union {void * val; uint64_t u64; int64_t s64; double d;} v; struct dictEntry * next; / * points to the next node and links tables to resolve Hash conflicts * /} dictEntry / * store callback functions of different data types corresponding to different operations * / typedef struct dictType {unsigned int (* hashFunction) (const void * key); void * (* keyDup) (void * privdata, const void * key); void * (* valDup) (void * privdata, const void * obj); int (* keyCompare) (void * privdata, const void * key1, const void * key2); void (* keyDestructor) (void * privdata, void * key) Void (* valDestructor) (void * privdata, void * obj);} dictType;typedef struct dictht {dictEntry* * table; / * dictEntry* array, Hash table * / unsigned long size; / * Hash table total size * / unsigned long sizemask; / * calculate the mask of the index in table, and the value is the size used by the size-1 * / unsigned long used; / * Hash table * /} dictht;typedef struct dict {dictType * type; void * privdata Dictht ht [2]; / * two hash tables. The index of * / long rehashidx; / * rehash is used for rehash.-1 indicates that there is no rehash * / int iterators; / * * /} dict;2.hash data structure diagram.

3. Progressive hash description

There are two hash tables in ht [2] in dict. When we store data for the first time, ht [0] will create a minimum hash table of 4. Once size and used in ht [0] are equal, a size*2 size hash table will be created in dict [1]. At this time, the data copy in ht [0] will not be directly added to ht [0], and the progressive rehash will be performed, that is, in the later operations (find, set). Slowly copy in get, etc.), and the newly added elements will be added to ht [0] later, so when ht [1] is full, you can make sure that all the data in ht [0] is copy into ht [1].

4. Create a hash table

The process of creating the hash table is very simple, directly call the dictCreate function, allocate a piece of memory, and initialize the intermediate variables.

Dict * dictCreate (dictType * type, void * privDataPtr) {/ * allocate memory * / dict * d = zmalloc (sizeof (* d)); / * initialization operation * / _ dictInit (ddocin type _ privDataPtr); return d;} 5. Add element

To add elements to the hash table, first determine whether there is enough space, then calculate the hash value corresponding to key, and then put the key and value that need to be added into the table.

Int dictAdd (dict * d, void * key, void * val) {/ * add to the hash table, return the entity structure of the newly added element * / dictEntry * entry = dictAddRaw (djournal key); put the vale value of if (! entry) return DICT_ERR; / * element into the element entity structure * / dictSetVal (d, entry, val); return DICT_OK } / * * add element entity function * / dictEntry * dictAddRaw (dict * d, void * key) {int index; dictEntry * entry; dictht * ht; if (dictIsRehashing (d)) _ dictRehashStep (d); / * calculate the index of the new element in the hash table based on the key value. Return-1 to indicate that the element already exists, and directly return NULL*/ if ((index = _ dictKeyIndex (d, key)) =-1) return NULL / * if the rehash process is underway, the new element is added to ht [1], otherwise to ht [0] * / ht = dictIsRehashing (d)? & d-> ht [1]: & d-> ht [0]; entry = zmalloc (sizeof (* entry)); entry- > next = ht- > table [index]; ht- > table [index] = entry; ht- > used++ / * set element key*/ dictSetKey (d, entry, key); return entry;} / * * function to calculate the index * / static int _ dictKeyIndex (dict * d, const void * key) {unsigned int h, idx, table; dictEntry * he; / * to determine whether the hash table has enough space, and if insufficient, you need to extend * / if (_ dictExpandIfNeeded (d) = DICT_ERR) return-1 / * calculate the hash value corresponding to key * / h = dictHashKey (d, key); for (table = 0; table ht[ table] .sizemask; / * traverse the conflict list to determine whether the key you need to find is already in the conflict list * / he = d-> ht [table] .table [idx] While (he) {if (dictCompareKeys (d, key, he- > key)) return-1; he = he- > next;} if (! dictIsRehashing (d)) break;} return idx } / * * determine whether the hash table needs to expand the space * / static int _ dictExpandIfNeeded (dict * d) {/ * the progressive hash adopted by redis's rehash. Twice the original memory space is allocated in rehash, and there must be enough space for * / if (dictIsRehashing (d)) return DICT_OK in the rehash phase. / * hash table is empty and needs to be initialized. Default is 4 steps / if (d-> ht [0] .size = = 0) return dictExpand (d, DICT_HT_INITIAL_SIZE) / * the used space cannot meet the set conditions * / if (d-> ht [0] .used > = d-> ht [0] .size & & (dict_can_resize | | d-> ht [0] .used / d-> ht [0] .size > dict_force_resize_ratio)) {/ * expand the space, using twice the space * / return dictExpand (d, d-> ht [0] .used * 2) } return DICT_OK;} / * * expand the space or initialize the hash table space * / int dictExpand (dict * d, unsigned long size) {dictht n; / * to allocate a multiple of round size 2 * / unsigned long realsize = _ dictNextPower (size); / * call error * / if (dictIsRehashing (d) | | d-> ht [0] .used > size) return DICT_ERR if there is enough space N.size = realsize; n.sizemask = realsize-1; n.table = zcalloc (realsize*sizeof (dictEntry*)); n.used = 0; / * hash table is empty initializing hash table * / if (d-> ht [0] .table = = NULL) {d-> ht [0] = n; return DICT_OK } / * the newly allocated space is put into ht [1], then rehash*/ d-> ht [1] = n; d-> rehashidx = 0; return DICT_OK;} 6 step by step. Find element

In the process of finding elements, first calculate the hash value, and then calculate the index position in ht [0] and ht [1].

DictEntry * dictFind (dict * d, const void * key) {dictEntry * he; unsigned int h, idx, table; if (d-> ht [0] .size = 0) return NULL; / * if rehash is in progress, execute rehash*/ if (dictIsRehashing (d)) _ dictRehashStep (d); h = dictHashKey (d, key) / * since you may be in rehash, you have to look in ht [0] and ht [1] respectively, and cannot return NULL*/ for (table = 0; table ht [table] .sizemask; he = d-> ht [table] .table [idx]) / * traverse the conflict list to find elements * / while (he) {if (dictCompareKeys (d, key, he- > key)) return he; he = he- > next;} if (! dictIsRehashing (d)) return NULL;} return NULL;} 7. Delete element

Delete an element first find the element, and then remove the element from the hash table. If you call dictDelete to delete the element, the space occupied by the element will be deleted at the same time

Int dictDelete (dict * ht, const void * key) {return dictGenericDelete (ht,key,0);} static int dictGenericDelete (dict * d, const void * key, int nofree) {unsigned int h, idx; dictEntry * he, * prevHe; int table; if (d-> ht [0] .size = 0) return DICT_ERR; if (dictIsRehashing (d)) _ dictRehashStep (d); h = dictHashKey (d, key); for (table = 0; table httable] .sizemask He = d-> ht [table] .table [idx]; prevHe = NULL / * find the element to the element, delete it, and release the occupied memory * / while (he) {if (dictCompareKeys (d, key, he- > key)) {/ * Unlink the element from the list * / if (prevHe) prevHe- > next = he- > next Else d-> ht [table] .table [idx] = he- > next; if (! nofree) {dictFreeKey (d, he); dictFreeVal (d, he);} zfree (he); d-> ht [table] .used-- Return DICT_OK;} prevHe = he; he = he- > next;} if (! dictIsRehashing (d)) break;} return DICT_ERR; / * not found * /} hash command

The operation of hash commands is relatively simple. It should be noted that when we create hash to represent the default storage structure, which is not dict, but ziplist structure, you can refer to redis's Ziplist data structure. Hash_max_ziplist_entries and hash_max_ziplist_ value values are used as thresholds. Hash_max_ziplist_entries indicates that once the number of elements in ziplist exceeds this value, it needs to be converted to dict structure. Hash_max_ziplist_value means that once the data length in the ziplist is greater than this value, it needs to be converted to the dict structure.

These are all the contents of how to achieve hash in redis. Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.