1. 散列思想
散列表的英文叫“Hash Table”,平时也叫它“哈希表”或者“Hash表”。
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当按照键值查询元素时,用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。
2. 基本概念
2.1 散列函数
一个把查找表中的关键字映射成该关键字对应的地址的函数,记为
Hash(key)=Addr
(这里的地址可以是数组下、索引或内存地址)2.2 散列表
根据关键字而直接进行访问的数据结构。也就是,散列表建立了关键字和存储地址之间的一种直接映射关系。
2.3 冲突
散列函数可能会把两个或两个以上的不同关键字映射到同一地址,这种情况称为冲突。
这些发生碰撞不同的关键字称为同义词。
3. 装填因子
衡量哈希表中关键字的填充程度,将关键字集合占用哈希表存储单元的比例成为填充因子。