外国人做中国数学视频网站,建筑网站 知乎,杭州有哪些网络公司,常用于做网站的软件1.rehash原理
hash包含两个数据结构为字典数组ht[0]和ht[1]。其中ht[0]用来存放数据#xff0c;ht[1]在rehash时使用。 扩容时#xff0c;ht[1]的大小为第一个大于等于ht[0].used*2的2的幂次方的数#xff1b;
收缩时#xff0c;ht[1]的大小为第一个大于等于ht[0].used的…1.rehash原理
hash包含两个数据结构为字典数组ht[0]和ht[1]。其中ht[0]用来存放数据ht[1]在rehash时使用。 扩容时ht[1]的大小为第一个大于等于ht[0].used*2的2的幂次方的数
收缩时ht[1]的大小为第一个大于等于ht[0].used的2的幂次方的数
将ht[0]中的所有键值对rehash到ht[1]中rehash指重新计算键的hash值和存放的索引位置。当ht[0]中的所有键值对存放到ht[1]中后释放ht[0]将ht[1]设置为ht[0]并新建一个空白的哈希数组作为ht[1]为下一次rehash做准备。
2.渐进式hash
在扩容或者收缩时如果哈希数组中有很多元素一次性rehash会占用服务器资源所以采用渐进式rehash。
hash初始容量为4当元素个数和hash长度一致时扩容hash变为原来的两倍。
hash结构内一个游标rehashindex当rehashindex为0时代表开始rehash。
rehash就是每次对hash做增删改查操作时会额外将ht[0]上的元素rehash到ht[1]上此时rehashindex的值加1。
当ht[0]上的元素rehash完成后rehash的值设为-1表示rehash结束。
在渐进式rehash时如果有增删改查操作当要操作的元素的下标大于rehashindex时访问ht[0]否则访问ht[1]。
3.渐进式rehash特点
分而治之每次对hash进行一次操作才rehash一个元素避免集中式rehash导致占用系统资源redis是单线程阻塞其他线程。
