哈希表(HashTable) 是一个经典的数据结构，只要写点过代码，应该都有用过哈希表。每种语言都有自己的哈希表实现，基本都是开箱即用。以至于虽然用过哈希表的人很多，但自己动手写过哈希表的人估计没多少吧。
要设计一个高性能的哈希表，其实还是有不少细节需要考虑的。比如如何处理哈希冲突，如何处理哈希表扩容等。一些成熟的哈希表实现，比如 C++ 标准库中的哈希表，代码量比较大，也比较难理解。
好在 LevelDB 在实现 LRU Cache 的时候，顺便实现了一个简单高效的哈希表，整体代码写的很精简，麻雀虽小五脏俱全，非常值得学习。本文以 LevelDB 的哈希表实现为例，分析下如何设计一个高性能的哈希表。
在上篇 LevelDB 源码阅读：跳表的原理、实现以及可视化中，详细分析了 LevelDB 中跳表的实现。然后在 LevelDB 源码阅读：如何正确测试跳表的并行读写？ 中，分析了 LevelDB 跳表的测试代码，最后还剩下一个问题，怎么分析跳表的时间复杂度呢？
在分析完跳表的时间复杂度之后，就能明白 LevelDB 中概率值和最大高度的选择，以及 Redis 为什么选择不同的最大高度。最后本文也会提供一个简单的压测代码，来看看跳表的性能如何。
本文不会有很高深的数学知识，只涉及简单的概率论，可以放心往下看。跳表的性能分析有不少思路很值得借鉴，希望本文能抛砖引玉，给大家带来一些启发。
在知道 LevelDB 的原理和实现后，我们可以推测出来，在极端情况下，每个节点的高度都是 1，那么跳表的查找、插入、删除操作的时间复杂度都会退化到 O(n)。在这种情况下，性能比平衡树差了不少。当然，因为有随机性在里面，所以没有输入序列能始终导致性能最差。
那么跳表的平均性能如何呢？前面给出过结论，和平衡树的平均性能差不多。引入一个简单的随机高度，就能保证跳表的平均性能和平衡树差不多。这背后有没有什么分析方法，能够分析跳表的性能呢？
在上篇 LevelDB 源码阅读：跳表的原理、实现以及可视化中，从当前二叉搜索树和平衡树的一些缺点出发，引出了跳表这种数据结构。然后结合论文，解释了跳表的实现原理。接着详细分析了 LevelDB 的代码实现，包括迭代器实现，以及并行读的极致性能优化。最后还提供了一个可视化页面，可以直观看到跳表的构建过程。
但是还有两个问题：
接下来通过分析 LevelDB 的测试代码，先来回答第一个问题。跳表的性能定量分析，放到另外单独一篇文章。