해시와 해시 테이블 Hash Table <2>

해시 테이블 Hash Table

1편이 있어용

해시 테이블 Hash Table

* 해시 테이블이 시간 복잡도 O(1)을 가지기 위해서는 

  해시 값과 인덱스가 쉽게 매칭이 되어야 한다.     

 

* 하지만 해시 값의 중복이나 인덱스의 중복으로 인해

  둘의 관계가 직관적이지 못 할 수 있다.

 

 

해시 값의 중복

1. 상황에 맞는 해시 함수 선택

  해시 함수에 따라 중복 확률이 다르며

  같은 해시 함수라도 자료형이나 크기에 따라 중복되는 확률이 다르다.

  상황에 맞는 해시 함수를 선택하는 것만으로 

  충돌을 많이 피할 수 있다.

 

1-1. 하지만 완벽하지는 않다.

  상황에 맞는 해시 함수를 선택한다 해도

  해시 함수는 어쩔 수 없이 중복이 생기는 함수이다. 

  다른 해결책과 같이 사용하는 것이 좋다.

 

1-2. 완벽할 수도 있다.

  해시 함수에 어떤 값이 들어가지는 알고 있다면 

  개발자가 해시 함수에 들어가는 값들을 모두 알고 있고

  모두 테스트해봤다면 중복이 없다고 확언할 수 있다.

 

2. Separate Chaining

  배열은 포인트 배열이며

  포인터들은 연길 리스트를 가리키는 구조이다.

 

3. Open Addressing

  비어있는 배열 공간을 찾아 넣는 방식이다.

 

 

Separate Chaining

* 포인트 배열이 연결 리스트를 가리키는 방식이다. 

* 비어있는 공간은 NULL로 판단할 수 있다.

 

장점:

* 연결 리스트의 공간을 미리 할당할 필요가 없으므로

  저장공간의 효율과 미리 총 저장공간을 예상하고 넉넉하게 잡을 필요가 적다.

* 해시 함수가 약간의 중복을 일으켜도 괜찮다.

 

단점:

* 동적 할당이 필요하다.

* 하나의 인덱스에 Node가 쏠린다면 성능이 낮아진다.

 

시간 복잡도:

* Best = O(1)

  Average = O(a)   (a = n / 배열의 길이) 

  Worst = O(n)

 

 

Open Addressing

* 찾은 인덱스가 이미 차있다면 비어있는 인덱스를 찾아 움직인다.

 

* 해시 값과 인덱스가 매칭 되어 있지 않을 가능성이 있으므로

  보통 Key와 Value가 함께 있는 형태가 많다.

 

 

*  비어있는 공간을 찾아가는 정해진 규칙이 있어야 한다.

	비어있는 공간을 찾아가는 규칙 중 몇몇
선형 탐색 Linear Probing	a개를 건너뛰며 빈 공간을 찾는다.
제곱 탐색 Quadratic Probing	해시 값을 제곱 후 다시 인덱스를 찾는다.
이중 해시 Double Hashing	해시 값을 다시 해시 함수에 넣어 해시 값을 구한다.

 

장점:

* 저장공간의 추가나 삭제가 필요 없다. (단점일 수도 있다.)

 

단점:

* Sperate Chaining보다 해시 함수의 영향을 많이 받는다.

* 저장공간의 전체를 미리 예상하고 확보해야 한다.

 

 

해시 테이블은 언제 사용하는가?

사용하면 좋을 때 

* 검색을 많이 하는 구조

* 상황에 맞는 해시 함수가 있을 때 

 

사용하면 안 좋을 때

* 자료의 순서가 중요할 때

* 공간의 효율성이 중요할 때

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.