算法(15)-哈希表

哈希表

Hash table，也叫散列表。

数组就是一张哈希表。

哈希表主要用于快速判断元素是否在一个集合里面。

哈希函数

哈希函数就是将值映射为哈希表上的索引。

哈希碰撞

哈希碰撞是指多个值映射到了同一个索引。

拉链法

线性探查法

哈希结构

• 数组
• 集合(Set)
• 映射(Map)

总结

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

哈希法牺牲了空间换取了时间。