[Java] 30. Hash

Hash

#Java

Set이란?

• 세트(셋)는 유일한 요소들의 컬렉션
• 특징
  • 중복된 요소가 존재하지 않음
  • 순서를 보장하지 않는다.
  • 빠른 검색: 요소의 유무를 빠르게 확인할 수 있도록 최적화되어 있다.
• 용도: 중복을 허용하지 않고, 요소의 유무만 중요한 경우에 사용

예시:

• List: 장바구니 목록, 순서가 중요한 일련의 이벤트 목록.
• Set: 회원 ID 집합, 고유한 항목의 집합.

셋 직접 구현하기

단순히 배열에다가 추가하는 방식을 생각해보자.

메서드

• add(value) : 셋에 중복된 값이 있는지 체크하고, 중복된 값이 있으면 false 를 반환한다. 중복된 값이 없으면 값을 저장하고 true 를 반환한다.
• contains(value) : 셋에 값이 있는지 확인한다. 값이 있으면 true 를 반환하고, 값이 없으면 false 를 반환한다.

성능

• add()로 데이터를 추가할 때 셋에 중복 데이터가 있는지 전체 데이터를 항상 확인해야 한다. 따라서 O(n)으로 입력 성능이 나쁘다.
  • 중복 데이터 검색 O(n) + 데이터 입력 O(1) O(n)
• contains() 로 데이터를 찾을 때는 배열에 있는 모든 데이터를 찾고 비교해야 하므로 평균 O(n)이 걸린다.

Set을 정의할 때는 굉장히 단순하게 정의했지만, 데이터 추가, 검색 모두 O(n)으로 성능이 좋지 않다.
이 부분을 개선하기 위해 해시(hash) 알고리즘이 등장했다.

해시 알고리즘

인덱스와 데이터

배열 기반 set에서 O(n)이던 검색 성능을, 해시 알고리즘을 통해 검색 성능을 평균 O(1)로 끌어올릴 수 있다.
우리는 성능을 끌어올리기 위해서 일부 메모리 공간을 희생할 수 있다. 단순히 생각하면 인덱스를 통한 조회가 O(1)이기 때문에, 인덱스가 데이터 값을 의미한다면, 데이터가 존재하는지를 O(1)로 확인할 수 있다.

문제점
그런데, 값의 범위가 만약 10억이라면? 10억개의 데이터를 담을만한 메모리 공간이 필요하다. 즉, 입력 값의 범위 만큼 큰 배열을 사용해야 하기 때문에 공간 낭비도 심할 뿐더러, 하드웨어 스펙상 매우 넓은 범위의 값(정수, 소수, 문자열…)을 담는 것은 불가능 할 것이다.

나머지 연산

정수 데이터를 특정 값으로 나눈 나머지를 인덱스를 사용한다고 해보자. 예를 들어 0 ~ 99 범위의 값을 10으로 나눈다면, 크기가 10인 배열이 필요할 것이다.

• 9 9
• 12 2
• 81 1

해시 인덱스(or 해시 값)
이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스(hashIndex)라 한다.
우리는 나머지 연산을 바탕으로 한 해시 인덱스를 사용해서 O(1)의 성능으로 데이터를 저장하고, O(1)의 성능으로 데이터를 조회할 수 있다.

해시 충돌
하지만, 나머지 연산을 통해 해시 인덱스를 구하는 방식에는 문제가 존재한다. 10으로 나눈 나머지가 같은 값들에서 충돌이 발생한다. 1과 11은 해시 인덱스 1에서 충돌이 발생한다.

이를 해결하는 방법 중 하나는, 값의 범위만큼 나머지 연산의 제수 범위를 늘려버리는 것이다. 100으로 나누면 절대로 충돌이 발생할 일이 없다.

해시 충돌 해결

물론 나누는 값을 단순히 키운다고 해서 해시 충돌 문제를 완전히 해결할 수는 없다.
하지만 해시 인덱스를 구하는 알고리즘을 적당히 조절하면 해시 충돌 확률을 낮출 수 있다는 것은 알 수 있다.

다른 관점에서 살펴보면, 해시 충돌이 일어났을 때 단순하게 같은 해시 인덱스의 값을 같은 인덱스에 함께 저장해버림으로써 해결할 수도 있다. 이런 방식을 체이닝(chaining)이라고 한다. 자세한 내용은 자료구조 카테고리의 “해시 테이블(2) - 충돌” 게시글을 참고하자.

해시 충돌이 난 경우
저장할 때는 배열 안의 배열에 데이터를 추가하고, 조회할 때 내부의 데이터를 하나씩 비교해보면 원하는 결과를 찾을 수 있다.

최악의 경우
모든 데이터가 9로 나눠떨어진다고 해보자. (9, 19, 29, 39, ….) 이런 최악의 경우에는 O(n) 성능을 보인다.

정리
해시 인덱스를 사용하는 방식은 최악의 경우 O(n)의 성능을 보인다. 하지만 확률적으로 보면 어느 정도 넓게 퍼지기 때문에 평균으로 보면 대부분 O(1)의 성능을 제공한다. 해시 충돌이 가끔 발생해도 내부에서 값을 몇 번만 비교하는 수준이기 때문에 대부분의 경우 매우 빠르게 값을 찾을 수 있다.

해시 인덱스 충돌 확률

해시 충돌은 가급적 발생하지 않도록 해야 한다. 앞에서 말한 것 처럼 입력하는 데이터의 수와 비교해서 배열
의 크기가 클 수록 충돌 확률은 낮아진다.

통계적으로 입력한 데이터의 수가 배열의 크기를 75% 넘지 않으면 해시 인덱스는 자주 충돌하지 않는다. 반대로 75%를 넘으면 자주 충돌하기 시작한다. 배열의 크기를 크게 만들면 해시 충돌은 줄어서 성능은 좋아지지만, 많은 메모리가 낭비된다. 반대로 배열의 크기를 너무 작게 만들면 해시가 자주 충돌해서 성능이 나빠진다. 상황에 따라 다르겠지만 보통 75%를 적절한 크기로 보고 기준으로 잡는 것이 효과적이다.

이 게시글에서 정리한 체이닝 방식 이외에도 해시 충돌을 해결하기 위한 여러가지 방법이 있다.

예를 들면, 자바 컬렉션에서는 자바 8이 도입된 이후로 HashMap은 내부 데이터 관리를 데이터가 적을 때는 linked list 로 하다가 데이터가 일정 수 이상 넘어가면 레드 블랙 트리로 전환하는 방식을 사용한다고 한다. 자바가 제공하는 해시에 관한 자세한 내용은 뒤 챕터에서 다룬다.

참고) 김영한의 실전 자바 - 중급 2편