AtomicUnorderedMap是一个不反对删除、反对高并发读写、反对自定义K、V的哈希表，只反对一个findOrConstruct操作。
template <typename Func> std::pair<const_iterator, bool> findOrConstruct(const Key& key, Func&& func) { // 依据哈希算法定位到索引 auto const slot = keyToSlotIdx(key); auto prev = slots_[slot].headAndState_.load(std::memory_order_acquire); // 遍历动态链表查找键是否存在 auto existing = find(key, slot); if (existing != 0) { return std::make_pair(ConstIterator(*this, existing), false); } // 在左近找一个空slot，同时设标记位为CONSTRUCTING auto idx = allocateNear(slot); new (&slots_[idx].keyValue().first) Key(key); func(static_cast<void*>(&slots_[idx].keyValue().second)); while (true) { slots_[idx].next_ = prev >> 2; // we can merge the head update and the CONSTRUCTING -> LINKED update // into a single CAS if slot == idx (which should happen often) auto after = idx << 2; // 第一次就查找到空slot if (slot == idx) { after += LINKED; } else { after += (prev & 3); } // 没有其他人读写原始slot prev if (slots_[slot].headAndState_.compare_exchange_strong(prev, after)) { // success if (idx != slot) { slots_[idx].stateUpdate(CONSTRUCTING, LINKED); } return std::make_pair(ConstIterator(*this, idx), true); } // compare_exchange_strong updates its first arg on failure, so // there is no need to reread prev // 原来的slot有变动，看看是不是其余线程进行了插入 existing = find(key, slot); if (existing != 0) { // our allocated key and value are no longer needed slots_[idx].keyValue().first.~Key(); slots_[idx].keyValue().second.~Value(); slots_[idx].stateUpdate(CONSTRUCTING, EMPTY); return std::make_pair(ConstIterator(*this, existing), false); } } }