자바 코드 구현 해시 표(google 회사 의 온라인 문제)

1 해시 표(해시)-Google 탑승 문제
1)실제 수 요 를 살 펴 보고 구 글 회사 의 온라인 문 제 를 봅 니 다.
2)새로운 직원 이 보 도 를 할 때 해당 직원 의 정보 가입(id,성별,연령,주소...)을 요구 하 는 회사 가 있 습 니 다.해당 직원 의 id 를 입력 할 때 확인 을 요구 합 니 다.
이 직원 의 모든 정 보 를 찾 습 니 다.
3)요구:데이터 베 이 스 를 사용 하지 않 고 메모 리 를 최대한 절약 합 니 다.속도 가 빠 를 수록 좋 습 니 다=>해시 표(해시 표)
2.해시 표 의 기본 소개
산 목록(Hash table,해시 표 라 고도 함)은 키 코드 값(Key value)에 따라 직접 접근 하 는 데이터 구조 입 니 다.즉,그것 은 통한다.
키 코드 값 을 표 의 한 위치 에 비 추어 기록 에 접근 하여 검색 속 도 를 빠르게 합 니 다.이 매 핑 함 수 는 해시 함수 라 고 하 며 기록 을 저장 하 는 배열 입 니 다.
산 목록 이 라 고 합 니 다.

3.google 회사 의 온라인 문제:
새로운 직원 이 보 도 를 할 때 이 직원 의 정 보 를 가입(id,성별,연령,이름,주소...)하 라 고 요구 하 는 회사 가 있 습 니 다.이 직원 의 id 를 입력 할 때,
이 직원 의 모든 정 보 를 찾 아 달라 고 요구 합 니 다.
요청:
1)데이터 베 이 스 를 사용 하지 않 습 니 다.속도 가 빠 를 수록 좋 습 니 다.
2)추가 시 id 에 따라 낮은 것 에서 높 은 것 으로 삽입
3)체인 시 계 를 사용 하여 해시 시 계 를 실현 한다.이 체인 시 계 는 시계 머리 를 가지 고 있 지 않다.[즉,체인 시계의 첫 번 째 노드 는 직원 정 보 를 저장한다.]
4)사고 분석 및 의도 제시

5)코드 구현

public class HashTableDemo {

 public static void main(String[] args) {
  
  HashTable hashTable = new HashTable(7);
  
  String key = "";
  Scanner scanner = new Scanner(System.in);
  while(true) {
  
   System.out.println("add:    ");
   System.out.println("list:    ");
   System.out.println("find:    ");
   System.out.println("del:    ");
   System.out.println("exit:  ");
     
   key = scanner.next();
   switch (key) {
   case "add":
    System.out.println("   id：");
    int id = scanner.nextInt();
    System.out.println("     :");
    String name = scanner.next();
    
    Emp emp = new Emp(id, name);
    hashTable.add(emp);
    break;
   case "list":
    hashTable.list();
    break;
   case "find":
    System.out.println("   id:");
    int id2 = scanner.nextInt();
    hashTable.findEmpById(id2);
    break;
   case "del":
    System.out.println("   id:");
    int id3 = scanner.nextInt();
    hashTable.del(id3);
    break;
   case "exit":
    System.exit(10);
   default:
    break;
   }
  }
 }
}

// emp
class Emp{
 public int id;
 public String name;
 public Emp next;
 public Emp(int id, String name) {
  super();
  this.id = id;
  this.name = name;
 }
}

// EmpLinkedList
class EmpLinkedList{
 //    ，     Emp，         head，        Emp
 private Emp head;
 
 // id     
 public void add(Emp emp) {
  //          
  if(head == null) {
   head = emp;
   return;
  }
  //        
  Emp curEmp = head;
  while(true) {
   if(curEmp.next == null) {
    break;
   }
   curEmp = curEmp.next;
  }
  curEmp.next = emp;
 }
 
 public void list(int no) {
  if(head == null) {
   System.out.println(" " + (no+1) + "     ！");
   return;
  }
  System.out.println(" " + (no+1) + "      ：");
  Emp curEmp = head;
  while(true) {
   System.out.printf("=> id=%d name=%s\t",curEmp.id,curEmp.name);
   if(curEmp.next == null) {
    break;
   }
   curEmp = curEmp.next;
  }
  System.out.println();
 }
 
 //   id    
 public Emp findEmpByid(int id) {
  if(head == null) {
   System.out.println("    ");
   return null;
  }
  Emp curEmp = head;
  while(true) {
   if(curEmp.id == id) {
    break;
   }
   if(curEmp.next == null) {
    System.out.println("    ，    ！");
    curEmp = null;
    break;
   }
   curEmp = curEmp.next;
  }
  return curEmp;
 }
 
 //   id    
 public boolean del(int id) {
  boolean flag = false;
  if(head == null) {
   System.out.println("      ！");
   return flag;
  }
  if(head.id == id) {
   head = null;
   flag = true;
   return flag;
  }
  Emp curEmp = head;
  while(true) {
   //       
   if(curEmp.next.id == id) {
    curEmp.next = curEmp.next.next;
    curEmp.next = null;
    return (flag == false);
   }
   //     
   if(curEmp.next == null) {
    System.out.println("      ！");
    curEmp = null;
    return flag;
   }
   curEmp = curEmp.next;
  }
 }
}

//    
class HashTable{
 
 private EmpLinkedList[] empLinkedListArr;
 private int size;
 public HashTable(int size) {
  super();
  this.size = size;
  empLinkedListArr = new EmpLinkedList[size];
  
  for(int i = 0; i < size; i++){
   empLinkedListArr[i] = new EmpLinkedList();
  }
 }
 
 //     
 public void add(Emp emp) {
  //      id              
  int empLinkedListNo = hashFun(emp.id);
  //  emp         
  empLinkedListArr[empLinkedListNo].add(emp);
 }
 
 public void list() {
  for (int i = 0; i < empLinkedListArr.length; i++) {
   empLinkedListArr[i].list(i);
  }
 }
 
 public void findEmpById(int id) {
  int empLinkedListNo = hashFun(id);
  Emp emp = empLinkedListArr[empLinkedListNo].findEmpByid(id);
  if(emp != null) {
   System.out.println("  " + (empLinkedListNo+1) + "      id = " + id + "  ");
  } else {
   System.out.println("         ");
  }
 }
 
 public void del(int id) {
  int empLinkedListNo = hashFun(id);
  boolean flag = empLinkedListArr[empLinkedListNo].del(id);
  if(flag == true) {
   System.out.println("  " + (empLinkedListNo+1) + "       id = " + id + "  ");
  } else {
   System.out.println("         ");
  }
  
 }
 
 public int hashFun(int id) {
  return id %size;
 }
}

메모:링크 의 첫 번 째 노드(머리 노드)를 삭제 하지 마 세 요.그렇지 않 으 면 전체 링크 가 없어 집 니 다.(개량 도 가능 하 다)
사고:만약 에 id 가 낮은 것 에서 높 은 것 으로 삽입 되 지 않 지만 각 링크 가 낮은 것 에서 높 은 것 으로 요구 하면 어떻게 해결 합 니까?
자바 해시 표(google 회사 의 온라인 문제)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 해시 표 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!