基本概念
散列方法(hashing)
:一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法。以最基本的向量作为底层支撑结构,通过适当的散列函数在词条的关键码与向量单元的秩之间建立起映射关系。
散列表(hashtable)
:逻辑上由一些列可存放词条(或者其引用)的单元(称作桶(bucket)
或桶单元
)组成。各桶单元按照其逻辑次序在物理上连续排列。通常直接使用数组进行排列,这时散列表也称作桶数组(bucket array)
地址空间(address space)
:如果桶数组的容量为R,则其中合法秩的区间[0,r)也称作为地址空间。