💚 자료구조 - HashMap과 해시 충돌

HashMap

key, value 형태로 저장하는 자료구조

HashMap은 하나의 key가 하나의 value에 매핑되도록 구성된 자료구조.

• 예시) 주민번호

예시로, 학생 정보를 저장한다고 할 때:

• key: 학생 고유 번호
• value: 학생의 세부 정보 (예: 이름)

1 : 이나영
2 : 이두유
3 : 최글대

여기서 number가 key라면, value는 그 학생에 대한 정보를 의미함.

HashMap의 가장 큰 특징은 삽입, 삭제, 갱신, 탐색이 상수 시간에 처리된다는 점이다.

특징

상수 시간에 처리된다는 것은 데이터의 크기에 상관없이 매우 빠르게 수행된다는 의미이며, 시간 복잡도는 O(1) 이다.

예를 들어, 한국의 예능인 인기 투표와 같은 경우를 생각해보겠다. 투표 참여자가 전 국민 5,500만 명일 때, key를 이름, value를 득표수로 설정해 HashMap을 사용하면, 매번 이름을 검색해 새로운 득표를 추가하는 작업이 상수 시간에 가능해진다. 이를 List 구조로 처리해 처음부터 카운트하려면 메모리 낭비가 심해지지만, HashMap을 사용하면 새로운 이름이 나올 때마다 빠르게 카운트할 수 있어 속도가 빠르고 메모리 낭비도 줄일 수 있다.

장점

HashMap의 장점은 삽입/삭제/갱신/탐색을 매우 빠르게 처리할 수 있다는 것이다. 이로 인해 메모리 낭비도 적게 발생한다.

HashMap (Hash table)

• 배열을 사용하여 구현

• 해시 함수(hash function) : key를 배열 크기 내의 인덱스로 바꿔주는 함수

key가 문자열, 이나영이 들어간다고 할 때 내부적으로 배열에 저장될 수 있는 것. 해시 함수가 이 key를 index에 사용될 수 있는 integer 정수로 바꾸어 주게 되고 이 정수를 통해 적절한 위치에 해당하는 값들을 넣어주게 되는 것.

내부 구현

이미지 출처

배열을 사용하여 구현

배열에 저장하기 위해 key의 hash를 구해야함

hash function으로 key의 hash를 구함

구해진 hash를 배열 사이즈로 modular(%) 한 값을 index로 사용

• hash map 안에서 사용되는 hash function이 반환하는 데이터의 타입은 정수여야 된다.

array[hf(key) % M] = value

hf : hash function,
M : hash_map size

여기서 hf는 해시 함수(hash function)로, key를 특정 배열 크기 내의 인덱스로 변환해주는 역할을 한다. 예를 들어, key가 문자열 “이나영”이라면, 해시 함수가 이 key를 배열에서 사용할 수 있는 정수형 인덱스로 바꿔 적절한 위치에 해당 값을 넣는다.

해시 충돌( Hash Collision)

HashMap에서 서로 다른 key들이 같은 hash를 가질 때 발생하는 문제가 해시 충돌이다.

1. key1!=key2 이지만 hf(key1)==hf(key2)

2. hf(key1) != hf(key2) 이지만 hf(key1) % M == hf(key2) % M

1번의 방법 뿐만 아니라 2번의 방법도 해시 충돌을 의미한다.

그렇다면 해시 충돌이 왜 발생할까?

• 완벽한 해시 함수(perfect hash function) 구현의 어려움

  • perfect hash function: key1 ≠ key2일 때 hf(key1) ≠ hf(key2)를 만족하는 해시 함수이다. 하지만 이를 구현하기 어려운 이유는 해시 함수의 특성상 입력값의 크기가 거의 무한대라고 볼 수 있기 때문이다. 입력값은 보통 문자열로 이루어져 있어 가능한 값의 범위가 매우 넓지만, 해시 함수의 출력은 4바이트 크기의 정수형 값으로 제한된다. 즉, 무한대에 가까운 입력값을 4바이트의 제한된 공간으로 매핑해야 하기 때문에, 마치 7인승 차에 20~30명을 태우려는 것과 같아 즉, 제한된 공간 내에서 충돌이 발생할 수밖에 없다.

