Hash Collision, 해시 충돌시 해결방법
해시 충돌이 일어났을 경우 해결하는 방법은 크게두 가지가 있습니다. 1. 체이닝(Close Addressing) 해시 충돌이 발생하면 키에 해당하는 데이터들을 연결하는 방식입니다. 1) 연결 리스트를 사용하는 방식(Linked List) 각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision이 발생하면 해당 bucket의 list에 추가하는 방식이다. 삭제 또는 삽입이 간단하다. 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다. 2) Tree를 사용하는 방식 (Red-Black Tree) 트리를 사용하는 방식은 메모리 사용량이 많다. 2. 개방 주소법(Open Addressing) 해시 충돌이 일어나면 다른 버킷에 데이터를 저장하는 방식입니다. 1..
