[알고리즘] 해시테이블과 충돌 회피 방안

일반적으로 효율적인 데이터의 저장 방법(직접 주소 테이블)

일반적으로 (key : value) 데이터를 기본 자료구조에 배치하면 탐색에 O(N)이 걸리거나 삽입/삭제에 O(N)이 걸린다. 가장 빠른 방법이 배열의 index로 key를 사용했을 때 탐색에 O(1) 시간이 걸린다. 그러나 key값의 종류가 대략 10^16 정도로 매우 많아지면 똑같이 배열로 구현할 수 있을까? 현실적으로 불가능하다. 혹은 key값이 최대 2000인데 실제 존재하는 key값은 0, 2000 뿐이라면 배열의 1~1999까지의 공간은 낭비된다. 이러한 문제들을 해시 테이블을 통해 해결할 수 있다.

---

해시 테이블이란?

해시 테이블은 임의의 길이를 가진 key값에 해시함수를 적용해 고정된 크기의 index를 생성하여 그 index에 값을 저장/삭제/탐색하는 자료구조이다. 해시 함수는 간단하게 나머지 연산자를 이용할 수 있고 다른 다양한 방법들이 많다. 해시 함수에서 가장 중요한 점은 충돌이 적게 일어나는 해시 함수를 짜야한다는 것이다. 충돌은 또 뭘까?

 

충돌이란 서로 다른 키가 같은 해시 값을 가져 해시 테이블이 꼬여버리는 상황이다. 해시 함수를 적절하게 잡아서 충돌이 발생하지 않게 만들 수 있지만 그렇게되면 데이터가 너무 많아서 이의 범위를 줄여 저장하려는 해시 테이블의 역할을 하지 못한다. 따라서 충돌을 막을 수는 없지만 충돌이 발생했을 때 회피 방안으로 크게 두 가지가 있다.

---

충돌 회피 방안 - Chaining

Chaining에서는 해시 테이블의 각 인덱스마다 연결 리스트나 동적 배열을 하나씩 두고, 삽입이 발생하면 해당 인덱스의 연 리스트에 값을 추가한다. 이러면 충돌이 일어나도 편하게 연결 리스트에 추가해 주면 된다. 삽입/삭제도 같은 원리로 가능하다. 이 방법은 최악의 상황에서도 탐색/삽입/삭제에 O(N)을 보장한다.

---

충돌 회피 방안 - Open Addressing

개방 주소화 방법은 간단히 말해서 내 집이 없으면 옆집 무단점거하기이다. 만약 해시 테이블의 해시값에 해당하는 칸이 비어있다면 바로 내용을 채운다. 그렇지않고 이미 해당 칸에 내용이 있다면 빈칸이 나올 때까지 그 다음칸으로 가서 내용을 쓴다. 삽입/삭제/탐색 모두 O(N)의 시간을 보장하지만, 테이블이 완전 가득 찰경우 충돌을 해결할 수 없다. 삭제/탐색을 자세히 보자.

 

탐색도 같은 방식이다. 먼저 찾고자하는 key의 해시값의 칸을 본다. 그 값과 찾고자 하는 값이 다르다면 그 값이 나올 때까지 다음 칸으로 이동하며 탐색한다. 만약 찾고자 하는 값이 테이블에 없다면 다음 칸이 빈칸이거나 테이블의 끝까지 탐색하면 된다. 삭제는 조금 주의가 필요하다. 그냥 값을 날린다면 그다음에 있는 값을 탐색할 때 문제가 생길 수 있다. 따라서 쓰레기 값을 두어서 삭제해야 한다.