青岛建站的模板,怎么注册自己的公司,网站网络投票建设步骤,专门做设计的网站字典
符号表、关联数组或者映射#xff0c;有点类似于java中的map#xff0c;用于保存键值对key-value。字典中的键key是独一无二的。底层实现为哈希表。下面进行简述#xff1a;
哈希表。哈希表主要包含table数组、size、sizemask以及used。table用于保存哈希表节点…字典
符号表、关联数组或者映射有点类似于java中的map用于保存键值对key-value。字典中的键key是独一无二的。底层实现为哈希表。下面进行简述
哈希表。哈希表主要包含table数组、size、sizemask以及used。table用于保存哈希表节点保存数据sizemask为哈希表掩码用于计算索引size用于保存table大小used用于保存已经保存的节点数目如图dictht结构体。哈希表节点。用于保存key-value数据以及next指针用于指向下一个节点为了解决哈希冲突而采用的拉链法。
typedef struct dictEntry{void *key;union{void *val;uint64_t u64;int64_t s64;} v;struct dictEntry *next;
} dictEntry;字典。主要包含type、privdata、ht[2]、rehashidx几个属性。type表示字典数据类型privdata保存了需要传递给type指定类型函数的可选参数ht[2]指向两个哈希表一个用于平时保存数据另一个用于rehash扩容等时使用rehashidx在rehash使用用于表示当前正在转移table中第几个索引的数据。整体结构茹下图。
哈希算法以及rehash
哈希算法。首先计算key的哈希值然后使用掩码sizemask求得在table中的索引例如 hash sizemask然后使用头插法直接插入使用链地址法解决哈希冲突。rehash。当哈希表的负载因子过大或者过小时需要进行扩展以及压缩这个时候需要rehash也就是需要重新计算当前值在新的table中的位置扩展时扩展为第一个大于等于ht[0].used*2的2的n次幂、压缩时压缩为第一个大于等于ht[0].used的2的n次幂负载因子等于used/size当当前正在进行持久化时BGSAVE或者BGREWRITEAOF负载因子大于等于5扩展平常选择1当负载因子小于0.1时进行压缩。rehash时查询操作先到ht[0]中查询如果没有再去ht[1]中查询插入新数据时直接在ht[1]中插入。rehashidx默认为-1当rehash时保存的为正在转移的ht[0]中table的索引。 本文为《Redis设计与实现》阅读笔记
