糌粑的面经笔记

Appearance

手写 flat hashmap（开放寻址 + 线性探测） ​

把哈希表压进一块连续内存：元素不再逐个分配、探针连续、cache 友好。 代价是 rehash 会搬家（引用失效）、删除必须留墓碑、对哈希质量更敏感。 对比实现见 unordered_map.md（拉链法）；另一种连续布局见 手写容器（flat_map）。

一、题面与澄清 ​

典型要求：实现 FlatHashMap<Key, Value> 的 insert / find / erase / operator[] / size， 说明复杂度与失效规则；追问集中在负载因子、rehash 与删除。

动手前需澄清：

  1. 删除是否允许使引用/指针失效（线性探测下删除会切断探测链，故需墓碑或后移重排）；
  2. Value 是否必须可默认构造（operator[] 需要；用节点或 optional 存储可规避）；
  3. 负载因子阈值（0.5 保守、0.7 省内存；墓碑须计入）；
  4. 容量是否限定为 2 的幂（是则可用 & (cap-1) 代替取模）。

二、接口与约束 ​

  • 接口：insert / find / contains / operator[] / erase / clear / reserve / size / capacity / load_factor / begin / end
  • 存储：连续数组；槽为「状态字节 + optional<pair<K,V>>」，状态取「空 / 占用 / 墓碑」三值
  • 不变量
    • 每个 key 至多占用一个槽；
    • 自 hash(key) 起的探测链上，在遇到空槽之前必能找到该 key（若存在）——这是墓碑存在的唯一理由。
  • 复杂度：find / insert / erase 期望 O(1)、最坏 O(n)；rehash O(n)；顺序遍历 O(容量)
  • 迭代器与失效：前向迭代，顺序为槽位顺序（非 key 顺序）；rehash 后全部失效，erase 只失效被删元素
  • 负载因子：(size + tombs) / capacity，超过 0.5 时 rehash 到 2 倍容量
  • 异常安全：元素存放在 optional 中，构造失败不影响表状态
  • 前置条件：Hash 与 Eq 语义一致（Eq(a,b) 为真 ⟹ Hash(a) == Hash(b)）

三、精简版：insert / find / erase（先交这个） ​

实现范围：最小可用集 —— insert / find / erase / size，含开放寻址、墓碑与按负载因子增长。 未提供 operator[] / clear / reserve / load_factor / capacity / 迭代器与 const 重载。

cpp
#pragma once
#include <cstddef>
#include <cstdint>
#include <functional>
#include <optional>
#include <utility>
#include <vector>

template <class K, class V, class Hash = std::hash<K>, class Eq = std::equal_to<K>>
class FlatHashMap {
  enum : std::uint8_t { kEmpty = 0, kFull = 1, kTomb = 2 };
  struct Slot {
    std::uint8_t state = kEmpty;
    std::optional<std::pair<K, V>> kv;
  };

 public:
  using size_type = std::size_t;

  FlatHashMap() { rehash_to(8); }
  size_type size() const noexcept { return size_; }

