数据结构系列之二 散列表

Reszing

哈希表一定是动态的，当数组无法满足需求时，就要扩展，这个时候就面临两个开销巨大的操作：

申请新的数组

重新计算已有的每个key的索引位置，并放入新数组

所以，我们在使用哈希表的时候，应该尽量的避免在使用的时候频繁的扩容，应该对使用需求有一个大概的估算。

在 JDK1.8中，HashMap 有一些比较大的变化。同时用了一些巧妙的技巧，使得重新计算索引的时间降低很多。这个有兴趣的同学可以读一下源码，并不复杂。

总结

上面讲了 哈希表最重要的3个地方，这也是我们实现自己的哈希表的三个比较重要的点。对于哈希函数来说，现代语言都会提供一些库来实现各种类型的哈希。对于我们自己的类型进行哈希的时候，就要对实际进行考量。实现一个分布均匀的哈希函数。在需要高性能的地方，一个哈希函数满足所有需求的“银弹”是不存在的。