散列表

1.散列表

Hash表是一种支持高效的查找，插入，删除操作的数据结构，高效的设计目标是时间复杂度为O（1）

概念：

1. 散列函数：数据元素的关键字和该元素的存储位置之间的对应关系。
                由散列函数觉得存储位置的存储结构称为散列表。
                实质：关键字集合到地址集合到映射。
2.  冲突： 多个关键字 映射到 同一个存储位置；
                         
构造散列表的关键：如何减少冲突 以及 如何有效处理冲突

2.散列函数

好的散列函数的标准： 使散列地址均匀的分布在散列表中，尽量避免或减少冲突。

常用散列函数：
    1.  直接定址法；
    2.  除数取余法；
    3. 平方取中法；
    4.  折叠法：把关键字拆成几部分，按照某种约定把这几部分组合在一起；

3.冲突处理

1. 开放定址法:
    
    设计一个关键字key，散列地址为i=hash(k),若散列表中i的位置已经存储元素，则产生冲突，探测下一个i＋1位置是否为空，若空，则存储该元素；否则继续探测下一个位置i＋2，以此类推，直到找到一个空的位置。

缺点：使非同义词也产生冲突，并堆积在散列表的一段区域，极速降低查找效率。

2. 链址法

3. 线性探测再散列法

4. 二次线性再散列；

参考博客：
浅谈算法和数据结构: 十一 哈希表 http://www.cnblogs.com/yangecnu/p/Introduce-Hashtable.html