  V* find(const K& k) {                                  // 命中返回指向值的指针，否则 nullptr
    const size_type mask = slots_.size() - 1;
    size_type i = Hash{}(k) & mask;
    for (size_type n = 0; n < slots_.size(); ++n, i = (i + 1) & mask) {
      Slot& s = slots_[i];
      if (s.state == kEmpty) return nullptr;             // 仅空槽终止探查
      if (s.state == kFull && Eq{}(s.kv->first, k)) return &s.kv->second;
    }
    return nullptr;
  }
  std::pair<V*, bool> insert(K k, V v) {                 // 已存在 -> {现有值, false}
    grow_if_needed();
    const size_type mask = slots_.size() - 1;
    size_type i = Hash{}(k) & mask;
    size_type first_tomb = static_cast<size_type>(-1);
    for (size_type n = 0; n < slots_.size(); ++n, i = (i + 1) & mask) {
      Slot& s = slots_[i];
      if (s.state == kFull) {
        if (Eq{}(s.kv->first, k)) return {&s.kv->second, false};
      } else if (s.state == kTomb) {
        if (first_tomb == static_cast<size_type>(-1)) first_tomb = i;
      } else {
        const size_type at = first_tomb == static_cast<size_type>(-1) ? i : first_tomb;
        if (first_tomb != static_cast<size_type>(-1)) --tombs_;
        Slot& d = slots_[at];
        d.state = kFull;
        d.kv.emplace(std::move(k), std::move(v));
        ++size_;
        return {&d.kv->second, true};
      }
    }
    rehash_to(slots_.size() * 2);
    return insert(std::move(k), std::move(v));
  }
  size_type erase(const K& k) {
    const size_type mask = slots_.size() - 1;
    size_type i = Hash{}(k) & mask;
    for (size_type n = 0; n < slots_.size(); ++n, i = (i + 1) & mask) {
      Slot& s = slots_[i];
      if (s.state == kEmpty) return 0;
      if (s.state == kFull && Eq{}(s.kv->first, k)) {
        s.kv.reset();
        s.state = kTomb;                                 // 置回 kEmpty 会切断探测链
        --size_;
        ++tombs_;
        return 1;
      }
    }
    return 0;
  }

 private:
  void grow_if_needed() {
    if (size_ + tombs_ + 1 > slots_.size() / 2) rehash_to(slots_.size() * 2);
  }
  void rehash_to(size_type n) {
    size_type cap = 8;
    while (cap < n) cap *= 2;
    std::vector<Slot> old = std::move(slots_);
    slots_.assign(cap, Slot{});
    size_ = 0;
    tombs_ = 0;
    for (Slot& s : old) {
      if (s.state != kFull) continue;
      put_into(slots_, size_, s.kv->first, std::move(s.kv->second));
    }
  }
  static void put_into(std::vector<Slot>& slots, size_type& size, const K& k, V&& v) {
    const size_type mask = slots.size() - 1;
    size_type i = Hash{}(k) & mask;
    while (slots[i].state == kFull) i = (i + 1) & mask;
    slots[i].state = kFull;
    slots[i].kv.emplace(k, std::move(v));
    ++size;
  }

  std::vector<Slot> slots_;
  size_type size_ = 0;
  size_type tombs_ = 0;
};

小问答 ​

  • 这个版本差在哪？ 无 operator[]、无容量接口与 load_factor() 观测、无迭代器与 const 重载，接口只够增删查。
  • 与 std::unordered_map 的差别？ 拉链法 vs 开放寻址：本版连续存储、无每元素分配、探针顺序访存；代价是 rehash 搬移元素，且墓碑占位增加探查成本。
  • 与完整版的差别？ 缺少值初始化插入（operator[]）、容量预留、遍历与负载因子观测。
  • 复杂度与失效？ 期望 O(1)、最坏 O(n)；rehash 会使既有引用/指针失效（本版虽不提供迭代器，但 find 返回的指针同样失效）。

四、完整版：全接口 + 迭代器 ​

实现范围：上列全部接口，含前向迭代器与容量/负载因子观测；单写单线程，不含并发保护。 未实现 at、erase(iterator)、swap、merge、自定义分配器与 Robin Hood 等优化变体。

cpp
#pragma once
#include <cstddef>
#include <cstdint>
#include <functional>
#include <optional>
#include <utility>
#include <vector>

template <class K, class V, class Hash = std::hash<K>, class Eq = std::equal_to<K>>
class FlatHashMap {
  enum : std::uint8_t { kEmpty = 0, kFull = 1, kTomb = 2 };
  struct Slot {
    std::uint8_t state = kEmpty;
    std::optional<std::pair<K, V>> kv;      // 仅在 kFull 时有值，故不要求 K/V 可默认构造
  };

 public:
  using value_type = std::pair<K, V>;
  using size_type = std::size_t;

  FlatHashMap() { rehash_to(8); }

  size_type size() const noexcept { return size_; }
  bool empty() const noexcept { return size_ == 0; }
  size_type capacity() const noexcept { return slots_.size(); }
  double load_factor() const noexcept {      // 含墓碑：墓碑同样产生探查成本
    return capacity() ? static_cast<double>(size_ + tombs_) / static_cast<double>(capacity()) : 0.0;
  }

