哈希表

今天做华硕的笔试题时，有道题是介绍哈希表和实现它的几个算法，虽然以前查过相关知识，但只是大概理解。

哈希表的概念

哈希表(Hash Table)也叫散列表，是根据关键码值（Key Value）而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录，以加快查找的速度。这个映射函数就做散列函数，存放记录的数组叫做散列表。

散列存储的基本思路

以数据中每个元素的关键字K为自变量，通过散列函数H（k）计算出函数值，以该函数值作为一块连续存储空间的的单元地址，将该元素存储到函数值对应的单元中。

哈希表查找的时间复杂度

哈希表存储的是键值对，其查找的时间复杂度与元素数量多少无关，哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的，因此，哈希表查找的时间复杂度为O（1）。

哈希函数的构造方法

哈希函数的构造方法：
1、直接定址法。取关键字或关键字的某个线性函数值为哈希地址。
即：H（key）=key或H（key）a*key+b
由于直接定址所得地址集合和关键字集合的大小相同，因此，对于不同的关键字不会发生冲突。但是，实际中使用这种方法的情况很少，因为随着关键字的增多，哈希表会变得很庞大。

2、平方去中位法。
取关键字平方后的中间几位为哈希地址。取的位数由表长决定。

3、还有折叠法、数字分析法、除留余数法、随机数法等

处理冲突的方法
1、开放定址法
2、链地址法

---

参考原文：
http://panlianghui-126-com.iteye.com/blog/968057
http://blog.csdn.net/chenhuajie123/article/details/9210529