1. 怎么样自己实现一个dictdics是一种常用的数据结构，而C语言没有提供内置类型，本文一起看看redis中dict的实现
不像C++、java等高级语言内置了map，C语言并没有提供dict库，所以如果想使用dict就需要自己实现。那么实现一个dict有方法呢？
- 数组法
- 这也是最容易实现的一种方法，简单说就是开辟一个长度为N的大数组（通常N是一个质数），然后通过一个哈希函数计算key的哈希值d，然后用d%N得到key对于的数组下边。设想一下，如果数组开的足够大，而且哈希函数足够散列，我们可以保证不同的key的对应的下标绝不会冲突，那么这样就可以实现一个dict了。
- 上述介绍实现dict的方法在实际中有很大的限制，比如我们不知道数组开大多大合适，即使开了一百万，那么随着业务的增长，这一百万也不够。其次没有一个哈希函数能够保证不同key的哈希值不重复。
- 鉴于此，我们在用数组实现dict的时候数组长度一般是动态的，根据元素个数/数组长度这一指标来判断扩缩容，其次我们找一个尽量能打散的哈希函数。最后，对于冲突的key，我们可以简单的使用拉链法解决冲突。
- 红黑树法
- C++中的map底层实现就是红黑树。红黑树的核心就是尽量保证二叉树是左右平衡的，所以红黑树的实现较为复杂，需要区分各种情况旋转。不需要哈希函数，只需要实现key的比较函数就可以了，所以也就不存在key冲突。
- 跳表法
- 如果想实现红黑树的效果，但是又不想实现红黑树，那么跳表是个不错的选择，它的效率几乎和红黑树等价。redis中zset底层就使用的了调表，具体实现后续再说。
-
redis中dict的实现用了上述第一种方法也就是数组拉链法，对于哈希函数，redis选用了Murmurhash2。下面看看结构定义。
typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry; typedef struct dictType { uint64_t (*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; unsigned long size; unsigned long sizemask; unsigned long used; } dictht; typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; unsigned long iterators; } dict;
-
公共操作
-
根据key查找数组中的index
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing) { unsigned long idx, table; dictEntry *he; if (existing) *existing = NULL; if (_dictExpandIfNeeded(d) == DICT_ERR) return -1; for (table = 0; table <= 1; table++) { idx = hash & d->ht[table].sizemask; he = d->ht[table].table[idx]; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) { if (existing) *existing = he; return -1; } he = he->next; } if (!dictIsRehashing(d)) break; } return idx; } -
扩容
static int _dictExpandIfNeeded(dict *d) { if (dictIsRehashing(d)) return DICT_OK; if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { return dictExpand(d, d->ht[0].used*2); } return DICT_OK; } -
rehash
static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1); } int dictRehash(dict *d, int n) { int empty_visits = n*10; if (!dictIsRehashing(d)) return 0; while(n-- && d->ht[0].used != 0) { dictEntry *de, *nextde; assert(d->ht[0].size > (unsigned long)d->rehashidx); while(d->ht[0].table[d->rehashidx] == NULL) { d->rehashidx++; if (--empty_visits == 0) return 1; } de = d->ht[0].table[d->rehashidx]; while(de) { uint64_t h; nextde = de->next; h = dictHashKey(d, de->key) & d->ht[1].sizemask; de->next = d->ht[1].table[h]; d->ht[1].table[h] = de; d->ht[0].used--; d->ht[1].used++; de = nextde; } d->ht[0].table[d->rehashidx] = NULL; d->rehashidx++; } if (d->ht[0].used == 0) { zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; return 0; } return 1; }
-
-
创建
dict *dictCreate(dictType *type, void *privDataPtr) { dict *d = zmalloc(sizeof(*d)); _dictInit(d,type,privDataPtr); return d; } int _dictInit(dict *d, dictType *type, void *privDataPtr) { _dictReset(&d->ht[0]); _dictReset(&d->ht[1]); d->type = type; d->privdata = privDataPtr; d->rehashidx = -1; d->iterators = 0; return DICT_OK; } -
插入
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing) { long index; dictEntry *entry; dictht *ht; if (dictIsRehashing(d)) _dictRehashStep(d); if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) return NULL; ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; entry = zmalloc(sizeof(*entry)); entry->next = ht->table[index]; ht->table[index] = entry; ht->used++; dictSetKey(d, entry, key); return entry; } int dictAdd(dict *d, void *key, void *val) { dictEntry *entry = dictAddRaw(d,key,NULL); if (!entry) return DICT_ERR; dictSetVal(d, entry, val); return DICT_OK; } -
删除
int dictDelete(dict *ht, const void *key) { return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR; } static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) { uint64_t h, idx; dictEntry *he, *prevHe; int table; if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL; if (dictIsRehashing(d)) _dictRehashStep(d); h = dictHashKey(d, key); for (table = 0; table <= 1; table++) { idx = h & d->ht[table].sizemask; he = d->ht[table].table[idx]; prevHe = NULL; while(he) { if (key==he->key || dictCompareKeys(d, key, he->key)) { 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 he; } prevHe = he; he = he->next; } if (!dictIsRehashing(d)) break; } return NULL; }
原文出处：http://ditanshow.com/articles/p/317.html
