해시 테이블(HashTable)

※ Direct Address Table
크기가 U인 테이블에서 key를 이용하여 데이터를 저장하는 자료구조이다. 중복되는 key는 없다고 가정한다. 시간 복잡도가 O(1)로 검색, 삽입, 삭제가 매우 빠르다는 장점이 있으나, 적재율이 낮다면 실제 대부분의 메모리 공간은  낭비된다는 단점이 있다.

 해시 테이블(HashTable)

 

해시 테이블(Hash Table)이란 해시 함수를 사용해서 변환된 값을 인덱스(index)로 삼아 key-value 쌍으로 데이터를 저장하는 자료구조로, Direct Address Table에서의 공간 낭비를 줄이고 시간 복잡도를 낮추기 위해 만들어졌다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.

 

 

해시 함수(Hash Function): 입력된 데이터를 고정 길이의 불규칙적인 숫자로 변환해주는 함수

해싱(Hashing): 해시 함수를 이용하여 임의의 값을 고정된 크기의 값으로 변환하는 작업

해시값: 해시 함수를 거쳐서 반환된 불규칙적인 숫자. 이는 일반적으로 16진수로 표기된다. 배열의 인덱스로 사용된다.

 

 

< 해시 테이블의 특징 >

• 해시 함수는 반환되는 데이터의 길이가 바뀌지 않는다.
• 동일한 key를 넣으면 항상 동일한 해시값이 반환된다.
• 전혀 다른 데이터를 넣었을 때 아주 낮은 확률로 동일한 반환값이 출력될 수 있다. => 해시값 충돌

내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문에 평균적으로는 O(1)의 빠른 검색 시간 복잡도를 가지고 있지만, 해시 충돌이 많이 일어난다면 최악의 경우에는 O(n)의 시간 복잡도를 가진다. (∵연결 리스트 탐색)

 

 

 

 해시 충돌이란?

해시 충돌(Hash Collision)은 서로 다른 key에 대해 동일한 해시값을 갖는 경우를 말한다. 해시 테이블에 접근하는 key값은 무한하지만, 해시 함수를 통해 나오는 해시값은 메모리의 한계로 인해 유한하기 때문에 발생하는 문제이다. 

 

※ 참고

① 비둘기집의 원리란 n+1마리의 비둘기가 n개의 비둘기 집에 들어간다면, 반드시 하나의 비둘기 집에는 두 마리 이상의 비둘기가 들어가 있다는 것이다. 해시 테이블의 key는 비둘기고, 해시 인덱스값이 비둘기 집이라고 했을 때, key는 무한하고 해시값은 유한하므로 특정 해시 인덱스값에 대해서 겹치는 key가 존재할 수밖에 없다.

② 적재율(Load Factor)이란 해시 테이블의 크기 대비 키의 개수를 말한다. 키의 개수를 k개, 테이블의 크기를 n이라고 했을 때 적재율은 k/n이다. 적재율이 1 초과인 해시 테이블은 반드시 해시 충돌이 발생한다.

 

 

< 해결 방법 >

1. 해시 테이블의 구조 개선
2. 해시 함수 개선 => 충돌이 적은 해시 함수 사용

 

• 분리 연결법(Seperate Chaining) : 인덱스의 버킷을 연결리스트로 구현해, 이미 값이 존재하더라도 연결리스트에 해당 값을 삽입하는 방식
• 개방 주소법(Open Addressing) : 해시 충돌이 일어난 경우, 특정한 간격만큼 이동 후 비어있는 주소 값에 저장하는 방식