算法学习笔记–散列表（1）

定义

散列表可以由散列函数和数组组成，当我们查找一个变量对应的值得时候可以马上得到它的值时间将为O(1)。

散列表的内部机制

实现，冲突，散列函数

散列函数

散列函数是这样的一个函数，当我们无论输入什么数据，它输出的都是一个数字。 然后我们把这个数字作为数组的索引。 所以当我们使用散列表查找值得时候速度非常快。

冲突

理想的情况下我们希望散列函数总是将不同的键映射到数组的不同位置，但是几乎不可能编写出这样的散列函数，所以这里就会出现多个键对应一个位置的冲突问题。 最简单的方法是：如果两个键映射到了有同一个位置，就在这个位置存储一个链表。

所以一个好的散列函数非常重要，如果散列表存储的链表很长，那么散列表的速度会急剧下降。 我想能否在位置上再存储一个散列表，这样效率会很快，这只是我的想法。

python中提供的散列表就是字典。使用dict()来创建散列表。

应用

映射

将网址映射到ip地址就可以使用散列表，这个映射过程称之为DNS解析。

防止重复

使用get方法查看键是否在字典中。

用作缓存

将反复访问的数据缓存起来

良好的散列函数

良好的散列函数让数组中的值呈均匀分布。