HashTable이란??
(Key, Value)로 데이터를 저장하는 자료 구조
Key를 hash function에 넣으면 고유의 값이 나오게 된다. 이 고유의 값을 index로 활용해서 검색 저장하는 테이블을 HashTable이라 합니다.
이상적인 조건하에 HashTable의 장점은 검색, 삭제, 삽입 모두 O(1)이라는 점이다.
(이상적인 조건은 아래에 적겠습니다.)
하지만 단점도 존재한다.
- 일반적인 배열에 비해서 저장공간이 많이 필요한다.
- Hash 충돌에 대한 별도의 자료구조가 필요하다.
- 순차적인 값들을 정렬 혹은 값들이 필요할 때는 배열에 비해 비효율적이다.
Hash 충돌
Hash 충돌이 일어나지 않는 것이 HashTable에서 가장 이상적인 상황이다.
그럼 Hash 충돌에 대해서 알아보자
다른 Key를 줬음에도 불구하고 hash function을 통해서 같은 값을 반환하면 값이 Overwrite하게 된다!
다른 값을 주었지만 같은 hash function 반환 값으로 인해 생기는 경우를 Hash 충돌이라고 한다.
이럴 경우 Value 하나를 잃어버리기에 당연히 똑똑한 개발자들은 이걸위한 해결책들을 만들어 놓았다.
Hash 충돌 해결법
연결법 / Chaining
분리 연결법은 Hash 충돌이 일어난 부분에 Linked List 처럼 계속해서 체인을 거는 방법
단점은 계속해서 체인이 걸린다면 저 체인들 속에서 값을 찾는 것도 큰 일이 될 것이다.
디도스를 공격하는 방법 중 한 방법이라고 한다.
Open Addressing
충돌 발생 시 해시함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장한다.
선형 프로빙 ( Linear probing )
선형 프로빙은 바로 슬롯에 데이터를 저장하는 방법이다.
하지만 이 방법은 삭제에 문제가 날 수 있다.
차례대로 가다가 중간에 삭제하게 된다면 데이가 손실 날 수 있다.
중간에 빨간 칸을 Value를 삭제하게 된다면 그 이후 검색 안되는 경우가 발생합니다.
따라서 삭제를 했다면 삭제했다는 표시를 해줘야 합니다.
장단점
한 번 충돌이 나면 집중적으로 충돌이 발생합니다. 이로 인해서 시간이 많이 소요 될 수 있습니다.
이중 해시
해시 충돌이 나면 다른 해시 함수로 값을 해시하여 그 값 만큼 현재 주소에 더하여 새 주소를 얻는 방법이다.
'Programming > CS' 카테고리의 다른 글
| [CS] 정렬 sort (0) | 2023.04.21 |
|---|
