해시 테이블(2)

- 해시 테이블의 장,단점

(1) 장점

- 데이터 저장/읽기 속도가 빠르다는 것임

- 해시는 키에 대한 데이터가 있는지 확인이 쉬움 

(2) 단점

- 일반적으로 저장 공간이 많이 필요함

- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요함

 

 

- 해시 테이블의 주요 용도 

(1) 검색이 많이 필요한 경우

(2) 저장, 삭제, 읽기가 빈번한 경우 

(3) 캐시 구현 시 

 

 

- 충돌(Collision) 해결 알고리즘

(1) Chaining 기법

- 충돌이 발생하면 해당 위치에 linked list 만듦

- 개방 해싱(Open hashing)이라고도 함

 

(2) Linear Probing 기법

- 폐쇄 해싱(Closed hashing)이라고도 함

 

Chaining 기법 코드

public class MyHash{


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

   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){
             Slot findSlot = this.hashTable[address];
             Slot prevSlot = this.hashTable[address];
             while(findSlot != null){
                 if(findSlot.key == key){
                     findSlot.value = value; 
                     return true; 
                 }else{
                   prevSlot = findSlot;
                   findSlot = findSlot.next;  
                }
             }
             prevSlot.next = new Slot(key, value);

          }else{
           this.hashTable[address] = new Slot(key, value);
         }
        return true;   
     }

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

- 참고

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