若结构中存在关键字和相等的记录，则其必定在的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系为散列函数，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即，但是，这种现象被称为冲突；并且具有相同函数值的关键字对该散列函数来说被称为同义词。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

根据散列函数和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。常见方法有以下五种：

取关键字或关键字的某个线性函数值为散列地址。即或，式中均为常数（这种散列函数叫作自身函数）。

假设关键字是以为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k)=kmodp,p≤m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

，式中,为散列函数，为散列表长，为增量序列，可有下列3种取法：，称为线性探测再散列；，称为二次探测再散列；

1. ，称为随机探测再散列。

，式中为不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

将所有哈希地址为的元素构成一个称为同义词链的链表，并将链表的头指针存在哈希表的第个单元中，因而查找、插入和删除主要在同义词链中进行。

散列表的查找过程和构造过程基本相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。

因此，影响产生冲突多少的因素，也就是影响查找效率的因素，主要有以下3个：①散列函数是否均匀。②处理冲突的方法。③散列表的装填因子。

其中散列表的装填因子定义为：

由于表长是定值，与“填入表中的元素个数”成正比，所以，越大，填入表中的元素较多，产生冲突的可能性就越大；越小，填入表中的元素较少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是装填因子的函数，只是不同处理冲突的方法有不同的函数。