散列表也是一种有用的基本数据结构,本文主要关于散列表的内部机制:实现、冲突和散列函数。
为什么会需要散列表?可以考虑有关查找的情况。
如果是简单查找,时间为O(n),如果用二分查找,时间为O(log n)。但是如果能够达到每个查找的时间为O(1)的话,散列函数就有了用武之地。
散列函数
散列函数就是将输入映射到数字。散列函数必须满足一些要求。
散列函数必须是一致的,将不同的输入映射到不同的数字。
实际上散列函数能够准备指出相应的存储位置,根本不用查找。具体原因在于:
散列函数总是将同样的输入映射到相同的索引,散列函数将不同的输入映射到不同的索引。散列函数知道数组有多大,并且只会返回有效的索引。
结合散列函数和数组就可以创建一种称为散列表的数据结构。
Python提供的散列表实现为字典dict。散列表由键和值组成。
散列表适合用在模拟映射关系,防止重复,缓存数据等情况下。
冲突
前面说散列函数总是将不同的键映射到数组的不同位置。但是假如两个键分配的位置相同,就会产生冲突。那么在同一个位置就会按照链表的方式存储。
所以散列函数很重要。最理想的情况是将散列函数将键均匀的映射到散列表的不同位置。
如果散列表存储的链表很长,散列表的性能将急剧下降。所以如果使用的散列函数很好,链表就不会很长。
性能
在平均情况下,散列表执行各种操作的时间都是O(1),实际上指的是不论散列表多大,各种操作的时间都是相同的。
但是在最糟的情况下,散列表所有操作的时间为O(n)。因此在使用散列表时需要避开最糟的情况。
避开最糟的情况有两种:较低的填装因子,良好的散列函数。
填装因子
填装因子就是: 。
如果散列表的装填因子越低,发生冲突的可能性越小,散列表的性能越高。一个不错的经验是散列表的装填因子大于0.7,就调整散列表的长度。
调整散列表长度的操作需要很长时间,但是平均而言,即便考虑到调整长度所需的时间,散列表操作所需的时间也是O(1)。
良好的散列函数
良好的散列函数让数组中的值呈均匀分布。糟糕的散列函数让值扎堆,导致大量的冲突。
而什么事良好的散列函数呢?SHA散列算法就是一种常见的散列函数。
散列表小结
散列表是一种功能强大的数据结构,其操作速度快,还能让你以不同的方式建立数据模型。
你可以结合散列函数和数组来创建散列表。
冲突很糟糕,你应使用可以最大限度减少冲突的散列函数。
散列表的查找、插入和删除速度都非常快。
散列表适合用于模拟映射关系。
一旦填装因子超过0.7,就该调整散列表的长度。
散列表可用于缓存数据(例如,在Web服务器上)。
散列表非常适合用于防止重复。
领取专属 10元无门槛券
私享最新 技术干货