散列表
2019-10-22 本文已影响0人
迷惘_89b7
-
散列函数
散列函数是无论你给它什么数据，它都还你一个数字
-
散列表
按照首字母顺序在数组中放入元素，首字母相同时以链表方式存储
性能
平均情况下，散列表执行各种操作时间都为O(1)
最糟情况下，散列表所有操作的运行时间都为O(n)
散列表的性能
| - | 散列表(平均情况) | 散列表(最糟情况) | 数组 | 链表 |
|---|---|---|---|---|
| 查找 | O(1) | O(n) | O(1) | O(n) |
| 插入 | O(1) | O(n) | O(n) | O(1) |
| 删除 | O(1) | O(n) | O(n) | O(1) |
-
填充因子和散列函数
平均情况下，散列表的查找速度与数组一样快，而插入和删除速度与链表一样快；最糟情况下，散列表的各种操作的速度都很慢。
使用散列表时， 避开最糟情况的条件：
- 较低的填充因子
- 良好的散列函数
一、填充因子
填充因子
当填充因子接近1时，需要增大数组数组长度。
一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。
