散列表

什么是 散列表?

　散列表（Hash Table，即哈希表）是根据键值（Key）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

为什么要有 散列表?

可以提供快速的插入操作和查找操作

　不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即 O(1) 的时间级
　实际上，这只需要几条机器指令
　哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器），而树的操作通常需要 O(N) 的时间级

编程实现相对容易

散列表工作机制

存储

　使用一个数组实现的无序符号表
　意味着, 数组创建后，难于扩展（某些哈希表被基本填满时，性能下降得非常严重）
　要么预设足够的空间，要么定期将数据迁移到更大的哈希表