memcached源码分析-----哈希表基本操作以及扩容过程

开发技术作者： 2024-06-17 09:35:01

转载请注明出处：http://blog.csdn.net/luotuo44/article/details/42773231 温馨提示：本文用到了一些可以在启动memcached设置的全局变量。关于这些全局变量的含义可以参考《memcached启动参数详解》。对于这些全局变量，处理方式就像《如何

转载请注明出处：http://blog.csdn.net/luotuo44/article/details/42773231

温馨提示：本文用到了1些可以在启动memcached设置的全局变量。关于这些全局变量的含义可以参考《memcached启动参数详解》。对这些全局变量，处理方式就像《如何浏览memcached源代码》所说的那样直接取其默许值。

assoc.c文件里面的代码是构造1个哈希表。memcached快的1个缘由是使用了哈希表。现在就来看1下memcached是怎样使用哈希表的。

哈希结构：

main函数会调用assoc_init函数申请并初始化哈希表。为了减少哈希表产生冲突的可能性，memcached的哈希表是比较长的，并且哈希表的长度为2的幂。全局变量hashpower用来记录2的幂次。main函数调用assoc_init函数时使用全局变量settings.hashpower_init作为参数，用于指明哈希表初始化时的幂次。settings.hashpower_init可以在启动memcached的时候设置，具体可以参考《memcached启动参数详解和关键配置的默许值》。

//memcached.h文件 #define HASHPOWER_DEFAULT 16 //assoc.h文件 unsigned int hashpower = HASHPOWER_DEFAULT; #define hashsize(n) ((ub4)1<<(n))//这里是1 左移 n次 //hashsize(n)为2的幂，所以hashmask的值的2进制情势就是后面全为1的数。这就很像位操作里面的 & //value & hashmask(n)的结果肯定是比hashsize(n)小的1个数字.即结果在hash表里面 //hashmask(n)也能够称为哈希掩码 #define hashmask(n) (hashsize(n)⑴) //哈希表数组指针 static item** primary_hashtable = 0; //默许参数值为0。本函数由main函数调用，参数的默许值为0 void assoc_init(const int hashtable_init) { if (hashtable_init) { hashpower = hashtable_init; } //由于哈希表会渐渐增大，所以要使用动态内存分配。哈希表存储的数据是1个 //指针，这样更省空间。 //hashsize(hashpower)就是哈希表的长度了 primary_hashtable = calloc(hashsize(hashpower),sizeof(void *)); if (! primary_hashtable) { fprintf(stderr,"Failed to init hashtable. "); exit(EXIT_FAILURE);//哈希表是memcached工作的基础，如果失败只能退出运行 } }

说到哈希表，那末就对应有两个问题，1个是哈希算法，1个怎样解决冲突。

对哈希函数(算法)，memcached直接使用开源的MurmurHash3和jenkins_hash两个中的1个。默许是使用jenkins，可以在启动memcached的时候设置设置为MurmurHash3。memcached是直接把客户端输入的键值作为哈希算法的输入，得到1个32位的无符号整型输出(用变量hv存储)。由于哈希表的长度没有2^32- 1这么大，所以需要用到前面代码中的hashmask宏进行截断。由因而位操作，所以常常能在memcached代码中看的hv & hashmask(hashpower)。

memcached使用最多见的链地址法解决冲突问题。从前面的代码可以看到，primary_hashtable是1个的2级指针变量，它指向的是1个1维指针数组，数组的每个元素指向1条链表(链表上的item节点具有相同的哈希值)。数组的每个元素，在memcached里面也称为桶(bucket)，所以后文的表述中会使用桶。下图是1个哈希表，其中第0号桶有2个item，第2、3、5号桶各有1个item。item就是用来存储用户数据的结构体。