#hashtable #algorithm # Video - [CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”](https://www.youtube.com/watch?v=ncHmEUmJZf4) - 如果 Hashtable 能放到L1，性能取决于指令个数；否则，取决于 L1 Cache miss ## new_set - Separate chaining 结构 - 链表元素可以不存储 hash code（只存储 value），hash 可以让用户存到自己的 Value 里。 ## dense_hash_set - Open Address 结构 - 删除需要写 tomestone 标记 - 计算 load factor 时，tomestone 也计入在内 ## flat_hash_set - **Metadata** - 每个 slot 对应一个 control byte，存储 hash code 的低 7 位，可以减少比较 value - hash code（64 bits）分为两个部分 H1 和 H2 1. H1：高 67 bits 用于定位 slot 2. H2：低 7 bit 存储在 control byte - **Control Byte** - 1000 0000 // Empty - 1111 1110 // Deleted - 1111 1111 // Sentinel - 0xxx xxxx // Full，x 对应 H2 - 大多数 probing 都发生在 control bytes 上，它很小，L1 cache 利用率很高。还可以使用 **SSE** 指令加速。 - **Group** - 16个 slots 为 1 组，对应 16 个 ctrl bytes - 一个 Table 包含 N 个 groups - group = H1(hash) % num_groups_ - 删除时如果 group 内任意元素为空，则指定 slot 不需要标记为 Deleted，只需要标记为 Empty - 好处：不会损害 load factor ## Experiments - Arbitrary group positions - group 可以从任意 slot 作为起始，不需要对齐 16 - 坏处：insert 时有时需要写两个 control bytes - 好处：提升 load factor 从 7/8 到 15/16 - Cache line aware groups（node only） - metadata 放在 group 之前，不再独立，都存储在一 CL 中 -----------