[운영체제] hashtable의 충돌이 발생한다면?

 

 

hashtable(해시테이블) 정의 

 

먼저, 해시테이블의 정의에 대해서 알아보겠습니다. 해시테이블(Hash Table)은 키(Key)를 값(Value)에 매핑하여 데이터를 저장하는 자료 구조입니다. 이 구조는 효율적인 검색, 삽입, 삭제 작업을 위해 사용됩니다.

 

 

해시테이블에서 충돌 발생시?

 

해시테이블에서 충돌(Collision)이 발생하면, 두 개 이상의 키가 동일한 해시 값을 가지게 되어 같은 위치에 저장될 상황이 발생합니다. 

1. 체이닝(Chaining): 충돌이 발생한 각 해시 버킷에 대해 연결 리스트를 사용하여 모든 항목을 저장합니다. 충돌이 발생하면 해당 버킷의 리스트에 항목을 추가합니다.
2.  
3. 오픈 어드레싱(Open Addressing): 충돌이 발생하면 다른 버킷에 항목을 저장합니다. 이 방법에는 여러 가지 변형이 있는데, 대표적인 것으로는 선형 조사(Linear Probing), 이차 조사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있습니다.
   • 선형 조사(Linear Probing): 충돌이 발생하면, 바로 다음 버킷을 검사합니다. 이미 차있다면 계속해서 다음 버킷을 순차적으로 검사합니다.
   • 이차 조사(Quadratic Probing): 선형 조사와 비슷하지만, 탐색 간격이 제곱수로 증가합니다.
   • 이중 해싱(Double Hashing): 두 번째 해시 함수를 사용하여 빈 버킷을 찾습니다.
4. 동적 리사이징(Dynamic Resizing): 해시테이블의 부하 계수(Load Factor, 즉 해시테이블에 저장된 항목 수 대비 해시테이블의 크기 비율)가 특정 임계값을 초과하면, 해시테이블의 크기를 증가시키고 모든 항목을 새로운 테이블에 재해싱합니다. 이는 충돌의 가능성을 줄이고 성능을 개선할 수 있습니다.

각 해결 방법은 특정 상황에 더 적합할 수 있으며, 해시테이블의 성능은 사용되는 해시 함수의 품질, 해시테이블의 크기, 저장되는 데이터의 특성 등에 크게 의존합니다.