关于Map增长时的遍历问题
来源：1-9 神奇的内置数据结构
theburn
2021-05-28 23:11:30
问题描述：
如果在迁移过程中遍历，只返回那些将迁移到当前bucket的oldbucket的条目。
这句话是否理解成，在遍历的同时，map还在持续增长并且伴随bucket的迁移。
比如一个原来bucket-1中的8个元素，增长后，变成 bucket-1中有3个（原来bucket-1） + 1个（来自bucket-M），另外5个（来自bucket-1）分配到bucket-N中了。
当遍历到bucket-1时，只返回最原始的3个（oldbucket）， 是这个意思吗？
如果是的话， 那来自bucket-M的那1个元素，会如何被遍历到呢？
1回答
-
两种情况：
等大扩容(扩容前 hmap.B = 扩容后 hmap.B)的时候，buckets[i] 的元素一定是来自于原来的 oldbuckets[i] 的，这种情况下无脑把 oldbuckets[i] 和它后面挂的 overflow 无脑遍历完就行了。
增大扩容(扩容前 hmap.B+1 = 扩容后 hmap.B，即 bucket 总数 *2)的时候，oldbuckets[i]，在 buckets 中一部分去了 buckets[i](代码里的 X part)，一部分去了 buckets[2^B+i](代码里的 Y part)，我们遍历 buckets[i] 的时候，就只要按那个扩容规则，就是 lowbits 来算一下，就知道 oldbuckets[i] 哪些元素会进 buckets[i] 了，只把这部分拿出来就行，剩下的那部分，会在遍历 buckets[N+i] 的时候被遍历到
这东西看起来拿文字描述确实不好懂，明天讲完课，我再补一下动画吧。
0
相似问题