散列表(二) 散列表(二)

点击蓝字“莫名Coder”关注我哟
加个“星标★”，每日良时，好文必达！

文章图片

散列表
散列表冲突在我们学习的大多数语言中，提供了散列表实现，你不用知道它们如何实现，有鉴于此不必讨论内部原理，但你需要知道散列表的性能，如果想知道散列表的性能，那么搞清楚什么是冲突？
问题：超市中，我们将苹果的价格存储到散列表中，分配的是第一个位置，接下来，将香蕉的价格存储到散列表中，分配第二个位置。一切顺利，但现在你要将梨的价格存储到散列表中，分配给你的是第一个位置。不好，这个位置是苹果的，那么就会覆盖苹果的价格，这种情况就是冲突，给两个键分配的位置相同。
如何处理？最简单的办法，如果两个键映射到了一个位置，那么这个位置存储一个链表。
如果说链表很短，那么查询速度就会很快，但是，如果很长，那么就很慢。
散列表性能前面所学中，简单的查找我们运行时间就是线性时间，二分查找的速度更快，则是对数时间，在散列表中查询它的时间为常量时间O(1)。
在最糟的情况向，散列表所有操作的运行时间是O(n)---线性时间。在平均情况下，散列表的查找速度和数组一样快，在最糟的情况下，散列表的各种操作速度都很慢，因此在使用散列表的时候，避开最糟情况就很重要。避免冲突需要有：