  const V* find(const K& k) const {
    if (slots_.empty()) return nullptr;
    const size_type mask = capacity() - 1;
    size_type i = Hash{}(k) & mask;                          // 容量为 2 的幂，掩码代替取模
    for (size_type probed = 0; probed < capacity(); ++probed, i = (i + 1) & mask) {
      const Slot& s = slots_[i];
      if (s.state == kEmpty) return nullptr;                 // 仅空槽终止探查，墓碑不能终止
      if (s.state == kFull && Eq{}(s.kv->first, k)) return &s.kv->second;
    }
    return nullptr;
  }
  V* find(const K& k) { return const_cast<V*>(static_cast<const FlatHashMap*>(this)->find(k)); }
  bool contains(const K& k) const { return find(k) != nullptr; }

  std::pair<V*, bool> insert(K k, V v) {                     // 已存在则不覆盖
    grow_if_needed();
    return insert_here(std::move(k), std::move(v));
  }
  V& operator[](const K& k) {                                // 不存在则值初始化插入
    if (V* p = find(k)) return *p;
    return *insert(k, V{}).first;
  }
  size_type erase(const K& k) {
    if (slots_.empty()) return 0;
    const size_type mask = capacity() - 1;
    size_type i = Hash{}(k) & mask;
    for (size_type probed = 0; probed < capacity(); ++probed, i = (i + 1) & mask) {
      Slot& s = slots_[i];
      if (s.state == kEmpty) return 0;
      if (s.state == kFull && Eq{}(s.kv->first, k)) {
        s.kv.reset();
        s.state = kTomb;                                     // 置回 kEmpty 会切断探测链
        --size_;
        ++tombs_;
        return 1;
      }
    }
    return 0;
  }
  void clear() {
    for (Slot& s : slots_) { s.kv.reset(); s.state = kEmpty; }
    size_ = 0;
    tombs_ = 0;
  }
  void reserve(size_type n) {                                // 保证容纳 n 个而不再 rehash
    if (n * 2 > capacity()) rehash_to(n * 2);
  }

  class iterator {                                           // 前向；按槽位顺序，跳过空槽与墓碑
   public:
    iterator(FlatHashMap* m, size_type i) : m_(m), i_(i) { skip(); }
    value_type& operator*() const { return *m_->slots_[i_].kv; }
    value_type* operator->() const { return &*m_->slots_[i_].kv; }
    iterator& operator++() { ++i_; skip(); return *this; }
    bool operator==(const iterator& o) const { return i_ == o.i_; }
    bool operator!=(const iterator& o) const { return i_ != o.i_; }

   private:
    void skip() { while (i_ < m_->slots_.size() && m_->slots_[i_].state != kFull) ++i_; }
    FlatHashMap* m_;
    size_type i_;
  };
  iterator begin() { return iterator(this, 0); }
  iterator end() { return iterator(this, capacity()); }

 private:
  std::pair<V*, bool> insert_here(K&& k, V&& v) {
    const size_type mask = capacity() - 1;
    size_type i = Hash{}(k) & mask;
    size_type first_tomb = static_cast<size_type>(-1);
    for (size_type probed = 0; probed < capacity(); ++probed, i = (i + 1) & mask) {
      Slot& s = slots_[i];
      if (s.state == kFull) {
        if (Eq{}(s.kv->first, k)) return {&s.kv->second, false};   // 已存在
      } else if (s.state == kTomb) {
        if (first_tomb == static_cast<size_type>(-1)) first_tomb = i;  // 记录首个墓碑，继续查找 key
      } else {                                                 // 空槽：链终止，确定落点
        const size_type at = first_tomb == static_cast<size_type>(-1) ? i : first_tomb;
        if (first_tomb != static_cast<size_type>(-1)) --tombs_;        // 复用墓碑
        Slot& d = slots_[at];
        d.state = kFull;
        d.kv.emplace(std::move(k), std::move(v));
        ++size_;
        return {&d.kv->second, true};
      }
    }
    rehash_to(capacity() * 2);                                 // 负载因子 0.5 下不可达，防御性重试
    return insert_here(std::move(k), std::move(v));
  }

