[CS/자료구조] ChainHash, maxLoadFactor(λ_max)

오늘 공부한 재밌는 개념 체이닝(Chaining)

https://www.boostcourse.org/cs204/lecture/625974/?isDesc=false 

자바로 구현하고 배우는 자료구조

우선 해쉬 테이블에 값에 따른 주소를 반환하기 위해서 

1. Hashcode로 돌린다.

2. 나온 정수가 있다면(int a 가정) 양수로 바꿔준다  8바이트의 경우 -> a & ox7FFFFFFF 를 통해(index 값은 음수를 가질 수 없다)

3. %tablesize를 통해 나머지 반환해서 그것을 index로 지정!

 

하지만 같은 index 값이 나올 때 해쉬 충돌이 발생한다.

+1, 제곱수 더하기, 이중 해쉬등의 해결 방법이 있지만 Chain hash를 이용하면 깔끔하게 된다!

 

이전시간에 왜 그렇게 주구장창 연결 리스트(Linked list)를 배웠는지 이해가 간다.

부족한 내 필력을 메우기 위해 참고할 수 있는 블로그를 찾아봤다.

https://twinparadox.tistory.com/518

해시테이블(Hash Table)과 체이닝(Chaining)에 대한 간략한 정리

좀 전문적으로 적으셔서 쪼꼼 어려울 수 있지만 요지는 간단하다. 

Hash Table의 index 마다 처음 들어간 값을 head로 잡고 linked list를 만들어주면 된다!! 

교수님 말씀으로는 이게 최고의 자료구조라고 한다.

파이썬의 Dictionary, 자바에서도 기본적으로 제공하는 hash가 Chaining을 이용한 Hash table이라고 한다.

이게 좋은 이유는 add, remove, find등의 시간이 일단 상수시간으로 주어지고

연결리스트의 덕택으로 사이즈에도 한계가 없다는 것이다.

 

하지만 단점은 물론 존재한다.

최악의 경우 - 예를 들어 해쉬 Value가 전부 같은 값만 나와서 결국 해쉬테이블의 이점은 못살리고 하나의 연결리스트처럼 되어버린 경우

그냥 연결리스트랑 같아져버리는 것이다. O(n)의 시간 복잡도를 가진다. add, remove, find등의 함수가

 

람다(λ)도 기억하자 적재율을 뜻하고 채워진 갯수/테이블 길이 정도로 기억하자

자료구조에서 최대적재비율과 테이블의 크기의 관계는 오묘하다.

최대적재 비율이 낮으면 연결리스트를 더 고르게 분포시킬 수 있겠지만 너무 낮으면 너무 자주 테이블의 크기를 바꿔서 오히려 시간이 더 낭비 될 수 있다.

 

일반적으로, 또 자바에서도 0.75를 적정 비율로 잡고 있다고 한다.

 

 

크기가 다른 해쉬테이블로 옮기려고 할 때 그냥 옮기면 안되고 넣어준 값들을 다시 해슁 해줘야 한다.

왜? 마지막 3번 과정 테이블 사이즈가 달라졌기 때문