散列表的相关概念和内容
散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。
也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。
这个映射函数称做散列函数,存放记录的数组称做散列表。
基本概念
- 关键字为$k$的值存储在$f(k)$的存储位置中,称映射$f$为散列函数,按照这个思想建立的表称为散列表。
- 对不同的关键字可能得到同一散列地址,即$k_1 \neq k_2$,而$f(k_1) = f(k_2)$,这种现象称为冲突(Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。
- 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数,这就使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。
构造散列函数的方法
若采用求余的方法,采用质数可以在一定程度上解决冲突问题。
处理冲突的方法
- 开放定址法
- 避免聚集:
- 单独链表法
- 再散列
Reference
- Computer Science: An Overview, § 9.5 Traditional File Structures.