顺序查找,二分查找,哈希查找的使用方法和总结
程序员文章站
2024-03-19 15:20:04
...
顺序查找
顺序查找是最普通的一种查找方式,它的基本原理:将要查找的元素与从线性表的开始到最后的每个元素进行逐个比较,看是否有匹配的
话不多说上代码:
public class Demo4 {
//顺序查找
static ArrayList<Integer> list=new ArrayList<Integer>();
public static void main(String[] args) {
//填充数组
list.add(99);
list.add(88);
list.add(22);
list.add(33);
list.add(44);
//输出数组
for(int i:list){
System.out.print(i+" ");
}
System.out.println();
//顺序查找
System.out.println(search(88));
}
//在list中按顺序查找,若成功返回其下标,否则返回-1
static int search(int a){
for(int i=0;i<list.size();i++){
if(a==list.get(i)){
return i;
}
}
return -1;
}
}
由此看出: 需要查找的数组中的数越多,所需要的时间越多,但平均时间永远都是0毫秒。
二分查找
二分查找是一种非常常用的查找算法,二分查找也叫折半查找。
二分查找的前提条件是线性表是有序的,这样每比较一次就可以排除掉一般的数据元素
Java中自带了二分查找算法,所以一般也不需要我们自己去实现二分查找算法。
话不多说上代码:
public class Demo5 {
//二分查找
public static void main(String[] args) {
ArrayList<Integer> list=new ArrayList<Integer>();
//填充数组;
list.add(55);
list.add(22);
list.add(66);
list.add(99);
list.add(33);
//需要查询的数字
int a=66;
//数组排序 ( Collections是辅助类)
Collections.sort(list);
//输出数组
for(int i:list){
System.out.print(i+" ");
}
System.out.println();
//二分查找
int pos=Collections.binarySearch(list, a);
System.out.println(pos);
}
}
由此看出: 和顺序查找一样,需要查找的数组中的数越多,所需要的时间越多,但平均时间永远都是0毫秒。因为是折半查找,它的速度会比顺序查找的速度快很多。
哈希查找
哈希是一种映射,哈希表是一种用空间换取时间的做法,哈希查找可以通过“计算”而不是“查找”得到目标地址。
话不多说上代码:
public class Demo6 {
//哈希查找
public static void main(String[] args) {
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
//填充数组
map.put(1, 11);
map.put(6, 66);
map.put(3, 33);
map.put(5, 55);
map.put(4, 44);
//输出数组
Set<Integer> keySet = map.keySet();
Iterator<Integer> it1 = keySet.iterator();
while(it1.hasNext()){
Integer a = it1.next();
System.out.print (a+"-"+map.get(a)+" ");
}
System.out.println();
//哈希查找
System.out.println(map.get(3));
}
}
由此看出:由于是通过计算得到的目标地址,它的查找速度是最快的
总结:顺序查找<二分查找<哈希查找
由于本人还是一个小菜鸟,写博客主要是为了记录学习过程,跟大家一起进步,如果上述文章中,有任何错误的地方,欢迎指出哦~