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