前言：查找是開發(fā)中用的非常多的一項，比如mysql中的查找，下面主要簡單介紹一下查找。
1：線性表查找
線性表查找主要分為順序查找和鏈式查找，順序表查找都是從一端到另一端進行遍歷。比如下面代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public int indexOf(T x){ if (x!=null){ for (int i=0;i<this.len;i++){ if (this.element[i].equals(x)){ return i; } } } return -1; } public T search(T key) { return indexOf(key)==-1?null:(T) this.element[indexOf(key)]; } |
第二種是鏈式查找也非常簡單
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public T search(T key) { if (key==null){ return null; } Node<T> p=this.head.next; while (p!=null){ if (p.data.equals(key)){ return p.data; } p=p.next; } return null; } |
2：基于有序順序表的二分查找
這個用的比較多，因為查詢效率比較高，但是有限制條件，1是順序存儲，2必須有序，所以每次只需要和中間值進行比對，如果大于中間值，說明在key值在后面，如果小于中間值，說明key在前面。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
public static<T> int binarySearch(Comparable<T>[] values,int begin,int end,T key) { if (key != null) { while (begin <= end) { int mid = (begin + end) / 2; if (values[mid].compareTo(key) == 0) { return mid; } if (values[mid].compareTo(key) < 0) { begin = mid + 1; } if (values[mid].compareTo(key) > 0) { end = mid - 1; } } } return -1; } public static int binarySearch(int[] arrays, int key) { if (arrays == null || arrays.length == 0) { return -1; } int start=0,end=arrays.length-1; while (start <=end) { int mid = (start + end) / 2; if (arrays[mid] == key) { return mid; } if (arrays[mid] < key) { start = mid + 1; } if (arrays[mid] > key) { end = mid - 1; } } return -1; } |
3：分塊索引查找
我們都知道查字典，首先要查詢是字的拼音，然后定位到字頁數(shù)的一個位置，比如查找張這個字，我們先查詢z，然后看哪些頁是z，然后在這一塊進行查找。ok我們做個簡單的例子
現(xiàn)在我們已知一個數(shù)組里面存放的是Java的關(guān)鍵字，那么我們給出一個關(guān)鍵字來判斷是否在這個數(shù)組中。首先我們看下關(guān)鍵字的數(shù)組
|
1
2
3
4
5
|
private static String[] keyWords={"abstract","assert","boolean","break","byte","case", "catch","char","continue","default","do","double","else","extend","false","final","finally","float","for","if","implements","import","instaceof","in","interface","long","native","new","null","package","private","protectd","public","return","short","static","super","switch","synchronized","this","throw","transient","true","try","void","volatile","while"}; |
然后我們思考一下建立索引，因為英文單詞是26個字母組成，那么我們效仿字典，把26個字母存起來，然后記錄每個字母的位置。
|
1
2
3
4
5
6
7
|
private static class IndexItem implements Comparable<IndexItem>{ String frist; int start; public IndexItem(String frist,int start){ this.frist=frist; this.start=start; } |
其中frist是字母，二start是字母的索引，比如abstract是a0，那么assert就是a1了以此類推
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public int compareTo(IndexItem o) { return this.frist.compareTo(o.frist); }private static IndexItem[] index;索引表 static { index = new IndexItem[26]; int i = 0, j = 0, size = 0; for (i = 0; j < keyWords.length && i < index.length; i++) { char ch = keyWords[j].charAt(0); IndexItem item = new IndexItem(ch + "", j); if (item != null) { index[i] = item; size++; } j++; while (j < keyWords.length && keyWords[j].charAt(0) == ch) { j++; } } int oldCount = index.length;利用trimTosize方法對數(shù)組進行壓縮 if (size < oldCount) { IndexItem[] items = index; index = new IndexItem[size]; for (int m = 0; m < size; m++) { index[m] = items[m]; } } } |
我們創(chuàng)建一個靜態(tài)塊,在類被加載的時候運行。最后我們利用2次2分查找第一找到索引，然后通過索引匹配到值
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public static boolean isKeyWord(String str){ IndexItem indexItem=new IndexItem(str.substring(0,1),-1); int pos=BSArry.binarySearch(index,indexItem); int begin=index[pos].start; int end; if (pos==index.length-1){ end=keyWords.length-1; }else { end=index[pos+1].start-1; } return BSArry.binarySearch(keyWords,begin,end,str)>=0; } |
4：散列表的查找
散列的查找非常高效，但是我們必須要完成2項工作，一個是散列函數(shù)，另一個是解決沖突。下面看一下如何利用單鏈表簡單的實現(xiàn)hash。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public class HashSet<T> { private SingleLinkedList<T>[] table; public HashSet(int size) { this.table = new SingleLinkedList[Math.abs(size)]; for (int i = 0; i < table.length; i++) { table[i] = new SingleLinkedList<T>();//制造單鏈表 } } public HashSet() { this(97); } private int hash(T x) {//利用hashCode解決 int key = Math.abs(x.hashCode()); return key % table.length; } public void insert(T x) { this.table[hash(x)].insert(0, x); } public void remove(T x) { this.table[hash(x)].remove(x); } public T search(T key) { return table[hash(key)].search(key); }} |
以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務器之家！
原文鏈接：http://www.cnblogs.com/LipeiNet/p/6511634.html
