文章目录迭代器
抛砖引玉
先手写一个哈希表吧 。
三小时过去…
就这种源码中的数据结构啊，我个人是比较推崇大家自己先看概念手写一个，能不能动咱另说，在写的过程中会领悟到很多直接看所领悟不到的细节 。
redis 中 哈希表的实现
哈希表主要看哪些方面？底层承载的数据结构、节点数据结构、哈希函数、冲突解决，还有啥？扩容与…
关于增删查改就不多说了吧，哈希表的增删查改，挺常见了 。
哈希函数
redis 使用的是 ，计算出来的hash值具有强分布性，不过算法有点复杂（可以把“有点”，换成“比较”，反正我看晕了） 。
uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k) {#ifndef UNALIGNED_LE_CPUuint64_t hash;uint8_t *out = (uint8_t*) &hash;#endifuint64_t v0 = 0x736f6d6570736575ULL;uint64_t v1 = 0x646f72616e646f6dULL;uint64_t v2 = 0x6c7967656e657261ULL;uint64_t v3 = 0x7465646279746573ULL;uint64_t k0 = U8TO64_LE(k);uint64_t k1 = U8TO64_LE(k + 8);uint64_t m;const uint8_t *end = in + inlen - (inlen % sizeof(uint64_t));const int left = inlen & 7;uint64_t b = ((uint64_t)inlen) << 56;v3 ^= k1;v2 ^= k0;v1 ^= k1;v0 ^= k0;for (; in != end; in += 8) {m = U8TO64_LE(in);v3 ^= m;SIPROUND;v0 ^= m;}switch (left) {case 7: b |= ((uint64_t)in[6]) << 48; /* fall-thru */case 6: b |= ((uint64_t)in[5]) << 40; /* fall-thru */case 5: b |= ((uint64_t)in[4]) << 32; /* fall-thru */case 4: b |= ((uint64_t)in[3]) << 24; /* fall-thru */case 3: b |= ((uint64_t)in[2]) << 16; /* fall-thru */case 2: b |= ((uint64_t)in[1]) << 8; /* fall-thru */case 1: b |= ((uint64_t)in[0]); break;case 0: break;}v3 ^= b;SIPROUND;v0 ^= b;v2 ^= 0xff;SIPROUND;SIPROUND;b = v0 ^ v1 ^ v2 ^ v3;#ifndef UNALIGNED_LE_CPUU64TO8_LE(out, b);return hash;#elsereturn b;#endif}
网上也有关于这个算法的解释，有兴趣的朋友可以自己找来看，准备点小零食，加杯咖啡，有条件可以再来包袋装方便面，不要拆，以备不时之需呀！
冲突解决
开链法 。不用多说了吧 。
表结构
再往下就没太多意思了，我就意思意思吧 。本来以为这篇会很难写的，没想到难的部分我直接就看不懂了，倒是轻松了 。
/* This is our hash table structure. Every dictionary has two of this as we* implement incremental rehashing, for the old to the new table. */typedef struct dictht {dictEntry **table; //存储键值对unsigned long size; //计算table总大小unsigned long sizemask; //掩码unsigned long used; //记录开的链里面有几个节点} dictht;
单个节点
typedef struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;} dictEntry; //喏，这里体现出开链了
这个 v 我解释一下，是个联合体看得出来，存的是值，为什么要用联合体？因为可以在不同场景下发挥不同的作用 。这个技法学了好多次都记不住 。
如：存数据键值对的时候，用val;存过期时间的时候，用s64;
容量变化
先说说扩容吧，拿源码直接看：
typedef struct dict {dictType *type;void *privdata;dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 */unsigned long iterators; /* number of iterators currently running */} dict;
/* Expand or create the hash table */int dictExpand(dict *d, unsigned long size){/* the size is invalid if it is smaller than the number of* elements already inside the hash table */if (dictIsRehashing(d) || d->ht[0].used > size)return DICT_ERR;dictht n; /* the new hash table */unsigned long realsize = _dictNextPower(size);/* Rehashing to the same table size is not useful. */if (realsize == d->ht[0].size) return DICT_ERR;/* Allocate the new hash table and initialize all pointers to NULL */n.size = realsize;n.sizemask = realsize-1;n.table = zcalloc(realsize*sizeof(dictEntry*));n.used = 0;/* Is this the first initialization? If so it's not really a rehashing* we just set the first hash table so that it can accept keys. */if (d->ht[0].table == NULL) {d->ht[0] = n;return DICT_OK;}/* Prepare a second hash table for incremental rehashing */d->ht[1] = n;d->rehashidx = 0;return DICT_OK;}