분리 연결법 (Separate Chaining)
링크드 리스트 또는 트리를 사용하는 방법이다. 링크드 리스트를 바탕으로 한번 알아보자 !
테이블 크기가 5일 때 해시로 1을 반환하는 1001, 11, 21, 31 을 저장할 때 분리 연결법을 사용하면 밑에 그럼처럼 된다.
어라? 근데 1001, 11, 21, 31 순서가 아니네요?! 🙋♂️
수행시간을 줄이기 위해 사용하는 방법이다. 어떻게 되는지 살펴보자.
자 링크드 리스트니까 다음 노드 값을 저장해준 것이다. 만약에 41이라는 값을 추가 하게되면 남은 메모리 주소에 저장을하고 새로운 노드를 리스트에 붙여야하니까 해당 리스트의 마지막 노드인 메모리 4에 저장된 노드까지 찾아가야한다.
그 다음 메모리 4에 저장된 값을 {값:31, 다음 노드:99}로 바꿔주면 끝난다.
문제는 새 노드를 리스트에 붙이기 뒤해서 메모리 4에 저장된 노드를 찾는 과정이다. O(n)으로 찾아가기때문에 시간이 소요될 것이다. 뭐 지금은 4니까 금방인것처럼 보이지만 만약에 정말 많은 값의 데이터면 너무 오래걸릴 것이다.
근데 순서를 반대로 뒤집으면 데이터 삽입이 한결 좋아진다. 한번 살펴보자
맨 앞에 노드를 추가하는 것이라 다른 노드를 탐색할 필요 없다. 리스트의 꼬리에 데이터를 붙이기보다는 머리에 붙이는 방법을 보통 많이 사용한다.
대신 이렇게 분리 연결법을 사용하려면 해시 함수의 역할이 중요하다. 균일하지 못한 해시를 사용해서 특정 인덱스에 데이터가 몰리게 된다면, 다른 곳은 비어있고 한 버킷에 저장된 리스트의 길이만 계속 길어지기 때문이다.
만약에 리스트의 맨 마지막에 위치하고 있었다면, 링크드 리스트를 O(n)의 시간복잡도를 가지게 되기 때문에 저장하고자 하는 데이터를 균일하게 뿌리고 리스트의 길이를 어느 정도로 유지해주는 해시 함수의 역할이 중요하다.
