Data Structure - Hash Table (2)

1. Linear Probing 기법 

- Close Hashing(폐쇄 해싱) 기법 중 하나로, 해싱충돌이 발생하면 Hash Table의 저장공간 안에서 충돌을 해결하는 기법이다. 

- 다시 말해, 충돌이 발생하면 Hash address를 이용하여 Hash Table의 빈공간을 찾아 저장하는 기법이다. 

- 이 기법을 사용하면 Hash Table의 저장공간 활용도를 높일 수 있다. 

---

2. Linear Probing 기법 구현하기 

[기본 구조]

시나리오1) 새로 추가하려는 데이터의 hash값에 이미 다른 데이터가 저장되어 있는 경우, hash table을 검색하여 가장 첫번째로 찾는 빈 공간에 데이터를 저장하는 방식이다. 

hash값	value
0	a
1

- 위의 표를 기반으로 설명합니다. 만약에 hash값이 0인 자리에 b라는 value를 넣는다고 한다면 linear probing기법에 의해 가장 첫번째 빈 공간인 1번 hash값 자리에 value를 저장하게 된다. 

hash값	value
0	a
1	b

- 문제점은 b를 다시 읽어올 때 발생한다. 왜냐면 a와 b 모두 동일한 hash값을 기반하여 저장된건데, 찾으려는 value가 a인지 b인지 구분하지 못하기 때문이다. 그래서 key값과 value를 같이 저장한다.

hash값	key값 / value
0	1023533 / a
1	09186483 / b

- 위의 개념이 이해됐다면 코드로 구현해보자. 

 

 

a) 데이터를 저장하는 메소드 

- 데이터를 저장하려는 hash값에 이미 데이터가 존재하는지 검증한다

- 이미 데이터가 존재한다면 가장 첫번째 빈 저장공간에 저장한다

- 데이터를 저장할 때는 항상 key값과 value를 함께 저장한다. 

 

b) 데이터를 읽는 메소드 

- 내가 찾는 data의 해시값(저장공간)에 data가 존재하는지 확인 / data가 없다면 저장된 적 없다는 뜻 

- data가 존재한다면 내가 찾는 data의 key값과 매치하는지 확인 / data가 없다면 저장된 적 없다는 뜻 

- 해당 key값과 매치하지 않는다면 다음 공간을 검색 

- 다음 공간을 검색하는데 0이 나오는 경우, 내가 찾는 data는 저장된 적이 없다는 뜻

 

c) 검증

 

1. 동일한 hash값을 가진 key를 찾는다. 
- hash_table에 저장된 data가 없다는 전제하에 둘 중 하나의 값은 hash_table[hash_address]에 저장, 다른 하나는 hash_table[hash_address + 1]에 저장되어야 한다. 

- 위의 사진의 경우 hash값이 5이기 때문에 하나는 hash_table[5]에, 다른 하나는 hash_table[6]에 저장되어야 한다. 

 

 

2. 저장 후 올바른 위치에 저장되어 있는지 확인한다. 

 

 

3. 키값에 따라 올바른 value가 검색되는지 확인한다. 

---

3. Hash Table사용 시, 꼭 알아두어야 할 중요 사항! 

1) 빈번한 충돌을 개선하는 방법 - 해쉬 함수을 재정의 및 해쉬 테이블 저장공간을 확대

- 현재 정의된 hash table 저장공간의 50% 이상을 사용해야 한다면 충돌 확률이 커지기 때문에 hash table의 크기를 두배이상 늘려야 한다. 

 

2) 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있다.

- 유명한 해쉬 함수들을 사용한다. ex) SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)

- hash값을 가지고 원래 어떤 data로 생성된 것인지 알아낼 수 없어서 안전하다. 

- 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

* SHA함수는 문자열을 반환하기 때문에 반드시 정수형으로 바꿔주어야 한다.

 

 

[SHA-1 사용방법]

 

 

[SHA-256 사용방법]

 

 

[기존 코드에 SHA 적용해보기]

- get_key()함수만 바꿔주면 된다. 

 

 

[작동 확인]

---

4. Hash Table의 시간복잡도 

 

일반적인 경우(Collision 없음)는 O(1)

- 최악의 경우(Collision이 모두 발생)는 O(n)

* 해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에 시간복잡도는 O(1) 이라고 말할 수 있다.

* Collision(충돌)은 반드시 없애야 하는 것이다.

 

ex) 검색에서 해쉬 테이블의 사용 예

- 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)

- 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)