问考虑L1缓存小的O(Log N)查找和更新的数据结构怎么设计？

EN

我建议实施Cuckoo Hashing机制(见http：//en.wikipara.org/wiki/cuckoo_hashing）。通过使用更多的散列函数，可以获得50%以上的负载因子(即将内存消耗从8N降低到7N)。“只使用三个散列函数就会将负载增加到91%。“

维基百科：

Zukowski等人的一项研究表明， cuckoo散列比链式散列要快得多。小的高速缓存驻留哈希表在现代处理器上。Kenneth Ross展示了 cuckoo哈希(使用包含多个键的存储桶的变体)的分块化版本，在空间利用率很高的情况下，它比传统方法更快。Askitis进一步研究了分解 cuckoo哈希表的性能，并与其它散列方案进行了比较。

std::set通常提供O(log(N))使用二进制搜索树插入和删除。大多数基于指针的使用了3*N空间。假设Word大小的数据，1表示数据，2表示指向每个节点上左和右子节点的指针。

如果你有一些常数N，可以保证ceil(log2(N))小于单词大小的一半，可以使用一个固定长度的树节点数组，每个树节点2。*n号。数据使用1，两个子节点的索引使用1，存储为单词的上、下半部分。这是否允许使用某种方式的自平衡二进制搜索树取决于N和字大小。对于一个16位系统，你只能得到N=256，而32位是65k。

既然你有有限的N，可以用std::set<short, cmp, pool_allocator> B带着Boost‘spool_allocator。