해시 테이블(Hash Table)이란?

해시 테이블(Hash Table)

• 해시 테이블이란 key를 이용하여 value를 저장하는 자료구조이다.
• 저장, 검색, 삭제의 평균적인 시간 복잡도가 O(1)에 수렴하여 그 이유는 다음과 같다.
  
• key를 특정 해시 함수(Hash Function)를 통하여 해싱한 결과 값을 해시 테이블의 인덱스로 사용한다.
• 해시테이블의 key로 만든 인덱스에 value를 저장한다.
• key를 알면 value가 저장된 인덱스를 알 수 있으므로 저장, 검색, 삭제의 시간 복잡도가 O(1)에 수렴한다.
  
  
• 장점
  • 저장, 검색, 삭제가 매우 빠르다.
  • 메모리 크기가 가변적이다.
  • 대량의 정보를 효율적으로 다룰 수 있다.
    
    
• 단점
  • 해시 함수를 사용하는데 추가적인 연산이 필요하다.
  • 다른 자료구조보다 메모리가 더 많이 필요하다.
  • 해시 충돌이나 클러스터링이 발생하면 성능이 낮아진다.
    
    
• 문제점
  • 해시 충돌(Hash Collision): 인덱스가 이미 존재할 수 있다.
  • 오버플로우(Overflow): 해시 충돌이 버킷에 할당된 슬롯 수보다 많이 발생하면 더 이상 버킷에 값을 넣을 수 없다.
  • 클러스터링(Clustering): 데이터가 한 쪽에 몰릴 수 있다.

해시 테이블의 문제점 해결 방법

• 해시 충돌
  • 체이닝(Chaining)
    
    • 버킷의 인덱스가 가르키는 연결 리스트에 노드를 추가하여 key와 value를 같이 저장한다.
    • 별도의 저장공간을 필요로 하지만 인덱스가 바뀌지 않는다.
    • key를 index로 변환 후 연결리스트에 해당 key가 존재하면 value를 가져온다.
    • 매핑되는 value가 저장되어 있는 공간을 슬롯(Slot)이라고 한다.
    • 해시 충돌이 계속 발생하여 할당된 슬롯 수를 넘게 되면 오버플로우가 발생한다.
      
      
  • 개방 주소법(Open Addressing)
    - 충돌이 발생했을 경우 추가적인 메모리를 사용하지 않고 빈 버킷을 찾아서 저장한다.
    - 다른 버킷에 저장하기 때문에 인덱스가 바뀔 수 있다.
    
    
    - 선형 검색법(Linear Probing)
    
    - 가장 간단한 방법이며 캐시 효율이 높다.
    - 충돌이 발생한 위치에서 선형적으로 검색하여 가장 처음 발견한 빈 영역에저장한다.
    - 충돌이 자주 발생하는 위치 주변에 데이터가 밀집될 수 있어 클러스터링에 취약하다.
    
    
    - 2차 검색법(Quadratic Probing)
    
    - 클러스터링을 해결하기 위한 방법이다.
    - 충돌이 일어나면 1, 4, 9, 16... 과 같이 떨어진 영역을 차례대로 검색하여 가장 처음 발견한 빈 영역에 저장한다.
    - 하지만 제2밀집이 발생할 수 있어 클러스터링을 완벽히 해결하진 못한다.
    
    
    - 이중 해싱(Double Hashing)
    
    - 캐시 효율을 포기하고 클러스터링 해결에 집중한 방법이다.
    - 충돌이 발생하면 2차 해시 함수를 이용하여 이동 거리를 계산하고 저장한다.
    - 가장 많은 연산량이 일어난다.
    
    
• Resizing
  • 개방 주소법에서 사용되는 배열이 가득차거나, 체이닝에서 사용되는 연결 리스트가 길어지게 되면 버킷의 개수를 늘려준다.
  • 늘어난 버킷의 크기에 맞게 재해싱하여 버킷을 채운다.