본문 바로가기

해시테이블2

이전 1 다음

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

[해시 테이블] 해시 테이블, 해시 함수 해시 테이블은 자료를 검색, 삽입, 삭제하는 데 평균시간이 가능하게 하여 극단적 효율에 다다른 자료구조 키 자신의 값에 따라 자리가 결정됨 해시 테이블은 키가 저장될 자리를 키의 '값'으로 결정하는 자료구조 해시 함수는 임의의 킷값을 입력으로 받아 주소 중 한 값을 리턴함(리턴값=해당 키를 저장하는 자리) 해시 함수 나누기의 방법 곱하기 방법 충돌 어떤 키가 이미 자리 잡고 있는 상태에서 다른 키가 삽입을 시도하는 것 동일한 주소에 2개 이상의 키가 해싱되는 상황 충돌 해결방법 체이닝 : 충돌을 일으킨 키들을 연결 리스트로 관리하는 방법 개방 주소 방법 : 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 것 검색 시간 체이닝, 개방 주소 방법으로 검색할 때의 기대시간 적재율 해시 테이블에 원.. 2023. 11. 30.

이전 1 다음

티스토리툴바