搜索:从数据集合中找出目标元素
(当然是越快越好了)
基本的搜索算法有如下三种:
线性搜索、二分搜索、散列搜索。
线性搜索:从头到尾依次查找目标元素,已经找到则返回,效率低但可用于任何形式的数据。O(n)
二分搜索:作用于已排好序的数据集,将搜索目标指向之间,经过判断取其中的一边再搜索。(可以在极短时间内完成搜索) O()
散列搜索(利用哈希值):利用关键(值)带入特定散列函数找其位置,效率极高。
线性搜索:
二分搜索:
散列搜索:
双散列函数:以h1(k)为基底若发生冲突,则以增加h2(k)个单位。
(i是冲突次数)
H(k) = h(k,i)
= ( h1(k) + i * h2(k) ) % m
(m为总基数)