• key의 사이즈에 비해 HashMap 사이즈가 작기 때문

  • 우리나라 인구가 5,500만 명이지만, 내 서비스 가입자를 모두 5,500만 명으로 예상하여 HashMap을 설정한다면 메모리 낭비가 심해진다. 그래서 HashMap 크기를 약 2천 개로 잡는다고 가정하면, 원래 key의 범위인 5,500만에 비해 맵핑할 크기를 크게 줄일 수 있다. 그러나 내 서비스를 실제로 누가 사용할지는 알 수 없고, 가능한 5,500만 개의 번호를 해시 함수를 통해 해시 값으로 변환한 뒤, 2천 개 크기로 modular 연산을 수행해야 한다. 이 경우, 제한된 크기인 2천 개 안에 수많은 key를 매핑하게 되면서 충돌이 발생할 수밖에 없고, 결과적으로 modular 연산 때문에 충돌 가능성이 항상 존재하게 된다.

해시 충돌 해결방법

이미지 출처

개별 체이닝(Separate chaining) : 추가적인 공간을 활용하여 해결하는 방식

• Linked List 사용

  • 개별 체이닝은 충돌 발생 시 연결 리스트로 연결하는 방식이다. 출동이 발생한 ‘윤아’와 ‘서현’은 다음 아이템이 ‘서현’인 형태로 서로 연결 리스트로 연결된다.

  • 1. 키의 해시 값을 계산한다.
  • 1. 해시 값을 이용해 배열의 인덱스를 구한다.
  • 1. 같은 인덱스가 있다면 연결 리스트로 연결한다.
  • 단점 : 구현을 잘했다면 탐색은 O(1)이지만 최악의 경우, 모든 해시 충돌이 발생했다고 하면 O(n)이 된다.

이미지 출처

해당 이미지는 오픈 어드레싱의 선형 탐사(Linear Probing) 방식임.

오픈 어드레싱(Open addressing) : 충돌 발생 시 인접한 비어있는 공간(bucket)에 저장

• 선형 탐사(Linear probing) : 고정폭으로 이동하여 빈 공간을 찾음

  • 선형 탐사 방식은 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행함. 특정 위치에 값이 들어가 있으면 바로 그 다음 위치를 확인하는 방식. 이렇게 탐사를 진행하다 비어있는 공간을 발견하면 삽입하게 됨. 결과적으로 가장 가까운 다음 빈 위치를 탐사해 새 키를 삽입하는 것이다.

  • 단점 : 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있음. 해시 테이블 이곳 저곳에 연속된 데이터 그룹이 생기는 현상을 클러스터링(Clustering)이라고 하는데 클러스터들이 점점 커지게 되면 인근 클러스터들과 서로 합쳐지는 일이 발생한다. 이렇게 되면 해시 테이블의 특정 위치에는 데이터가 몰리고, 다른 위치에는 상대적으로 데이터가 거의 없는 상태가 될 수 있다. 이러한 클러스터링 현상은 탐사 시간을 오래 걸리게 하고 전체적으로 해싱 효율을 떨어뜨리는 원인이 된다.

  • 주의할 점 : 중간 연결고리 역할을 하는 key의 삭제 시, 이미 있는 값도 없다고 판단할 수 있음.

    • 해결책 : 삭제 시 DELETE 같은 상징적인 형태로 표시

      • DELETE 표시를 보고 다음 위치도 확인해봐야함을 알 수 있음. 단점 : DELETE를 만나면 무조건 다음 위치를 확인해야 함.

      • 삭제 위치 다음의 open addressing된 key들은 한 단계씩 앞으로 옮겨준다. 단점 : 이동시키는 추가적인 비용 발생.

• 제곱 탐사(Quadratic probing) : 제곱수만큼 이동하여 빈 공간을 찾음

• 이중 해싱(Double Hashing) : 또 다른 hash function을 사용하여 빈 공간을 찾음

Java에서는 해시 충돌을 어떻게 해결했을까?

• jdk7까지는 linked list를 사용한 separate chaining을 활용

• jdk8에서 linked list와 red black tree를 혼용한 separate chaining을 활용

정리

HashMap은 배열이 상수 시간 내에 데이터를 처리할 수 있는 점을 활용한 자료구조이다. 배열은 인덱스를 통해 삽입, 삭제, 갱신, 조회를 빠르게 할 수 있지만, 인덱스가 양의 정수여야 한다는 제한이 있다. 그래서 HashMap에서는 다양한 key 값을 배열의 인덱스로 변환하기 위해 해시 함수를 사용한다. 이 해시 함수가 주어진 key를 적절한 인덱스로 바꿔주어, 그 인덱스에 데이터를 저장할 수 있게 한다.