[CS] 해시테이블

해시테이블

 

• (Key, Value)로 데이터를 저장하는 자료구조
• 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 숫자값인 hashcode를 생성하고 이를 인덱스로 사용한다.
• hashcode를 index로 한 value 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
• 검색 시 해시테이블의 평균 시간복잡도( Time Complexity ): O(1)

 

해시 테이블이 검색속도가 빠른 이유

• 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문

 

해시테이블(HashTable) 시간복잡도

• 데이터 조회 최악: O(N) - 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로
• 평균: O(1) - 각각의 Key값은 해시함수에 의해 고유한 index를 가지므로 데이터에 바로 접근

 

해시 충돌

 

hash function을 통해서 key 값을 작은 범위의 값들로 바꿀 때 동일한 값이 도출될 수가 있다 

동일한 key 값에 복수 개의 데이터가 존재할 수 있게 되는 것인데 이를 해시 충돌이라고 한다.

hashing 된 인덱스에 이미 다른 값이 들어 있다면 새 데이터를 저장할 다른 위치를 찾은 뒤에야 저장할 수 있다

 

 

• 해시 충돌 해결 방법
  1. 분리 연결법(Separate Chaining)
     • 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것
     • 장점: 구현이 간단하고, 손쉽게 삭제할 수 있다
     • 단점: 동일한 버킷에 chaining되는 데이터가 많아지면 그에 따라 캐시의 효율성이 감소한다
  2. 개방 주소법(Open Addressing)
     • 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다
     • Linear Probing
       • 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장
     •  Quadratic Probing
       • 해시의 저장순서 폭을 제곱으로 저장하는 방식이다.
       • ex) 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식
     • Double Hashing Probing
       • 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식

 

HashMap과 HashTable의 차이

• 동기화 지원 여부
  • 해시테이블의 put에는 synchronized 키워드가 붙어있다
  • → 이것은 병렬 프로그래밍을 할 때 동기화를 지원해준다는 것을 의미
• 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)을 사용해야 하며, 
• 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵(HashMap)을 사용하면 된다.

 

• HashTable
  • 데이터 변경 메소드가 모두 동기화 메소드로 선언되어 있어 thread-safe하다
  • → 멀티 쓰레드 환경에서 사용하기 적합
  • 속도가 느리다.
  • 해시 충돌 위험
  • key에 null값을 허용X
• HashMap
  • 동기화를 지원하지 않아 데이터 무결성을 보장하지 못함
  • → 단일 쓰레드 환경에서 사용하기 적합
  • 속도가 빠르다.
  • 보조해시 함수를 사용하기 때문에 해시 충돌 발생 가능성이 낮다
  • key에 null값을 허용