基于线性探测再散列的哈希表查找效率浅析

Search Efficiency Analysis Based on Linear Detection Hash Table Lookup

哈希表的理想情况是无需比较一次存取便能找到所查的记录,但是在实际应用中,哈希表通常存在冲突的情况,这就需要反复查找处理冲突。一般的搜索方法,在搜索时需进行关键字的比较。这一类建立在比较基础上的搜索方法,其效率依赖于搜索过程中所进行的比较次数。而通过使用哈希表人们可以不经任何比较,一次存取便能得到所需的信息,从而大大提高了搜索的效率。然而,建立哈希表不可能没有冲突,解决冲突则会产生诸如堆积、二次聚集等现象,降低了查找效率。文中通过举例阐明了线性探测再散列构造哈希表的方法,并详细地分析了查找成功时和查找失败时的ASL。

The ideal condition of the hash table is to find the record without comparing an access. But in practice, the hash tableusually has a conflict situation and needs to repeatedly look for conflict. General search methods need to carry out the comparisonof key words. The efficiency of the search method based on the comparison of this class depends on the number of times in thesearch process. But by using a hash table, people can get the required information without any comparison and greatly improve theefficiency of the search. However, building a hash table cannot be without conflict. To resolve conflicts, such as the accumulationof two times, and other phenomena, reduces the search efficiency. In this paper, the method of constructing a hash table of the lin-ear detection and hash table is illustrated by an example and the efficiency of the success and the failure is analyzed in detail.