Loading [MathJax]/jax/output/HTML-CSS/config.js
본문 바로가기

해시충돌1

해시 충돌(Hash Collision)과 최적화 방법 해시 충돌 해시함수는 해시테이블의 키 값으로 레코드가 저장되어 있는 주소(또는 색인)을 산출하는 함수이다. 다른 내용의 데이터가 같은 키를 갖는 상황을 해시 충돌이라고 하는데, 같은 키 값이 생긴다는 것은 특정 키의 버켓에 데이터가 집중된다는 뜻이다. 따라서 빈번한 해시 충돌은 해시테이블의 성능을 저하시킨다. 해결 방법 1) 체이닝 버켓 내에 연결리스트를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터를 연결하는 방식이다. 복잡한 계산식을 사용할 필요가 없고, 삭제 또는 삽입이 용이하다. 해결 방법 2) 개방 주소법 체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려갈 수 있기 때문에 데이터의 주소값은 바뀌지 않는다. 그러나 개방 주소법은 해시 충돌이 일어나면 다른 버.. 2021. 11. 22.

티스토리툴바