发布于 2020-04-02 作者 风铃 258次 浏览 版块 前端
散列表(Hash Table,即哈希表)是根据键值(Key)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表
不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即 O(1)
的时间级
实际上,这只需要几条机器指令
哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器),而树的操作通常需要 O(N)
的时间级
使用一个数组实现的无序符号表
意味着, 数组创建后,难于扩展(某些哈希表被基本填满时,性能下降得非常严重)
要么预设足够的空间,要么定期将数据迁移到更大的哈希表