[알고리즘, 자료구조] 해시테이블(Hash table)

해시테이블

해시테이블은 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑한 테이블이다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간복잡도를 가지며 unorderd_map으로 구현한다.

이를 통해 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있다.

 

해시 함수를 이용하여 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키값과 데이터를 저장하는 자료구조이다.

 

해시테이블의 장점

• 검색속도가 매우 빠르다.
  • 해시 테이블의 키값에는 숫자, 문자열, 파일데이터 등등 제한이 거의 없다. 키값을 해시함수를 통해 해시코드를 정수로 생성해내 인덱스로 활용하기 때문에 키값이 얼마나 큰지에 관계없이 정수의 인덱스로 환산된다. 해시코드를 인덱스로 사용하기 때문에 바로 데이터의 위치에 다이렉트로 접근할 수 있다. 즉 배열의 경우 배열 안의 특정 값을 찾기 위해선 배열의 0번인덱스 부터 n번째 인덱스까지 선형검색을 해야하는데 (O(n)) 해시 테이블을 이용하면 키값이 해시코드로 환산되어 이 해시코드 자체를 배열의 인덱스로 활용하기 때문에 검색 자체가 없고 바로 데이터의 위치에 접근할 수 있다. (O(n1))

 

해시테이블의 문제점 : 해시충돌(Collision)

• 해시함수를 통해 나온 해시코드가 중복되는 경우
  • 해시 테이블에서 키값에는 숫자나 문자열 뿐만 아니라 파일 데이터 등 무한한 가지수가 있다. 하지만 해시함수를 통해 결과값으로 나온 해시코드는 정수이다. 즉 무한대로 들어오는 입력에 비해 해시코드는 정수개로 한정지어지므로 당연하게 중복된 해시 코드를 가질 수 밖에 없다. 같은 이유로 해시테이블의 배열의 갯수가 한정되어 있기 때문에 해시코드를 배열의 크기만큼 나머지 연산(%)을 통해 인덱스로 환산 할 경우에도 중복되는 경우가 발생한다.
  • 해결방법으로는 해당 배열방에 배열 또는 리스트를 삽입하여 여러개의 값을 저장하는 것이다. 이런 경우엔 특정 키의 값을 찾기 위해선 해시코드를 통해 데이터의 위치에 접근해 선형검색을 하여 해당키의 값을 찾는다.
• 하나의 인덱스에 모든 키값이 저장되어 시간복잡도가 늘어는 경우 : O(n)
  • 키값이 해시함수를 통해서 산출된 해시코드 or 인덱스 값이 하나 또는 소수인 경우를 말한다. 해당하는 배열방에 여러개의 값을 저장하기 위해서 배열 또는 리스트를 추가해 문제점을 해결했지만, 만약 해시함수를 통해 환산된 해시코드가 하나 또는 소수일 경우에는 원하는 값을 찾기 위해선 해시코드가 가르키는 배열방에서 한번 더 선형검색을 통해 하나씩 비교해야 한다. 최악의 경우엔 일반 배열과 시간복잡도가 같아질 수 있다. 이런 문제점은 해시코드를 고르게 분배할 수 있도록 해시알고리즘을 짜야한다. 하지만 대부분 프로그래밍 언어 내부에 내장되어 있기 때문에 직접 수정하는 일은 거의 없다. 즉 최악의 경우 O(n)의 시간복잡도를 가질수 있다는 것과 고르게 분배할 알고리즘이 해시테이블에서 매우 중요한 이슈이다.

 

따라서 좋은 해시함수의 조건이란 다음과 같다.

• 충돌이 적어야한다.
• 해시함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 한다.
• 계산이 빨라야 한다.