散列查找基本概念

• 散列函数

​ 在进行查找时，在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字K为自变量，通过函数h(K)计算出该元素的存储位置，我们将h函数称为散列函数或哈希函数。h(K)的值称为散列地址或哈希地址。

• 冲突

​ 在实际应用中，通常可能出现一个待插入元素的散列地址单元已被占用情况，使得该元素无法直接存入此单元，这种情况称为冲突。

• 同义词

  ​ 具有不同关键字而具有相同散列地址的元素称为同义词，即key1≠key2，但h(key1)=h(key2)。由同义词引起的冲突称作同义词冲突。

• 装填因子(α)

  指散列表中已存入的元素数n与散列表空间大小m的比值,即：α=n/m。当α越小时，冲突可能性就越小，但同时，存储空间利用率就越低。

散列表：根据设定的哈希函数及处理冲突的方法将一组关键字映象到一个有限的连续的地址集上，即把记录存放在表中映象的位置上，这种表便称为散列表(哈希表)。

• 一个散列表的好坏与三个因素有关：1.装填因子 2、所采用的散列函数 3、解决冲突的方法