顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较**。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN )**，搜索的效率取决 于搜索过程中元素的比较次数。 理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过 某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函 数可以很快找到该元素。 当向该结构中：

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表 (Hash Table)(或者称散列表)。 例如：数据集合{1，7，6，4，5，9}； 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。 用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快 问题：按照上述哈希方式，向集合中 插入元素44，会出现什么问题？ 答案是： Hash（44） = 44 % 10 = 4；与元素4映射到了形同的位置，我们将这样子的情况称为“哈希冲突”。

对于两个数据元素的关键字K1 和 K2 ，有K1 ！= K2，但有Hash（K1） = Hash（K2），即：不同关键字通过 相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。 把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 那么发生哈希函数该如何处理呢？

引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则：

解决哈希冲突两种常见的方法是：闭散列和开散列。 1.闭散列 闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？ （1）线性探测 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。