  void grow_if_needed() {
    if (size_ + tombs_ + 1 > capacity() / 2) rehash_to(capacity() * 2);
  }
  void rehash_to(size_type n) {
    size_type cap = 8;
    while (cap < n) cap *= 2;
    std::vector<Slot> old = std::move(slots_);
    slots_.assign(cap, Slot{});
    size_ = 0;
    tombs_ = 0;                                                // 重哈希顺带清除全部墓碑
    for (Slot& s : old) {
      if (s.state != kFull) continue;
      put_into(slots_, size_, s.kv->first, std::move(s.kv->second));
    }
  }
  static void put_into(std::vector<Slot>& slots, size_type& size, const K& k, V&& v) {
    const size_type mask = slots.size() - 1;
    size_type i = Hash{}(k) & mask;
    while (slots[i].state == kFull) i = (i + 1) & mask;         // 重哈希时 key 必不重复
    slots[i].state = kFull;
    slots[i].kv.emplace(k, std::move(v));
    ++size;
  }

  std::vector<Slot> slots_;
  size_type size_ = 0;
  size_type tombs_ = 0;                                         // 计入负载因子，不计入 size()
};

技术选型 ​

  • 开放寻址 + 线性探测，而非 std::unordered_map 的拉链法
    • 元素存在连续数组中，无需每元素一次分配，探针也顺序访存；一条 cache line 可覆盖多个候选。
    • 代价是 rehash 会搬移元素（引用失效）、需为空槽付出内存、对哈希质量更敏感。
  • 删除留墓碑，不置回空槽
    • 置空会切断探测链：erase(b) 之后同一链上的 c 将查不到（不变量第 2 条）。
  • find 仅在空槽终止
    • 墓碑不能作为终止条件，否则整条链上位于墓碑之后的 key 都会漏查。
  • 插入时复用首个墓碑，但先确认 key 不存在
    • 复用墓碑可抑制墓碑堆积；若不先扫完探测链，同一 key 会被写入两份。
  • 容量取 2 的幂，用 & (cap - 1) 代替取模
    • 位运算更快，且探测序列可写作 i = (i + 1) & mask（无需处理回绕分支）。
  • 负载因子包含墓碑，阈值取 0.5
    • 墓碑同样产生探查成本；只看 size / capacity 会在「删多插少」时低估真实退化程度。
  • 槽内用 std::optional<std::pair<K,V>> 存放元素
    • 不要求 K / V 可默认构造，且「空 / 占用」两态表达清晰（墓碑由状态字节区分）。
  • rehash 只搬占用槽
    • 顺带清除全部墓碑，即「删除过多」的另一种修复手段。
  • 迭代器为前向、按槽位顺序
    • 哈希表本身无序，不做随机访问假设；只提供 ++ 与相等比较。

小问答 ​

  • 比精简版多了什么？ operator[]、contains、clear、reserve、capacity、load_factor 与前向迭代器。
  • 与 std::unordered_map 接口还差什么？ at、erase(iterator)、swap、merge、extract（节点句柄）、bucket_* 系列、max_load_factor 与自定义分配器。
  • 与 absl::flat_hash_map 的差别？ 后者把「控制字节」与「紧凑数据」分离，一次比较多个控制字节；本版是单数组 + 每槽 optional。
  • 遍历顺序是什么？ 槽位顺序 —— 既非 key 顺序，也非插入顺序；rehash 后全部迭代器失效。

