我正在处理一个练习问题，涉及设计一个直接地址表，可能具有非不同的键。约束是 INSERT、DELETE 和 SEARCH 应该在 O(1) 时间内运行；arguments 是指向设置对象的指针。
一种明显的解决方案是使用链接，表条目指向链表的头部（可能为 NULL）。有了这样的链接，INSERT 和 DELETE 肯定会在 O(1) 时间内运行，但是，SEARCH 不会......任何建议都将不胜感激。
问问题
527 次
1 回答
1
根据您是否要存储 {unique, non-unique} 和 {keys, key-values} 来研究 STL 关联容器std::unordered_set、std:unordered_map、std::unordered_multiset、std::unorderd_multimap的设计。如果您没有 C++11 编译器（例如 MSVC++ >= 2010 或 gcc >= 4.4），您可以使用Boost.Unordered。
更新： 如果您专门寻找 C 库：请查看http://attractivechaos.wordpress.com/2008/09/02/implementing-generic-hash-library-in-c/
于 2012-05-04T14:18:37.037 回答