数据结构系列之二 散列表

Reszing

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

申请新的数组

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

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

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

总结

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180622G0NCSX00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券