问个hash table 哈的设计问题，谢谢。

susesuse_cu

最近要做的程序想用hashtable 保存100万个节点<key, value>，每个节点估计大小为100字节。节点是逐渐增加然后稳定到一百万。
我想问的是如果把bucket数搞成1万，每个bucket的链表上大概有100个节点。这样的话load factor 大概在100左右，这样的insert, lookup效率会怎么样？
还没写程序，不知道会怎样。有做过的人指点下吗？谢了！

liexusong

你怎么不把桶设为10w呢？

susesuse_cu

10万个桶倒是值得考虑。因为我这个程序会有16个线程来访问hash table, 然后我想的是每个bucket会有一个mutex保护只有一个线程访问。这样的话100万个节点放进hash table里，我需要10万个桶，10万个mutex。效率能保证吗？有什么其它好的设计方法吗？好像还是固定桶数比较好，动态resize不太好。我是没这方面的经验，呵呵。

samlumengjun

如果key是连续的,那么最好设置100万个桶,这样比多线程要快得多.单线程不需要锁.

susesuse_cu

顶一个，继续问！

wells-xu

为什么是16个线程，是不是设计有问题？
感觉服务器线程越少越好

zhangsuozhu

主要看桶里的数据结构如何组织了。

如果查询远大于修改操作。可以用红黑树在桶里存储冗余的结点。

如果查询与修改大体相当。用普通的链表好了。做树平衡旋转不值得了。

当然，如果写红黑树比较麻烦，花心思在这上面，不如好好设计下hash算法。
使100万桶里每个桶里结点尽可能为1个。这样最快。

mirnshi

搞得这么复杂。直接上memcache

susesuse_cu

4核服务器线程数最好在8个吧？ 我这个应用查询数和修改数差不多，每个bucket可能用双向链表做。
貌似hash + doubly linked list主要是为了LRU(least recently used)的cache 的想法吧。如果我只是要insert, update, lookup, check timeout(如果超时就delete)这几个操作，单向链表也可以吧？双向链表有啥特别的好处吗？

fallening

貌似几乎每个版本的stl都带了hash