[파이썬 | 자료구조] 6. 해시 테이블(Hash Table)

해시 구조란?

Key와 Value 두 쌍으로 이루어진 데이터이다.

Key를 이용해서 Value를 찾는다. (최선 : O(1) 최악 : O(N))

파이썬에서는 기본적으로 제공되는 딕셔너리 자료형이 해시 테이블과 같은 구조이다.

검색, 저장, 삭제가 잦은 경우 사용하면 속도가 빠르다.

하지만 저장공간이 더 많이 필요하며(넉넉하게 필요하며), 해시 값이 같은 경우 충돌을 해결하는 알고리즘이 필요하고, 최악의 경우 시간복잡도가 O(N)으로 증가하게 된다.

어떤 Key값에 대해서 숫자(주소값)로 바꿔주는 함수를 해시 함수라고 한다.

해시 테이블이란 해시 함수로 접근하는 데이터 구조를 뜻한다.

파이썬에서는 특정 문자열을 숫자값으로 바꿔주는 hash()함수가 있는데 파이썬3 부터 보안을 이유로 프로그램을 실행할 때마다 값이 달라진다.

그래서 해시 테이블을 구현할 때 간단하게 해시값을 만드는 방법으로는 각 문자열의 아스키코드 값을 다 더하는 것이다. 그렇지만 이 방법은 "ABC"와 "ACB"의 해시값이 같아서 충돌이 빈번하게 일어나기 때문에

각 자리 아스키코드값을 더할때마다 특정 소수를 곱해서 충돌을 피하게 만든다.

그럼에도 불구하고 결국 충돌을 완전히 피할 수는 없다.

충돌 해결 알고리즘은 크게 2가지로 나눌 수 있다.

1. Chaining

   버킷(해시 함수값에 따라 데이터를 넣을 수 있는 공간)에 여러개의 데이터를 Linked List형태로 계속 연결해서 연결하는 방법.

   같은 해시 함수는 같은 버킷에 계속해서 들어간다.

2. Open Addressing

   버킷에 하나의 데이터만을 넣을 수 있을때는, 해시 함수의 충돌을 피해야 한다.

   따라서 이미 특정 해시 함수의 버킷에 데이터가 있는 경우에 해시 함수값을 변경시켜서 빈 버킷을 찾는다.

   해시 함수값을 변경시키는것에도 크게 2가지 방법이 있다.

   1. Probing (Linear/Quadratic)

      Linear는 해시값을 1씩 계속해서 증가시키는 방법

      Quadratic은 해시값을 1, 4, 9, ... 로 제곱해서 증가시키는 방법

   2. Double Hashing

      해시값을 증가시키는 값도 해시함수로 계산하는 방법

Chaining 방법

Open Addressing 방법