|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
根据设定的哈希函数和处理冲突的方法，将一组关键字映射到一个有限的、连续的地址集（区间）上，并以关键字在地址集中的"像"作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。
|
|
|
|
对于哈希表，主要考虑两个问题：一是如何构造哈希函数；二是如何解决冲突。
|
|
|
|
|
|
常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
|
|
|
|
|
|
常见的处理冲突的方法有开放地址法、链地址法、再哈希法、建立一个公共溢出区。
|
|
|
|
|
|
|
|
（1）虽然哈希表在关键字与记录的存储位置之间建立了直接映像，但由于冲突的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程，因此，仍须以平均查找长度衡量哈希表的查找效率。
|
|
|
|
（2）查找过程中须与给定值进行比较的关键字的个数取决于哈希函数、处理冲突的方法和哈希表的装填因子3个因素。哈希表的装填因子定义为
|
|
|
|
|
|
式中，α表示哈希表的装满程度。直观地看，α越小，发生冲突的可能性就越小；反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
|
|
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
|
|
|
|
|
|
根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。当选择了某个散列函数后，不同的关键字可能与同一个散列地址相对应，这种现象称为冲突。
|
|
|
|
对于哈希表，主要考虑两个问题：一是如何构造哈希函数，二是如何解决冲突。
|
|
|
|
|
|
常用的哈希函数的构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
|
|
|
|
|
|
解决冲突就是为出现冲突的关键字找到另一个"空"的哈希地址。常见的冲突处理方法有：开放地址法、链地址法、再哈希法等。
|
|
|
|
|
|
|
|
|
|
|
|
|
