[자료구조] Hash(해시), Hash Table, HashMap

ㅇ Hash

개념

해시는 임의 길이의 입력 데이터를 고정 길이의 해시 값 또는 해시 코드로 매핑하는 과정 혹은 그 결과물을 의미한다

해시 함수를 사용하여 매핑하고, 이 함수는 입력 값(Key)을 특정 규칙에 따라 연산해 일정한 길이의 정수로 변환한다

 

특징

• 고속성
  키를 즉시 특정 값으로 매핑할 수 있으므로 연산 속도가 매우 빠르다
• 결정론적 성질
  같은 입력은 항상 같은 해시 값을 반환한다
• 해시충돌
  서로 다른 입력에 대해 서로 다른 해시 값을 주는 것이 이상적이나, 해시충돌이 발생할 수 있다
• 균등 분포성
  우수한 해시 함수는 가능한 한 해시 값을 균등하게 분포시켜 충돌을 최소화한다

 

ㅇ Hash Table

개념

해시 테이블은 (키, 값) 쌍을 저장하는 자료구조로 키를 해시 함수에 통가시켜 해시 값을 얻고 이를 배열의 인덱스로 사용하여 데이터를 관리한다

 

핵심 아이디어는 키를 직접 비교하지 않고도 해시 함수를 통해 빠르게 해당 키가 위치할 수 있는 인덱스를 찾아가는 것

 

구조 및 동작 원리

1. 버킷 : 해시 값을 인덱스로 하는 배열의 각 원소를 버킷이라고 한다 각 버킷에는 하나 이상의 (키, 값)쌍이 저장될 수 있다

 

2. 해시 함수 : 입력 키를 버킷 배열의 인덱스 범위 내에 매핑하는 함수다 

 

3. 충돌(Collision)처리 방법 : 서로 다른 키가 동일한 해시 값을 만들어 동일 버킷에 위치하려 할 때의 상황이다.

• 체이닝
  하나의 버킷에 여러 개의 원소를 연결 리스트나 트리형태로 저장한다. 충돌 발생 시 해당 버킷에 쌍을 추가한다
• 오픈 어드레싱
  빈 버킷을 찾을 때까지 해시 테이블 내 다른 위치를 선형 탐사, 이중 해싱 등의 기법으로 탐색하여 충돌을 해결한다

시간 복잡도

평균적으로 검색, 삽입, 삭제가 O(1)의 시간 복잡도로 매우 빠르게 동작한다

 

장점

• 매우 빠른 접근 시간
• 키를 통해 직접적인 접근 가능

단점

• 효율적인 해시 함수를 설계하기 어려울 수 있음
• 충돌 해결을 위한 추가 메커니즘 필요
• 메모리 사용에 신경 써야 함

 

ㅇHashMap

개념

해시 맵은 해시 테이블을 기반으로 구현된 추상 자료구조 혹은 클래스의 한 형태이다

 

가장 흔히 알려진 예시로 자바의 해시맵이 있다

내부적으로 해시 테이블 구조를 사용하며, (키, 값)쌍을 저장하고 키를 통해 값을 조회할 수 있도록한다

 

특징(자바 기준)

• 키의 유일성
  키는 고유해야 하며, 동일한 키 삽입 시 기존 값이 덮어씌워진다
• Null 허용
  키와 값 모두 Null을 허용한다
• 순서 비보장
  입력 순서나 정렬 순서를 보장하지 않는다
• 내부 구조
  키에 대해 hashCode() 메서드를 호출하여 해시 값을 구한 뒤, 해당 값을 기반으로 적절한 버킷 인덱스를 구한다
  충돌 발생 시 JAVA8 이후에는 체이닝을 통해 연결리스트를 사용하고 충돌이 빈번한 경우 트리로 변환되어 최악의 경우를 줄인다

장점

• 해시 테이블 기반이므로 빠른 검색, 삭제, 삽입
• 구현이 간편하고 활용 범위가 넓다

단점

• 멀티스레드 환경에서 동기화 문제가 발생할 수 있음
• 메모리 및 해시 함수 품질에 따라 성능 차이가 날 수 있음