本文转自:.
1 HASH查找基本原理
在上进行查找的过程和建表的过程基本一致。假设给定的值为K，根据建表时设定的H，计算出哈希地址H(K)，若表中该地址对应的空间未被占用，则查找失败，否则将该地址中的结点与给定值K比较，若相等则查找成功，否则按建表时设定的处理冲突方法找下一个地址，如此反复下去，直到找到某个地址空间未被占用（查找失败）或者关键字比较相等（查找成功）为止。
2 查找算法演示
著名的ELFhash算法:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | int ELFhash(char *key) { unsigned long h=0; while(*key) { h=(h<<4)+*key++; unsigned long g=h&0Xf0000000L; if(g) h^=g>>24; h&=~g; } return h%MOD; } |
开放寻址法：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | HashTable InitializeTable( int TableSize ) { HashTable H; int i; /* 为散列表分配空间。 */ /* 有些编译器不支持为 struct HashTable 分配空间，声称这是一个不完全的结构， */ /* 可使用一个指向 HashTable 的指针为之分配空间。 */ /* 如：sizeof( Probe )，Probe 作为 HashTable 在 typedef 定义的指针。 */ H = malloc( sizeof( struct HashTable ) ); /* 散列表大小为一个质数。 */ H->TableSize = Prime; /* 分配表所有地址的空间。 */ H->Cells = malloc( sizeof( Cell ) * H->TableSize ); /* 地址初始为空。 */ for( i = 0; i < H->TableSize; i++ ) H->Cells[i].info = Empty; return H; } |
查找空单元并插入：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | Position Find( ElementType Key, HashTable H ) { Position Current; int CollisionNum; /* 碰撞次数初始为0。 */ /* 通过表的大小对关键字进行处理。 */ CollisionNum = 0; Current = Hash( Key, H->TableSezi ); /* 不为空时进行查找。 */ while( H->Cells[Current].info != Empty && H->Cells[Current].Element != Key ) { Current = ++CollosionNum * ++CollisionNum; /* 向下查找超过表范围时回到表开头。 */ if( Current >= H->TableSize ) Current -= H->TableSize; } return Current; } |
3 性能分析
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
(1)散列函数是否均匀；
(2)处理冲突的方法；
(3)散列表的载荷因子。