基于哈希的搜索算法

文摘

多年来,计算机科学家参与研究线性搜索和二进制搜索发现哪一个是更快。这是两个搜索技术二分查找数组的条件必须是顺序,但在线性搜索,没有必要。但在本文中提出了一种新的搜索算法既适用于有序和无序数组,因为在本文中,我们提出了基于哈希的搜索技术搜索给定数组中的元素。

关键字

搜索技术,线性搜索,二分搜索算法,基于散列搜索技术

介绍

搜索特定元素在计算机算法是很常见的任务。但在现实生活中应用程序的数组元素代表一个对象数组。任何搜索算法的主要目标是找到特定的搜索用户想要搜索的元素。但任何搜索算法的主要两个截然不同的任务是存储过程的一个关键的过程,另一个是检索的关键,顺序搜索算法是一个非常简单的算法中,如果发现搜索元素,想搜索然后过来给搜索元素如果不是那搜索到最后一个元素的数组。该算法适用于当数组中元素的数量非常少。在二叉搜索条件是,数组必须以排序顺序。二进制搜索算法是基于划分和克服方法,搜索时间非常少,比较其他搜索技术。也适用于大量的元素。

二世。线性搜索算法

最简单的方法搜索一个元素的线性搜索[1][2][3][4][7]。简单地检查第一项,然后第二个像数组中搜索所有在场的项目吗?线性搜索算法遵循

对于小数量的数组元素线性搜索非常快比较其他搜索算法。主要有两种类型的线性搜索一个阶线性搜索,另一个是无序的线性搜索。线性搜索的优点是:线性搜索检查每个列表项直到找到目标或最后一个元素的数组。线性搜索的复杂性在坏的情况下(N),在最好的情况下(1)。

三世。二进制搜索算法

二分搜索的策略[5][6][7][8][9]是检查列表中的元素的中间。如果键值小于中间值然后搜索左侧到0。,继续这个过程,直到N如果键值大于中间值。二进制文件Log (N)的复杂性。

这是二进制搜索算法的主要步骤是遵循

第四,基于散列的搜索算法

基于散列搜索算法[6][7]表明每个数组元素与特定的索引值和散列索引值的函数形式的M mod N (M是索引值和N是用户定义的数字)。基于哈希的搜索算法是不取决于订单或无序列表。然后地图索引值的散列值,然后定义元素的特定的地址。然后定义地址值的特定值。这增加了算法的搜索速度散列基本搜索技术的复杂性是少那么Log (N)。基于哈希算法的搜索算法是遵循Algorithm3所示。

诉的结论

在本文中,我们提出了一种新的搜索算法和比较现有的复杂性和提议。线性搜索的复杂性是N, Log (N),因为它使用二叉搜索分而治之的方法但在提出一个使用哈希函数搜索的复杂性是非常少与其他现有的一个。所以在未来我们实现一个算法的复杂性是少了这两种算法对秩序和无序列表。

表乍一看

表1 表2

引用

1. Booch G。,Object Oriented Analysis and Design, second Edition, Addison-Wesley. 1995.
2. 柯林斯w·J。,Data Structures, first Edition Addison-Wesley publishing company, page 397,1992, U.S.A.
3. 唐纳德·K。,The Act Computer Programming, Volume 3, Sorting and Searching, Third Edition, Addison-Wesley, 1997.
4. 霍洛维茨·e·萨尼,基本的计算机算法,计算机科学出版社,Inc,马里兰州,1978年,美国
5. Josuttis n·M。,The C++ Standard Library; A Tutorial and Reference, Addison-Wesley, Reading, M.A, 1999.
6. 克鲁斯r . L。,Data Structures and Program design in C++, Prentice Hall, page 280, 1999, USA.
7. 罗杰J。,Searching Arrays:Algorithms and Efficiency linear versus Binary Search, Rai Unversity, 2007.
8. http:en.wikipedia.org/wiki/binarysearchalgorithm),最后于2008年9月20日通过。
9. Stroustrup b, c++的设计和演化,addison - wesley阅读m ., 1994年。