해시충돌1 [알고리즘] 해시 충돌 해결 방법 | Hash Collision Seperate Chaining 추가적인 공간을 활용해 충돌을 해결한다. seperate 뜻에 맞게 Linked-List를 사용한다. 보통 헤드에 삽입한다. (테일에 삽입하면 테일까지 가는 시간이 걸리기 때문) 최악의 경우 하나의 해시에 데이터가 몰리면, 조회할 때 Linked-list를 탐색하는 시간이 걸리게 된다. Open Addressing Linear Probing 해시 충돌 발생 시 충돌이 발생하지 않을 때까지 해시를 linear 하게 탐색한다. 단, clustering 군집현상이 발생할 수 있다. Quadratic Probing 충돌 발생 시 해싱 함수에 특정 연산을 더해 새로운 해시를 제작한다. 보통 제곱연산을 쓰는데 추가적인 상수곱이나 제곱연산이 가능하다. 사진을 예시로 3번째 값 hf_q.. 2023. 5. 3. 이전 1 다음
