패스트캠퍼스 챌린지 6일차

해쉬 테이블 (Has Table)

1. 해쉬 테이블

  • 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조

  • 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산

  • Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐

  • 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당, 키에 따른 데이터 저장 및 탐색 지원

 

2. 용어

 • 해쉬 함수(Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수

  • 해쉬, 해쉬 값 , 또는 해쉬 주소 : 해쉬 함수를 통해 리턴된 고정된 길이의 값

• 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

  • 슬롯(Slot) : 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간

 

[ key : value] => key값을 hash function을 이용해 계산을 한 후 해당 결과값으로 HashTable의 key로 만들어 Hash Table를 만든다, Hash Table은 결과값으로 나온 key값과 value가 저장되어 있다.

 

Hash Table 만들기

public class MyHash{
   publi Slot[] hashTable;
   
   // HashTable은 Slot을 기반으로 테이블 설정
   public MyHash(Integer size){
     this.hashTable = new Slot[size];
   }
   
   public class Slot{
     String value;
     
     Slot(String value){
       this.value = value;
     }
   }
   
   // Hash Fucntion 만들기
   public int hashFunc(String key){
     // EX) "David : 123124 => key.charAt(0) = "D" => (int) D = 68 (아스키코드) => 68 % hashTable.length
     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;
     }
   }
   
}

 

MyHash mainObject = new MyHash(20);

// Hash Function을 이용해서 만들어진 key값을 기반으로 데이터를 찾음
mainObject.saveData("DaveLee","123456789");
mainObject.saveData("fun-coiding","987654321");
mainObject.getData("DaveLee"); // 123456789
mainObject.getData("funcoding"); // 987654321

 

해쉬 테이블의 장•단점

 • 장점 

  - 데이터 저장/읽기 속도가 빠르다 (검색 속도가 빠르다)

  - 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움

 • 단점

   - 저장공간이 좀 더 많이 필요하다

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

 

 • 주요 용도

 - 검색이 많이 필요한 경우

 - 저장, 삭제, 읽기가 많은 경우

 - 캐쉬 구현 시 (중복 확인이 쉽기 때문)

 

충돌 해결 방안

  충돌이란?

   - key값이 중첩되어 key값 조회시 데이터가 덮혀씌어지어 이전 데이터가 사라지는 현상

 

 1. Chaning 기법

  - 개방 해싱 또는 Open Hashing 기법 : 해쉬 테이블 저장공간 외의 공간을 활용하는 기법

  - 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜 저장

public class Slot{
  String key;
  String value;
  Slot next;
  
  Slot(String key, String value){
    this.key = key;
    this.value = value;
    this.next = null; 
  }
}

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];
    // LinkedList를 체크하면서 key값을 이용하여 같은 key값을 찾으면 LinkedList 로 연결하여 Slot 생성
    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);
  }
}

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

              

 2. Linear Probing 기법

  - 폐쇄 해싱 or Close Hashing 기법 : 해쉬 테이블 저장공간 안에서 충돌문제를 해결하는 기법

  - 충돌이 일어나면, Hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법

public class Slot{
  String key;
  String value;
  Slot next;
  
  Slot(String key, String value){
    this.key = key;
    this.value = value;
    this.next = null; 
  }
}

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;
      // 다음 Slot이 있는지 여부 확인
      while(this.hashTable[currAddress].key != null){
        if(this.hashTable[currAddress].key == key){
          this.hashTable[currAddress].value = value;
          return true
        }else{
         // 다음 Slot이 비어있다면
          currAddress++;
          if(currAddress >= this.hashTable.length){
             return false;
          }
        }
      }
      this.hashTable[currAddress] = new Slot(key,value);
      return true;
    }    
  }else{
    this.hashTable[address] = new Slot(key,value);
  }
}

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

 

 

• 시간 복잡도

 - 일반적인 경우(충돌이 없는 경우) : O(1)

 - 최악의 경우 (충돌이 모두 발생) : O(n)

 

검색기능에서는 해쉬 테이블을 사용하여 하는것이 좋다~~~

 

해쉬 테이블 개념은 이해가 가나 코드로 작성할때 하나하나 이해하면서 작성해야 할 필요가 있을듯 하다

 

 

 

6일차 인증

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]