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)
'컴퓨터공학기초 개념 > 알고리즘 개념' 카테고리의 다른 글
Data Structure - Heap(1) (0) | 2020.08.31 |
---|---|
Data Structure - 트리(Tree) & 이진탐색트리(Binary Search Tree) (0) | 2020.08.26 |
Data Structure - Hash Table (1) (0) | 2020.08.22 |
Data Structure - 시간 복잡도(Time Complexity) (0) | 2020.08.21 |
Data Structure - Linked List (2) (0) | 2020.08.20 |
댓글