해시 테이블(3)

- Linear Probing 기법의 코드는 다음과 같이 작성할 수 있음 

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

   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){
               if(this.hashTable[address].key == key){
                     this.hashTable[address].value = value;
                     return true;
               }else{
                     Integer currAddress = address+ 1;
                     while(this.hashTable[currAddress] != null){
                        if(this.hashTable[currAddress].key == key){
                            this.hashTable[currAddress].value = value;
                            return true;
                        }else{
                            currAddress++;
                            if(currAddress >= this.hashTable.length){
                                  return false; 
                             }
                        }
                }
                this.hashTable[currAddress] = 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){
             if(this.hashTable[address].key == key){
                    return this.hashTable[address].value;
             }else{
                    Integer currAddress = address + 1;
                    while(this.hashTable[currAddress] != null){
                         if(this.hashTable[currAddress].key == key){
                                return this.hashTable[currAddress].value;
                         }else{
                               currAddress++;
                               if(currAddress >= this.hashTable.length){
                                     return null;
                               }
                          }
                    } 
                    return null; 
          }else{
             return null;
           }
     }          
}

 

- 충돌이 일어나면, 성능이 떨어질 수 밖에 없음

-> 가장 좋은 방법은 충돌이 일어나지 않도록 만드는 것임

-> 해시 테이블의 저장 공간을 확대하고, 해시 함수를 재정의함  

 

- 자바를 쓰면서 해시맵도 많이 씀

-> 해시 테이블 구조를 활용하여 구현된 해시 맵이라는 클래스가 있음  

 

import java.util.HashMap;

HashMap<Integer, String> map1 = new HashMap();

map1.put(1, “사과”);
map1.put(2, “바나나”);
map1.put(3. “포도”);

HashMap<String, String> map2 = new HashMap();

map2.put(“DaveLee”, “01033334444”);
map2.put(“Dave”, “01032221111”);
map2.put(“David”, “01044445555”);

 

- 보통의 해시 테이블은 일반적인 경우(Collision이 없는 경우)는 O(1)

- 최악의 경우 O(n)

 

- 배열에 데이터를 저장하고, 검색할 때 O(n)

- 해시 테이블은 O(1) 

-> 검색에서 해시 테이블을 많이 사용함 

 

- 참고

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