google code上有个著名的hash map类库，今天看了一下文档,聊做记录:
sparse hashmap: 空间高效
dense hashmap:时间高效
sparse hashmap使用的数组(sparsetable),按M分为一组,每组用数组存储数据(虽然链表速度更快，但空间多),bits做查找。M越大内存overhead越小,在323位机器上是2bits,64位机器上是2.5bits,适合做持久化操作，做hash时使用二次内部探测(quadratic internal probing),一般查找需要4-5次。
dense hashmap和一般hash map实现差不多，只是冲突解决用二次内部探测，一般查找是table[i], table[i + 1],table[i + 3]这样，这些数组元素一般就大一个缓存行内，因此很高效，使用内存比标准的hash map多，但是性能可以到两倍左右。另外其中判断empty,delete,是在entry上做的，需要set_empty_ key,set_deleted_key。
最后还提到hash function对性能的重要性，有时间研究一下。
参考:
https://code.google.com/p/sparsehash/
http://sparsehash.googlecode.com/svn/trunk/doc/implementation.html
http://sparsehash.googlecode.com/svn/trunk/doc/performance.html
Google Dense Hashmap和Sparse HashMap,布布扣,bubuko.com
Google Dense Hashmap和Sparse HashMap
原文：http://blog.csdn.net/jollyjumper/article/details/23627037