해시 테이블 (Hash Table)

Hash Table 이란?

- key 와 value를 대응시켜 저장하는 데이터 구조

키를 통해서 해당 데이터(value)에 빠르게 접근할 수 있다.

 

- 해싱

키를 특정 계산식(해시 함수)에 넣어 나온 결과를 사용하여 값에 접근하는 과정

 

구조

- 키

해시 테이블에 접근하기 위한 입력 값

 

- 해시 함수 

키를 해시 값으로 매핑하는 연산

 

- 해시 값

해시 테이블의 인덱스

 

- 해시 테이블

key - value를 연관시켜 저장하는 데이터 구조

 

해시충돌

서로 다른 키인데도 해시함수를 통한 해시 값이 동일한 경우, 이를 해시충돌

이러한 경우 해결방법으로 두가지가 있다.

 

- 개방 주소법 (Open Address)

충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장하는 방법

hash와 value가 1:1 관계를 유지

비어 있는 공간을 탐색하는 방법에 따라 분류

• 선형 탐사법 (Linear Probing)
  
  • 빈 공간을 순차적으로 탐사 -> 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
  • 일차 군집화 문제 발생 -> 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우가 발생한다.
• 제곱 탐사법 (Quadratic Probing)
  • 빈 공간을 n제곱 만큼의 간격을 두고 탐사 -> 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사
  • 일차 군집화 문제 일부 보환
  • 이차 군집화 문제 발생 가능성
• 이중 해싱 (Double Hashing)
  • 해싱 함수를 이중으로 사용 : 1. 최초 해시를 구할 때  -> 2. 충돌 발생 시, 탐사 이동 간격을 구할 때
  • 위의 두 방법보다 데이터를 골고루 분포시킬 수 있다.

 

- 분리 연결법 (Separate Chaining)

해시 테이블을 연결 리스트로 구성하여 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결리스트를 이용하여 해당 테이블에 데이터를 연결한다.

하나의 해시 값에 여러개의 데이터가 붙어있기 때문에 1:1 상황이 아니라서 원하는 값을 얻을 때 개방 주소법보다 오래 걸린다.

 

 

 

궁금증 : HashMap이랑 HashTable이랑 비슷해보이는데 뭐가 다른걸까?

 

• 공통점
  • Map 인터페이스를 상속받아 구현 
  • Key 와 Value로 구분되어 값을 관리
  • 값을 탐색함에 있어서 높은 효율 
• 차이점
  • 동기화
    • HashMap은 동기화 지원 X / 동기화 처리가 없기 때문에 더 빠름
    • HashTable은 동기화를 지원 O / 멀티 스레드 환경에서 동기화 처리 가능하지만 동기화가 보장되는 HashMap인  ConcurrentHashMap을 사용하는게 더 좋다고 한다. 
  • Null 여부
    • HashMap은 null을 허용 O
    • HashTable은 null 허용 X
  • 기타
    • 보조 해시 함수 여부 ( M : O / T : X) -> 해시충돌이 덜 발생한다
    • 그 외 Enumeration 여부 차이 등이 있다.