\2. 添加元素
template class raw_hash_set { // 查找 // Attempts to find `key` in the table; if it isn't found, returns a slot that // the value can be inserted into, with the control byte already set to // `key`'s H2. template std::pair find_or_prepare_insert(const K& key) { prefetch_heap_block(); auto hash = hash_ref()(key); // 在相同hash值的桶中查找 auto seq = probe(ctrl_, hash, capacity_); while (true) { Group g{ctrl_ + seq.offset()}; for (uint32_t i : g.Match(H2(hash))) { // 如果key相等 ， 则找到了目标元素 if (ABSL_PREDICT_TRUE(PolicyTraits::apply( EqualElement{key, eq_ref()}, PolicyTraits::element(slots_ + seq.offset(i))))) return {seq.offset(i), false}; } if (ABSL_PREDICT_TRUE(g.MaskEmpty())) break; seq.next(); assert(seq.index() <= capacity_ && "full table!"); } // 如果没有相等的key ， 则插入元素 return {prepare_insert(hash), true}; } // 找到下一个可用的slot // Given the hash of a value not currently in the table, finds the next // viable slot index to insert it at. size_t prepare_insert(size_t hash) ABSL_ATTRIBUTE_NOINLINE { auto target = find_first_non_full(ctrl_, hash, capacity_); if (ABSL_PREDICT_FALSE(growth_left() == 0 && !IsDeleted(ctrl_[target.offset]))) { rehash_and_grow_if_necessary(); target = find_first_non_full(ctrl_, hash, capacity_); } ++size_; growth_left() -= IsEmpty(ctrl_[target.offset]); SetCtrl(target.offset, H2(hash), capacity_, ctrl_, slots_, sizeof(slot_type)); infoz().RecordInsert(hash, target.probe_length); return target.offset; } // 在找到的slot处构造元素 template iterator lazy_emplace(const key_arg& key, F&& f) { auto res = find_or_prepare_insert(key); if (res.second) { slot_type* slot = slots_ + res.first; std::forward(f)((&alloc_ref(), &slot)); assert(!slot); } return iterator_at(res.first); }};
\3. rehash
template class raw_hash_set { // Called whenever the table *might* need to conditionally grow. void rehash_and_grow_if_necessary() { if (capacity_ == 0) { resize(1); } else if (capacity_ > Group::kWidth && size() * uint64_t{32} <= capacity_ * uint64_t{25}) { drop_deletes_without_resize(); } else { // Otherwise grow the container. resize(capacity_ * 2 + 1); } } void resize(size_t new_capacity) { assert(IsValidCapacity(new_capacity)); auto* old_ctrl = ctrl_; auto* old_slots = slots_; const size_t old_capacity = capacity_; capacity_ = new_capacity; initialize_slots(); size_t total_probe_length = 0; for (size_t i = 0; i != old_capacity; ++i) { if (IsFull(old_ctrl[i])) { size_t hash = PolicyTraits::apply(HashElement{hash_ref()}, PolicyTraits::element(old_slots + i)); auto target = find_first_non_full(ctrl_, hash, capacity_); size_t new_i = target.offset; total_probe_length += target.probe_length; SetCtrl(new_i, H2(hash), capacity_, ctrl_, slots_, sizeof(slot_type)); // 调用 policy transfer 在新地址处构造元素 PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, old_slots + i); } } if (old_capacity) { SanitizerUnpoisonMemoryRegion(old_slots, sizeof(slot_type) * old_capacity); Deallocate( &alloc_ref(), old_ctrl, AllocSize(old_capacity, sizeof(slot_type), alignof(slot_type))); } infoz().RecordRehash(total_probe_length); }};// flat_hash_map在rehash时 ， 将元素移动至新地址处template struct map_slot_policy { template static void transfer(Allocator* alloc, slot_type* new_slot, slot_type* old_slot) { emplace(new_slot); // 将元素 move 至新地址处 if (kMutableKeys::value) { absl::allocator_traits::construct( *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value)); } else { absl::allocator_traits::construct(*alloc, &new_slot->value, std::move(old_slot->value)); } destroy(alloc, old_slot); }};// node_hash_map在rehash时 ， 将指向元素的指针拷贝至新地址处template struct node_slot_policy { template static void transfer(Alloc*, slot_type* new_slot, slot_type* old_slot) { // 将“指向元素的地址” copy 至新地址处 *new_slot = *old_slot; }};基准测试
基准测试场景如下：
 

• k、v均为std::string
• k长度约20字节
• v长度约40字节
• 写操作：向空map中 ， emplace N个k值不同的pair
• 读操作：从包含N个pair的map中 ， find N次随机k值（提前生成好的随机序列）