散列表

发布于 2020-04-02 作者 风铃 51次 浏览 版块 前端

什么是 散列表?

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

为什么要有 散列表?

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

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

编程实现相对容易

散列表工作机制

存储

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

收藏
暂无回复