如何解决哈希表的拉链法的缺点？

Question

也就是拉链特别长的时候，有什么好办法能够解决的吗？主要是为了解决查询的效率问题，我想过把拉链变为一棵红黑树，除了这个办法以外还有什么好办法吗？

Answer 1

一般是引入rehash机制，通过判断哈希表的桶的比例，当超过1/2等时，就自动扩充哈希表的桶到2倍。这样就可以降低拉链的长度等。