해시

해시 알고리즘을 쓰면 O(N)의 성능을 O(1)로 끌어올릴 수 있다. O(1)이라는건 인덱스 기반

데이터를 인덱스의 값으로 같이 쓰면 중복 검사를 하지 않고 조회 시 빠르게 할 수 있음

그런데 그럼 메모리 낭비가 심하다 나머지 연산으로 메모리를 아낀다 하지만 해시 충돌이 일어날 수 있다.

해시 충돌은 인정해야한다. 대신 자바에서는 나머지 연산 및 갖가지 수학적 요소로 해시 충돌을 최대한 막고 사실상 충돌이 일어나는 일은 많지 않다.

충돌이 일어나면 해시 안의 배열 같은 인덱스에 값이 여러개 들어가야하고 거기서 풀스캔을 해야한다.

그래서 해시는 O(1)을 보장하는건 아니고 최악의 경우 O(N)이 될 수도 있다.

하지만 그런일은 잘 일어나지 않고 O(1)에 가깝다고 볼 수 있다.

 

 

해시 기반 자료 구조를 사용하는 경우 통계적으로 보면 입력한 데이터의 수가 배열의 크기의 75%를 넘을 때 부터 충돌이 자주 일어나기 시작한다.

자바는 데이터의 수가 배열의 수의 75%를 넘으면 배열 크기를 2배늘린다.