뼈
컴퓨터 세상에서 모든 객체는 정수로 표현이 가능하다. (메모리) 즉, 모든 데이터를 정수로 표현하고, 특정 정수를 통해 나눈 나머지를 이용한다고 가정한다면 나머지의 집합 범위로 축소시켜 모두 저장할 수 있다.
패러다임의 전환
생각의 틀 변경
기존의 배열은 메모리 공간에 데이터를 저장하고, Index를 통해 접근한다.
⇒ 배열의 Index 가 곧 데이터라면??
Index를 통해 데이터로 바로 접근 할 수 있으므로 O(1) 성능으로 데이터 검색 가능
-20241026191207374.webp)
하지만 이 방법에는 문제가 발생한다. 저장하는 데이터의 값이 늘어나면 배열의 크기가 늘어나고, 낭비되는 메모리의 양이 함께 늘어난다.
배열의 크기를 고정시키고, 해당 크기로 데이터를 나머지 연산으로 데이터를 저장한다면 크기가 큰 데이터도 지정한 범위의 인덱스에 저장할 수 있게 된다.
⇒ 배열의 크기를 조정할 수 있으며 낭비되는 메모리를 최소화 시킬 수 있다.
해시의 충돌
이처럼 나머지 연산을 통해 Hash Index를 사용해 검색을 O(1), 메모리의 낭비를 최소화하여 데이터를 저장할 수 있게 되었다.
한계점 예를 들어 1의 데이터와 11의 데이터가 있고, 배열의 크기(Capacity)가 10이라면? 1 % 10 = 1 / 11 % 10 = 1 의 동일한 Hash Index를 가지게 되고, 같은 인덱스의 두 데이터가 들어가는 현상( 해시의 충돌 ) 이 발생 된다.
해결
해시 충돌의 확률은 낮고 해시 충돌을 인정해 버린다.
⇒ 충돌이 일어났을 경우 같은 인덱스에 두 데이터 모두 저장해버린다.
-20241026191056577.webp)
충돌이 일어난 9, 99 데이터를 배열 9번 인덱스에 LinkedList를 활용해 둘다 넣는다.
⇒ Hash Index 까지의 검색은 O(1)로 가고 인덱스 내부 데이터 검색 (equals)로 순회는 O(n)의 복잡도
하지만 해시 충돌은 매우 드문 일이고, 충돌된 데이터들의 수는 매우 적을 것이기 때문에 매우 빠르게 값을 찾을 수 있다.
시간 복잡도
해시 인덱스를 사용하는 경우
- 데이터의 저장
- 평균 : O(1)
- 최악 : O(n)
- 데이터 조회
- 평균 : O(1)
- 최악 : O(n)