지난 시간에는 자바의 자료구조 컬렉션 중 배열리스트와 연결리스트에 대해 알아봤다.
결론은 데이터 구조의 앞을 빈번하게 수정할 때를 제외하고 배열리스트를 사용하자! 였다.
배열리스트는 index를 보유하여 순서가 있고 중복된 값을 저장할 수 있었다.
하지만 이와 정반대의 성격을 가진 컬렉션이 있었으니..
바로 세트다.
세트(Set)
세트는 순서가 없고, 중복된 값을 저장할 수 없다.
배열리스트와 달리, 값의 순서가 중요하지 않고 유일성을 보장해야할 때 사용할 수 있다.
거기에 웬만한 성능은 O(1)이라는 우수한 성능을 자랑하는데,
세트의 성능의 우수성을 이해하기 위해서는 해시(hash)에 대해 이해해야 한다.
해시
해시 알고리즘은 내부적으로 배열을 사용한다.
그리고 배열 사용의 기원은 데이터의 값과 인덱스를 일치하는 것에 있다.
1 → array[1]에 저장
123456 → array[123456]에 저장 이렇게 하면 원하는 데이터를 탐색할 때,
데이터의 인덱스 번호로 접근하면 되므로 O(1)의 성능을 자랑한다.
하지만 위 예시의 경우 엄청난 메모리 낭비 역시 자랑한다.
단순히 데이터 2개를 저장하는데, 배열의 크기는 123457이다(무려 123455가 낭비된다!).
메모리 낭비에 대한 문제를 해결하는 것이 바로 해시 알고리즘이다.
감자튀김 먹고싶다
해시 알고리즘
해시 알고리즘이란, 데이터를 나누기 계산하여 배열을 관리하는 방법이다.
해시 알고리즘에 등장하는 세 가지 개념을 이해해야 한다.
해시 함수
데이터(해시 코드)를 나누기 계산하여 나머지 값을 도출하는 함수.
해시 코드
데이터를 대표하는 값.
1 → 1.
A → 66.
해시 인덱스
해시 함수에 해시 코드를 나누기 계산하여 얻은 나머지 값.
===== 해시 함수 : 해시 코드 % 10 ======
해시 코드 → 해시 인덱스
1 → 1
2 → 2
33 → 3
555 → 5
데이터 값을 곧바로 배열의 해당 index에 저장하는 것이 아닌,
해시 함수를 통해 데이터 값(해시 코드)을 나누어 해시 인덱스를 도출하여
해시 인덱스에 값을 저장하는 것이 바로 해시 알고리즘인 것이다!
===== 해시 함수 : 해시 코드 % 10 ======
1 → 1
123456 → 6이전의 메모리 낭비가 엄청 심하던 예시도 데이터 개수대로 배열의 크기를 최적화할 수 있게 됐다.
문제점
아마 이야기를 들으면서 한가지 문제점이 떠올랐을 것이다.
1 → 1
11111 → 1아무리 해시 함수를 잘 짠다고 하더라도, 나머지 계산은 결국에
해시 인덱스가 겹치는 순간이 올 것이다.
이럴땐 어떻게 하면 좋다는 말인가?
현실에서 도망치지 말자.
극복할 수 없음을 인정하고, 배열 속 배열로 그냥 다 넣어버리는거다!
배열 속 배열
배열 속에 배열을 넣어서 관리하면,
해시 인덱스가 겹치는 문제도 해결할 수 있다.
1 → 1
11 → 1
111 → 1
1111 → 1
11111 → 1
array[1] = {1, 11, 111, 1111, 11111}물론 이 경우, 11111이라는 데이터를 찾기 위해
배열의 1번 index에 접근했다가 조회하는 과정에서 O(n)의 성능을 맛볼 수도 있다.
하지만 이런 경우는 매우 드물고, 해시 인덱스로 1차적으로 데이터를 분류했기 때문에
O(1)에 가까운 성능을 유지할 수 있다.
해시 인덱스 충돌
위 예시에서 볼 수 있듯, 해시 인덱스가 겹치면 성능이 저하될 수 있다.
해시 함수를 수정하고 배열의 크기를 늘려버리면 되지 않는가?
그렇게 되면 메모리 낭비로 이어진다는 것 쯤은 가뿐하게 알 수 있다.
배열의 크기가 너무 작아도 충돌이 자주 일어나고,
배열의 크기가 너무 크면 메모리 낭비로 이어지는 진퇴양난의 순간이다.
다행히도 이상적인 기준이 존재한다.
배열 크기의 75%를 데이터 수로 잡고 배열의 크기를 조절하면
성능도 유지하면서 메모리의 낭비도 최적화할 수 있다.
물론 데이터의 성질마다 다를 수 있으므로 잘 확인해서 판단하자.
숫자가 아닌건 어떡해?
데이터 타입은 boolean, 사용자 정의 등 숫자가 아닌 데이터 타입도 존재한다.
이 경우에는 아스키 코드를 통해 숫자로 변환해서 계산하여 전혀 문제가 되지 않는다.
하지만 잠깐.
참조값과 내부에 데이터를 보유한 인스턴스를 하나 떠올려 보자.
참조값이 다르지만 내부에 데이터가 같은,
동등성과 동일성의 차원에서 해시 인덱스는 어떻게 분류될 것인가?
IntelliJ hashCode(), eqauls()
자바는 기본적으로 사용자 정의 객체를 비교할 때,
Object 클래스의 hashCode() 메서드와 eqauls() 메서드를 사용한다.
위 메서드는 참조값을 바탕으로 동일성 비교를 수행한다.
하지만 IntelliJ에서 지원하는 hashCode() 메서드와 eqauls() 메서드 자동 생성 기능을 이용하여
Override한 hashCode() 메서드와 equals() 메서드는 객체 내부의 데이터를 비교한다.
따라서 해시 자료 구조는 반드시 hashCode()와 eqauls() 메서드를 오버라이딩 해야한다.
세트 종류
세트는 해시를 사용한 내부 구조를 통해서
중복을 허용하지 않고 순서가 무의미한 상황에 좋은 성능을 가지는 자료 구조로써 사용될 수 있다.
세트의 종류를 몇가지 살펴보자.
HashSet
실무에서 가장 많이 사용하는 세트 구현체.
중복을 허용하지 않고 순서를 보장하지 않는 세트의 종류.
LinkedHashSet
배열 속에 LinkedList를 사용하여 중복을 허용하지 않지만 순서는 보장하는 세트.
TreeSet
중복을 허용하지 않으면서 값을 정렬하는 기능을 가지는 세트.
순회를 활용하여 데이터 조회 시 O(log n)의 성능을 가진다.
값의 정렬과 순서의 필요성에 따라 HashSet 이외의 Set를 사용하면 된다.
마무리
배열리스트, 연결리스트와는 또다른 상황에서 사용할 수 있는 세트에 대해 알아봤다.
세트는 HashSet을 사용하고, 상황에 따라 LinkedHashSet과 TreeSet이 사용될 수 있다는 점을 기억하자.
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
@java.io.Serial
static final long serialVersionUID = -5024744406713321676L;
transient HashMap<E,Object> map;
...
}그런데 HashSet을 보면 내부에 HashMap이란 것을 사용한다.
HashMap이 뭐길래 내부에서 사용하는 걸까?
다음은 HashMap에 대해 알아보자.
