본문 바로가기

충돌해결1

이전 1 다음

[해시 테이블] 충돌 해결 충돌 어떤 키가 이미 자리잡고 있는 상태에서 다른 키가 삽입을 시도하는 것 동일한 주소에 2개 이상의 키가 해싱되는 상황 충돌 해결 방법 체이닝 개방 주소 방법 체이닝 같은 주소로 해싱되는 키를 모두 하나의 연결 리스트에 매달아서 관리함 해시테이블의 크기가 m이면 최대 m개의 연결 리스트가 존재할 수 있음 같은 주소로 들어온 키들은 해당 헤더 다음에 연결리스트로 매달려 있음 체이닝은 임의의 키를 삽입할 때 해시값이 가리키는 연결리스트에 삽입함 리스트의 맨 앞에 삽입하는 것이 좋음 키를 검색할 때 해당 연결 리스트의 키들을 차례로 지나가면서 찾음 적재율이 1을 넘어도 사용할 수있음 개방 주소 방법 체이닝과 달리 추가 공간을 사용하지 않음. 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결함 모든 키.. 2023. 12. 8.

이전 1 다음

티스토리툴바