Java 데이터 구조 찾기

선언: 검색은 개발에서 매우 많은 것을 사용하는 것이다. 예를 들어 mysql에서 검색하는 것이다. 다음은 주로 검색을 간단하게 소개한다.
1: 선형 테이블 찾기
선형 테이블 찾기는 주로 순서 찾기와 체인 찾기로 나뉘는데 순서 테이블 찾기는 모두 한쪽에서 다른 한쪽으로 옮겨간다.예컨대 아래 코드

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)];
 }

두 번째는 체인 검색도 간단해요.

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: 질서정연한 순서표에 근거한 2점 찾기
이것은 조회 효율이 비교적 높기 때문에 제한 조건이 있다. 1은 순서대로 저장하고 2는 질서정연해야 하기 때문에 매번 중간 값과 비교하기만 하면 된다. 만약에 중간 값보다 크면 키 값이 뒤에 있고 중간 값보다 작으면 키가 앞에 있다는 것을 설명한다.

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: 블록 인덱스 찾기
우리는 모두 사전을 찾는 것을 알고 있다. 먼저 글자의 병음을 조회한 다음에 글자 페이지 수의 한 위치를 지정해야 한다. 예를 들어 이 글자를 찾으려면 먼저 z를 조회한 다음에 어떤 페이지가 z인지 보고 이 부분에서 찾아야 한다.오케이, 우리 간단한 예를 들자.
현재 우리는 하나의 그룹에 자바의 키워드가 저장되어 있다는 것을 알고 있다. 그러면 우리는 이 그룹에 있는지 아닌지를 판단하기 위해 키워드를 제시한다.일단 키워드의 그룹을 볼게요.

 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개의 자모를 저장한 다음에 각 자모의 위치를 기록한다.

private static class IndexItem implements Comparable<IndexItem>{
  String frist;
  int start;
  public IndexItem(String frist,int start){
   this.frist=frist;
   this.start=start;
  }

그 중에서frist는 자모이고, 2start는 자모의 인덱스이다. 예를 들어 abstract는 a0이다. 그러면assert는 a1이다.

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 
   if (size < oldCount) {
    IndexItem[] items = index;
    index = new IndexItem[size];
    for (int m = 0; m < size; m++) {
     index[m] = items[m];
    }
   }
  }

클래스가 불러올 때 실행되는 정적 블록을 만듭니다.마지막으로 우리는 두 번 2점을 이용하여 첫 번째 색인을 찾은 다음에 색인을 통해 값에 일치한다

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: 흩어진 목록 찾기
산열의 검색은 매우 효율적이지만, 우리는 두 가지 작업을 완성해야 한다. 하나는 산열 함수이고, 다른 하나는 충돌을 해결하는 것이다.다음은 어떻게 단사슬표를 이용하여hash를 간단하게 실현하는지 봅시다.

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);
 }
}

이상은 본문의 전체 내용입니다. 본고의 내용이 여러분의 학습이나 업무에 일정한 도움을 줄 수 있는 동시에 저희를 많이 지지해 주시기 바랍니다!