第10.9章: Swiss 表：无序且可扩容

1. 它有什么不同

str_swiss_set 与 str_swiss_map 是哈希表。它们计算键的哈希，把元素放进由该哈希选定的槽位，而不是让键保持有序。三个后果决定了你该怎么用它们：

• 没有顺序。遍历顺序由哈希决定。对相同输入它是可复现的，但它既不有序，也不是插入顺序。绝不要基于它构建逻辑。
• 大小是已知的。size() 与 capacity() 既精确又便宜，reserve() 让你能一次把表的大小定下来。
• 只有键操作。contains、find_key、insert_key、erase_key。没有 lower_bound，没有 front()/back()：那些都需要哈希表并不具备的顺序。

#include <fast_io_dsal/str_swiss_set.h>
#include <fast_io.h>

using namespace ::fast_io::io;

int main()
{
	::fast_io::str_swiss_set s;
	for (auto k : {::fast_io::cstring_view("hello"), ::fast_io::cstring_view("world"),
				   ::fast_io::cstring_view("foo")})
	{
		s.insert_key(k);
	}

	println("size: ", s.size(), " capacity: ", s.capacity());
	println("contains foo: ", s.contains("foo"));
	for (auto const &e : s) { println("  ", e); }
}

size: 3 capacity: 15
contains foo: 1
  world
  hello
  foo

注意遍历顺序：既不是有序的，也不是插入顺序。

2. size()、capacity()、reserve()

哈希表必须知道自己有多满 — 它就是这样决定何时增长的。所以计数本来就在手边，你免费拿到它：

println(s.size());       // elements currently stored
println(s.capacity());   // slots currently allocated
println(s.is_empty());   // size() == 0

capacity() 与 size() 不是同一个数：表会让一部分槽位保持空闲，使探测保持简短。当表被填满时，它会增长，并把每个键重新哈希进一张更大的表。

如果你知道要来多少个键，reserve(n) 可以一次在开头把表扩好，这样后续插入不会反复触发增长：

println(s.capacity());   // 15
s.reserve(100zu);
println(s.capacity());   // 127 — big enough for 100 keys
println(s.size());       // 3 — reserve never changes the elements

15
127
3

3. 插入与删除

插入函数返回一个小结构体而不是裸 bool，因为哈希表知道自己碰了哪个槽位，并把迭代器交给你：

auto r{s.insert_key("alpha")};
println(r.inserted);      // 1 — the key was new
println(*r.position);     // alpha — iterator to the element

auto dup{s.insert_key("alpha")};
println(dup.inserted);    // 0 — already present, nothing changed

删除仍然是 B 树容器那套 erase_key / erase(it) / erase(first, last) 家族，边遍历边删除的循环形状也一样（第10.6章）：

for (auto it{s.cbegin()}; it != s.cend();)
{
	::fast_io::string_view k{*it};
	if (k.starts_with(::fast_io::string_view("w")))
	{
		it = s.erase(it);   // returns the next occupied slot
	}
	else
	{
		++it;
	}
}

size after erase: 2
  foo
  hello

从哈希表中删除可能把某个元素搬进它留下的空洞，所以你在删除之前保存的任何迭代器或键视图都已经失效（第10.11章）。

4. 读写映射值

读是 find_key，写是赋值函数。两次调用，两种含义：

::fast_io::str_swiss_map<::std::size_t> m;
m.emplace_key("a", 1zu);                       // insert if new
m.insert_key_or_assign("a", 100zu);            // replace either way
println(m.find_key("a")->mapped());            // 100
println(m.size());                             // 1

要就地更新值而不是替换它，就用非 const 的映射做遍历 — 非 const 迭代器暴露可写的 mapped()：

for (auto &e : m)
{
	e.mapped() += 1zu;
}
println(m.find_key("a")->mapped());   // 101

find_key 即使在非 const 映射上也返回 const_iterator，所以 m.find_key(k)->mapped() 只能读不能写。规则就是这些：查找只读，所有修改要么来自插入/赋值函数，要么来自遍历。

哈希器是类型的一部分（默认是 ::fast_io::native_swiss_hasher）。你很少需要写出它；如果要写，它是第三个模板参数，而 hash_function() 返回它的一份副本。

5. 什么时候 Swiss 表是正确的选择

当每个问题的答案都是“这个确切的键”时，就该用 Swiss 表：

• 成员判断：这个 token 在表里吗？
• 值查找：这个名字对应哪条记录？
• 流式输入时去重。
• 以字符串为键的缓存和索引。

而当问题涉及范围或顺序时，就留在 B 树这边：“所有以这个前缀开头的键”、“最小的那个”、“这个之后的下一个”。哈希表不扫遍全部就无法回答其中任何一个。

要点

• str_swiss_set / str_swiss_map 是哈希表：只支持精确键操作，没有顺序。
• 遍历顺序是任意的，但可复现；绝不要依赖它。
• size()、capacity() 和 is_empty() 都很便宜；reserve(n) 一次定好表大小，使批量插入不会反复重新哈希。
• insert_key 返回 {position, inserted}；inserted 告诉你这个键原本是不是新的。
• erase_key、erase(it)、erase(first, last) 的行为与 B 树家族一致。
• 写通过 insert_key_or_assign / emplace_key 或非 const 迭代器；读通过 find_key。
• find_key 给出 const_iterator：只读。