[파이썬] Hash Table 구현과 Hash Collision 해결 기법

  해쉬 테이블(Hash Table)은 키(Key)와 데이터(Value)를 저장하는 데이터 구조로, 키와 짝을 이루는 데이터를 빠르게 찾을 수 있는 특징이 있다. 해쉬(Hash)는 임의의 값을 고정 길이로 변환하는 것으로, 해쉬 함수(Hashing Function)을 통해 해쉬 값(Hash Value)을 산출할 수 있다. 즉 해쉬 테이블의 키를 해싱 함수로 연산해서 얻은 해쉬 값을 기반으로 데이터 저장 위치를 정하는 것이다.

 

  해쉬 테이블은 배열처럼 미리 데이터 공간을 생성한 후 사용한다. 따라서 서로 다른 키들의 해쉬 값이 우연히 같을 경우, 같은 공간에 데이터를 저장해버리는 충돌(Collision) 문제가 발생할 수 있다. 따라서 이 문제를 해결하기 위한 여러가지 알고리즘들이 존재한다.

 

  참고로 파이썬에서는 딕셔너리(Dictionary) 타입을 사용하면 해쉬 테이블을 별도로 구현하지 않아도 된다.

 

• 장점
  - 데이터 저장/검색/삭제 속도가 빠름
  - 중복 확인이 쉬워 캐시(Cache) 구현에 사용됨
• 단점
  - 일반적으로 저장 공간이 많이 필요함
  - 여러 키에 해당하는 주소가 동일할 경우 충돌 해결을 위한 별도의 작업이 필요함

 

< 리스트를 활용해 간단한 해쉬 테이블 구현 >

 

  위에 구현한 해쉬 함수는 데이터를 저장할 때 중복된 해쉬 주소가 생성될 경우(충돌이 발생할 경우), 데이터를 덮어써버리는 문제가 발생한다. 따라서 이러한 문제를 해결하기 위한 충돌 해결 알고리즘을 구현할 필요가 있다.

  충돌 해결을 위한 방법은 크게 두 가지로 나눌 수 있다. 첫 번째는 충돌이 발생했을 때, 연결리스트(Linked List)를 이용해 데이터를 추가로 뒤에 연결시켜 저장하는 기법이고, 두 번째는 충돌이 일어난 해쉬 주소의 다음 주소들 중 빈 공간에 데이터를 저장하는 기법이다. 전자는 Open Hashing 기법, 후자는 Close Hashing 기법으로, 후자의 경우가 저장 공간을 더 효율적으로 사용한다. 그리고 저장된 데이터들 간의 구분을 위해 Value 뿐만 아니라 Key도 함께 저장한다.

 

< Open Hashing 기법 적용하기 : Chaining >

< Close Hashing 기법 적용하기 : Linear Probing >

* 시간 복잡도

해쉬 테이블의 시간 복잡도는 충돌이 없을 경우 O(1), 충돌이 모두 발생할 경우 O(n) 이다. 일반적으로 충돌이 없을 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1) 이라고 말할 수 있다.

 

** SHA(Secure Hash Algorithm) : 고정된 크기의 유일한 값을 리턴해 주는 함수로 Key Hashing 적용해보기