📌 - Hash table
- 기본적인 해쉬 테이블은 key - value를 저장하는 구조이다
- 예를들어서 50을 저장할 때 index = hash_function(50) % 16 을 통해서 해쉬 값을 받아와서 해당 테이블에 저장한다.
- 이렇게 저장하면 key에 대한 데이터를 찾을 때 한번만 수행하면 index 위치를 찾을 수 있기 때문에 저장과 삭제가 O(1)로 매우 빠르다.
하지만 이런 방식으로 해쉬 테이블을 구현하게 되면 해쉬 값이 겹칠 경우 문제가 발생하는데 겹치게 되면 충돌이 발생한다. 해결 방법으로는
📌 - Seperate Chaining
Linked List를 이용하는 방식으로 각 index 데이터를 저장하는 linked list에 대한 포인터를 가지는 방식이다.
index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 linked list에 노드를 추가하여 값을 추가한다.
이렇게 하면 충돌이 발생하더라도 데이터를 삽입하는데 문제가 없다.
하지만 단점으로 최악의 경우로 같은 index에 계속해서 값이 들어간다면 탐색을 하는데 많은 시간이 들게 되어 비효율적이다.
📌 - load factor
로드 팩터(Load Factor)는 해시 테이블에서 사용되는 지표로, 해시 테이블에 저장된 요소 수와 버킷 수 간의 비율을 나타낸다. 주로 해시 테이블의 가득 차는 정도를 측정하는 데 사용된다.
로드 팩터는 일반적으로 요소 수를 버킷 수로 나눈 값으로 계산된다. 예를 들어, 해시 테이블에 100개의 요소가 있고 버킷이 50개인 경우, 로드 팩터는 100/50 = 2이다.
은 로드 팩터는 해시 테이블에 여유 공간이 많다는 것을 의미하며, 충돌이 발생할 확률이 적어진다. 반대로 큰 로드 팩터는 해시 테이블이 가득 차있거나, 버킷 당 평균 요소 수가 많아져 충돌이 더 자주 발생할 가능성이 높아진다.
로드 팩터를 적절하게 설정하고, 재해싱을 효율적으로 수행함으로써 해시테이블의 성능을 향상시킬 수 있다.
