해시 테이블(1)

 

- 키에 데이터를 매핑할 수 있는 데이터 구조임  

-> 각각의 데이터마다 키와 밸류에 해당하는 값은 다를 수 있음

 

- key를 hash function에 넣으면 주소를 리턴해줌 

-> hash function은 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수임

 

- hash 함수는 사용자가 정의할 수 있음 

 

- 해시 테이블에 저장하면 key를 hash function에 넣으면 O(1)에 확인할 수 있음

  (cf. 배열, 링크드 리스트)

 

- 해시 테이블은 보통 배열을 많이 사용함

-> 각각의 실제 데이터가 저장되는 공간을 slot이라고 함

 

- 해시 함수를 통해 리턴된 값을 해쉬 주소, 해쉬 값, 해쉬 라고 함

 

- 해시 클래스는 다음과 같이 만들 수 있음 

public class MyHash{

   public Slot[] hashTable;

   public MyHash(Integer size){
       this.hashTable = new Slot[size];
   }
 
   public class Slot{
      String value;
      Slot(String value){
          this.value = value; 
      }  
   }


   public int hashFunc(String key){
        return (int)(key.charAt(0)) % this.hashTable.length;
   }

   public boolean saveData(String key, String value){
          Integer address = this.hashFunc(key);
      
          if(this.hashTable[address] != null){
              this.hashTable[address].value = value;
          }else{
           this.hashTable[address] = new Slot(value);
         }
        return true;   
     }

   public String getData(String key){
          Integer address = this.hashFunc(key);
          
          if(this.hashTable[address] != null){
             return this.hashTable[address].value;
          }else{
             return null;
          }
   }          

}

   

- 참고

한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online편