散列表(Hash Table)

2018-12-09  本文已影响0人  币来币往

散列表其实就是数组+hash函数构成。
所以它就具有了数组和hash函数的所有优点。
数组,支持按索引随机访问数组中的任意数据;
hash函数,可以将任意类型的数据映射成为一个整数(数组下标)。
所以当我们存储数据的时候,将数据存储到按hash函数计算出来的索引下面,查询的时候通过hash函数就可以找到数据所在位置的下标,就可以在O(1)时间内取到数据。

image.png

这里肯能遇到的问题是,两个key可能映射到了同一个下标值,我们把这种现象称为hash冲突。显然不能直接覆盖,否则之前存的数据就没有了。常用的解决方法有两个:

上一篇 下一篇

猜你喜欢

热点阅读