해시충돌을 방지하기 위한 방법
1. 선형 조사법
2. 2차식 조사법
3. 이중 해싱
선형 조사법
- 찾고자 하는 값을 찾을 때까지 뒤로 간다
- 빈 공간을 찾을 때까지 자료구조를 살펴본다
- 자료구조가 차면서 추가된 객체를 찾기 위해 더 많은 칸을 살펴봐야 한다
요소를 제거 할 때
가운데에 있는 요소를 지우고자 할 때
이 요소를 제거하고 이 칸을 null로 설정하는 방식은 사용할 수 없다
-> 나중에 찾고자 하는 요소가 있을 때 중간에 null이 있을 때 null 뒤의 값을 찾을 수 없기 때문이다
어떤 요소가 존재했지만 비었다는 표시를 해야한다
해시값에서 시작해서 null에 도착할 때까지 1씩 더하고 그 위치에 저장한다
-> 추가보다는 제거가 까다롭다
관계가 있든 없든 데이터가 뭉치게 된다 -> 선형 조사법의 비효율적인 부분이다
2차식 조사법
해시값이 있으면 그 위치에 요소를 한 개 넣은 뒤 다른 요소를 넣으려 할 때
공간이 차 있으면 위치값에 1을 더하는 선형 조사법과 달리 그 값의 제곱만큼 더한다
+1^2
+2^2
+3^2
+4^2
선형 조사법이든 2차식 조사법이든 값을 더하면서 테이블의 크기보다 커질 수 있다
->테이블의 끝을 넘어갈 수 있다 이 경우 %연산을 해서 테이블의 범위에 들어오도록 해야 한다
이중해싱
단순히 해시값을 증가시키는 방법이다
hashCode 함수가 한 개가 아닌 두 개가 있다
두 번째 함수가 첫 함수와는 달라야하고 0을 반환하면 안된다
데이터를 가지고 데이터 d의 hashCode를 호출
->값을 양수로 반환 후 테이블의 크기만큼 %연산을 하여 할당
d.hashCode()
e.hashCoce()
e.haseTwo()
두 해시코드 e.hashCoce() e.haseTwo()의 결과를 더한다
-> 이 합은 이 요소가 들어가야 할 테이블 내의 위치가 된다
이중해싱은 아예 다른 해시 함수를 사용할 수 있기 때문에 데이터를 골고루 넣을 수 있다
단점으로는 자료구조에 들어가는 데이터는 두 개의 다른 해시 함수가 필요하다는 것이다
-> 첫 위치를 알기 위한 기본적인 해시 함수와 자리가 할당되어 있을 때 부르는 두 번째 해시 함수가 필요
자바에서는 어떠한 자료 형태에 대해서 두 개의 해시 함수가 있다는 것을 보장할 수 없다
hashCode가 있는 것은 보장할 수 있다 -> 모든 객체는 hashCode 함수가 구현되어 있어야 하기 때문이다
선형 조사법, 2차식 조사법, 이중해싱의 공통적인 단점은 테이블이 빠르게 찬다는 것이 있다
특히 선형 조사법과 2차식 조사법은 적재율이 증가하여 테이블 크기를 바꿔야한다
체이닝(Chaining)
배열의 위치마다 새로운 자료구조를 만들어서 수많은 데이터를 수용할 수 있도록 만들어야 한다
-> 연결리스트로 효율적으로 수행 가능
-> 요소마다 연결리스트를 만들어 수 많은 데이터를 수용할 수 있게 하는 방법이다
상수시간으로 어떤 요소든 추가하고 제거하고 찾을 수 있는 자료구조가 완성된다
체인 해시 : 가장 안정적이고 보편적으로 사용되는 자료구조 중 하나이다
//자바에서는 쉽게 해시를 만들 수 있도록 API를 제공한다
적재율은 항목의 개수를 체입의 배열에 들어있는 요소의 개수로 나눈 값이다
주의할 점 : 체인 해시에 요소를 계속 추가하면 시간 복잡도가 상수가 아닌 O(n)이 되어
체인의 요소를 전부 살펴서 찾아야 한다
-> hashCode가 같은 숫자만 반환한다면 이런 경우가 발생한다
hashCode가 다 다른 숫자를 반환하면 다시 찾거나 제거하려 할 때 상수시간 O(1)이 된다
-> 반환값이 비교적 다양하면 안정적이고 일괄적이면 시간복잡도가 늘어난다
자료구조의 함수와 시간복잡도
size, isEmpty, isFull -> 무조건 상수시간이 걸린다
add, remove, find -> 어떻게 구현하느냐에 따라 복잡도가 변경된다
키와 값은 반환 -> 어떻게 구현하든 O(n)이 걸린다