7.5.1散列表的基本概念

知识总览：

散列表、散列函数：

散列表是一种新的数据结构，每一个散列表都会配套一个散列函数，即设计散列表时就要设计散列函数。散列函数的作用是可以根据数据元素的关键字(关键字就是指这个数据元素代表的值)去计算出这个数据元素在散列表中的存储地址，即根据数据元素映射在散列表的存储地址

如下例子：散列表长度为13，给出散列函数H(key)=key%13，即数据元素在散列表存储位置的计算方式是数据元素对13取余，一组数据元素19,14,23插入散列表，19在散列表存储位置=H(19)=19%13=6,即19存储在散列表位置为6的位置，14在散列表存储位置=H(14)=14%13=1,14存储在散列表1的位置，H(23)=23%13=10，即23存储在散列表10的位置

理想情况，散列表查找数据元素的时间复杂度O(1)。因为可根据散列函数马上定位到数据元素在散列表中的位置，再确定位置上是不是目标关键字，如果是就是查找成功，如果不是查找失败

冲突、同义词：

冲突：在散列表插入数据元素时，根据散列函数计算出的应存在散列表的地址上已经有了其他元素，这种情况就叫冲突或碰撞。冲突发生的越少，散列表的性能就越高

同义词：不同的关键字经过散列函数映射到同一个存储地址，那么这些关键字就是同义词。不同的关键字可能换个散列函数，就没有冲突的情况或不属于同义词了。

如何减少冲突：

构造更合适的散列函数，尽量让不同的数据元素通过散列函数落在散列表不同的位置上，但是再怎么构造合适的散列函数，可能还是会发生冲突，即冲突不可避免

 

冲突不可避免，如何处理冲突：

使用拉链法和开放定址法

拉链法：由冲突造成的同义词，会用拉链把所有的同义词连起来

开放定址法：由冲突造成的同义词，会给后插入的元素再找一个空闲的位置来存储，但是根据什么规则来找空闲的位置。。。。。。

知识回顾：

又水一篇。。。。。。。。