五、边界与测试 ​

  • 空表：find 返回空、erase 返回 0、begin() == end()；
  • 重复 key：insert 返回 {现有值, false} 且不覆盖；operator[] 才覆盖；
  • 墓碑链：构造「全部 key 哈希到同一桶」的哈希函数，插 200 个后隔一删一， 验证剩余项可查出、被删项查不到，再插回被删项；
  • 增长：插入 10000 个后 load_factor() <= 0.55；reserve 之后继续插入 capacity() 不变；
  • clear() 后 size() == 0、find 全空、可继续使用；
  • 对拍：与 std::unordered_map 执行同一随机 insert / operator[] / erase / find 序列， 逐步比较 size、各 key 的值与全量元素集合；
  • 字符串 key；容器本体仅一块存活缓冲。

六、高频问答 ​

Q1. 为什么必须有墓碑？ ​

线性探测以「遇到空槽」作为查找终止条件。若删除直接置空，会截断同一探测链， 使该链上后续插入的元素无法被查到。

Q2. 墓碑会无限增长吗？ ​

会：删除多、插入少时 tombs 持续增长并推高负载因子。两个缓解手段为复用墓碑（本实现） 与触发 rehash（本实现），也可对 size / (size + tombs) 单独设阈值。

Q3. rehash 的时机与代价？ ​

size + tombs + 1 > capacity / 2 时容量翻倍；单次 O(n)，摊还 O(1)。 rehash 后所有迭代器与引用失效（元素实际搬家），这是相对 unordered_map 的主要语义代价。

Q4. 最坏情况？ ​

所有 key 冲突时探查退化为 O(n)。防御手段是随机化种子或带密钥的哈希（抗哈希洪水攻击）， libstdc++ 的 unordered_map 亦采用随机化。

Q5. 与 std::unordered_map 的取舍？ ​

后者每元素一个节点（一次分配 + 指针追逐 + 桶尾），flat 版一次分配、探针连续 （一条 cache line 可覆盖多个候选）。代价是 rehash 搬元素、为空槽付出内存、对哈希质量更敏感。

Q6. Value 不可默认构造怎么办？ ​

本实现以 optional 规避；也可手动管理生命周期 （alignas(T) unsigned char buf[sizeof(T)] + placement new + 显式析构）， 或采用「状态字节数组 + 紧凑数据数组」的两数组布局。

Q7. 删除能否不用墓碑？ ​

可以实现「后移重排」（backward shift deletion）：删除后将同链后续元素前移，直到遇到空槽。 无需墓碑且探查更短，代价是删除 O(探查长度)，且被移动元素的引用会失效。

Q8. 并发场景？ ​

读多写少可用「单写 + 发布不可变副本」（见并发件）； 原地并发需分片锁；开放寻址的无锁删除难度较高（墓碑的并发回收问题）。

Q9. 内存优化方向？ ​

小类型可分「控制字节数组 + 紧凑数据数组」，一次比较多个控制字节（absl::flat_hash_map 的思路）； 按探查距离重排的 Robin Hood 哈希可降低探查长度方差。

Q10. 与 flat_map 如何选择？ ​

需要有序遍历或范围查询选 flat_map；只需平均 O(1) 查找且不关心顺序选 flat hashmap。 两者均为「连续内存 + 一次分配」。

七、常见错误 ​

错误后果
erase 将槽置回 kEmpty探测链断裂，同链后续元素再也查不到
find 遇墓碑即返回未命中同上
插入只找首个非占用槽，不复用墓碑表被墓碑填满，探查变长
直接写入首个墓碑而未确认 key 不存在同一 key 出现两份
insert 覆盖已存在的值与 unordered_map::insert 语义不符
rehash 未重置 size_ / tombs_，或未只搬 kFull 槽size 计数错误
以 % capacity 取模却未约束容量为 2 的幂探测序列与掩码假设不一致
负载因子只统计 size，忽略墓碑删除多时性能退化
假设迭代顺序按 key 有序，或忽略 rehash 使迭代器全部失效遍历/持有引用出错

本页实现已实测：与 std::unordered_map 的 20000 步随机对拍、坏哈希下的 200 元素墓碑链、 负载因子与 reserve 纪律均通过（ASan + UBSan）；「erase 置空」与「find 遇墓碑终止」 两个经典错误以 mutation 注入后测试立即失败。

糌粑的面经笔记 · VitePress 版

整理自 xiaolincoding / cppguide / jyy OS