[CS 문답] 해쉬 충돌과 해결방법은 무엇인가요?

Hash Collision key는 다른데 hash값이 같을때 key도 다르고 hash값도 다른데, capacity로 나눈 모듈러값이 같을때 두 경우 모두 해쉬충돌이라고함. 원천적으로 충돌을 피하는건 불가능하고 충돌이 일어났을때 해결해야함. Hash Collision 해결 체이닝 기법 충돌이 발생한 인덱스 자리에 링크드리스트 기법으로 key, value, next_address를 모두 저장하여 해결 늘리는 타이밍 : 보통 capacity의 3/4정도 차면 두배로 늘림. 개방주소법(설명할 것은 linear probing) 충돌이 발생한 인덱스 자리의 다음 인덱스에 삽입을 시도함. key를 지울때 더미값을 넣어야함!!! 그래야 다음번 버켓을 찾으려는 시도를 하므로. 더미값이 없으면 아 원래 한번도 삽입되지 않은 버켓이구나 하고 바로 끝남. hash table의 사이즈를 늘려야할때, 늘어난 사이즈로 다시 모듈러연산을 해서 확장함 key, value, hash값 세가지를 같이 저장해놓음 그...

원문링크 : [CS 문답] 해쉬 충돌과 해결방법은 무엇인가요?