Collection Framework 완전 정복 5탄 - Set인터페이스 (HashSet, LinkedHashSet)

Set 인터페이스

일반적으로 Set을 구현하는 클래스들은 다음과 같은 공통점을 가집니다.

1. 중복되는 요소를 허용하지 않는다
2. 저장 순서를 유지하지 않는다(LinkedHashSet은 예외)

구현체 각각에 대해 상세히 알아보기 전, 우선 요약해서 간단히 설명드리겠습니다.

 

HashSet은 가장 기본적인 Set컬렉션의 클래스로, 중복을 허용하지 않고 입력 순서를 보장하지 않습니다(== 인덱스로 접근 불가)

LinkedHashSet은 중복은 허용하지 않으면서 순서를 보장하는 자료구조입니다.

TreeSet은 HashSet과 마찬가지로 입력 순서를 보장하지 않고, 중복되는 데이터를 넣지 못합니다. 다만 특별한점은 가중치에 따른 순서대로 정렬된다는 것입니다. 즉 중복 되지 않으면서, 특정 규칙에 의해 정렬된 집합을 쓰고 싶을때 사용합니다.

 

Set인터페이스에 선언할 메서드들을 살펴본 후 각각에 대해 좀더 상세히 다루어보겠습니다.

---

Hash Set

우선 HashSet을 이해하려면 Hash에 대한 이해가 필요합니다! 혹시 Hash와 Hash Function 및 Collison에 대해 알고 싶으시다면 밑의 글을 참고해주세요!

https://wookjongbackend.tistory.com/15

 

위의 글은 좀 길수도 있기에 이 포스팅에서도 한번 요약해서 다루어보겠습니다!

 

Hash란 임의의 길이를 갖는 데이터를 고정된 길이의 데이터를 변환(매핑)하는 것입니다.

위의 그림과 같이 key를 고정된 길이의 hash 값으로 변환하는 함수를 Hash Function이라고 합니다. 위와 같은 과정을 보통 해싱(Hashing)한다 라고 표현합니다.

 

그렇다면 왜 굳이 복잡하게 이러한 해시함수를 사용할까요???

 

앞선 완전 정복 시리즈에서 살펴보았던 ArrayList, LinkedList등 수 많은 자료구조들은 특정 값(인덱스x)이 있는지 찾아내기 위해서 어떻게 해야했었나요?

배열 혹은 노드들을 순회하면서 특정 값이 있는지 찾아냈어야 합니다.

 

하지만 해시 함수는 위와 같이 순회를 할 필요가 없습니다. 왜냐하면 동일한 key에 대해서는 동일한 hash를 가지기 때문입니다.

즉 특정 key에 대한 hash는 변하지 않기에, 이러한 hash값을 배열의 index로 활용하는 것입니다!

 

Hash + Set 에서 Set은 중복 원소를 허용하지 않는다고 설명드렸죠?

이 말을 또 다르게 생각해보면 원소를 추가할때 마다 해당 원소가 중복되는 원소인지 검사를 해야할텐데, 이때 모든 요소를 순회하면서 중복 여부를 판단한다면 매우 비효율적입니다.

 

그렇기에 고안한 방법이 hash함수(ex: hashCode() 메서드)를 통해 특정 값에 대한 고유 Hash값을 얻고 그 값에 대응하는 index를 찾아서 해당 인덱스에 있는 요소만 검사하면 되는것입니다!

위와 같은 원리들이 HashSet의 기본 개념입니다.

 

그렇다면 객체의 hash값은 어떻게 얻을까요????

이 경우에는 자바에서 제공하는 hashCode()라는 메서드를 활용하면 됩니다.

위 메서드는 객체의 메모리 주소값을 이용하여 해시 알고리즘에 의해 생성된 고유의 정수값을 반환합니다. 즉 객체가 같은 메모리 주소를 가리키고 있다면 같은 값을 얻게 되겠죠?

 

Java에서 모든 객체는 Object 클래스를 상속받으며, Object 클래스에는 hashCode()라는 메서드가 정의되어 있어 모든 객체가 이 메서드를 가지고 있습니다. 이러한 hashCode()는 기본적으로 객체의 메모리 주소를 기반으로 한 고유한 정수값을 반환합니다. 따라서 기본적으로는 new 연산자를 통해 생성된 두 객체의 hashCode() 값은 다릅니다. 즉 객체의 내용이 같더라도, 이 두 객체는 서로 다른 메모리 주소에 할당 되므로 서로 다른 해시 코드를 가집니다.

 

하지만 저희가 일반적으로 쓰는 String, Integer, Double 등의 자료형은 hashCode() 메서드를 오버라이드하여 객체의 내용을 기반으로한 해시코드를 반환하도록 하고 있습니다. 이 경우에는 내용이 같다면 해시코드 또한 같습니다.

 

String s1 = new String("Hello");
String s2 = new String("Hello");

System.out.println(s1.hashCode());  // 출력: 69609650
System.out.println(s2.hashCode());  // 출력: 69609650

위와 같이 String 클래스의 경우, 같은 문자열을 가지는 두 String 객체는 서로 다른 메모리 주소에 있지만, hashCode() 결과값은 같습니다. 이는 String 클래스에서 hashCode() 메서드가 문자열의 내용을 기반으로 해시코드를 계산하기 때문입니다.

 

그렇다면 사용자 정의 클래스의 경우엔 어떻게 해야할까요?

사용자가 정의한 클래스의 인스턴스가 같은 내용을 가지더라도, 그 클래스에서 hashCode() 메서드를 재정의 하지 않으면 각 인스턴스는 서로 다른 해시값을 가집니다. 이는 hashCode() 메서드가 기본적으로 메모리 주소를 기반으로 해시코드를 계산하기 때문입니다.

 

따라서 사용자 정의 클래스내에 hashCode() 메서드를 재정의하면, 같은 내용의 인스턴스는 같은 해시코드를 가집니다. 이렇게 하면 HashSet과 같은 클래스에서 사용자 정의 클래스를 원소로 사용할때, 원소의 중복성을 내용 기반으로 판단할 수 있습니다.

 

class MyClass {
    private int x;

    MyClass(int x) {
        this.x = x;
    }

    @Override
    public int hashCode() {
        return x;
    }
}

MyClass obj1 = new MyClass(10);
MyClass obj2 = new MyClass(10);

System.out.println(obj1.hashCode());  // 출력: 10
System.out.println(obj2.hashCode());  // 출력: 10

 

HashSet 연산은 일반적으로 O(1)의 시간복잡도를 가지게 됩니다.

이는 HashSet이 내부적으로 HashMap(이후 포스팅에서 좀더 상세히 다루어 볼 내용!)을 사용하고, 각각의 요소들이 해시 함수를 통해 결정되는 버킷에 저장되기 때문입니다. 이 때문에 특정 요소를 찾거나 추가하거나 삭제하는데 상수시간이 걸립니다.

 

하지만 해시 충돌이 발생한다면 어떨까요?

만약 체이닝 방법을 사용한다면, 최악의 경우 O(n)의 시간복잡도를 가질것입니다. 즉 모든 요소가 동일한 버킷에 해시되어, 버킷을 탐색하는데 n개의 요소를 모두 확인해야 하는 경우겠죠??

---

LinkedHashSet

앞서 다룬 HashSet과 LinkedHashSet은 공통적으로 중복된 원소를 허용하지 않는 다는 공통점이 있습니다.

하지만 LinkedHashSet은 HashSet과 다르게 입력 순서를 유지하는 클래스입니다.

 

HashSet에서는 일반적으로 데이터를 해싱한 값을 배열의 인덱스로 활용하여 해당 인덱스에 데이터를 저장합니다.

이는 데이터에 대해 빠르게 탐색할 수 있다는 장점이 있지만, 데이터 해싱된 값에 따라 저장되는 위치가 달라지기 때문에 순서가 보장되지않습니다!

 

위와 같은 단점을 보완하기 위해 HashSet과 동일하게 table에 저장을 하되, 순서를 보장할 수 있도록 LinkedList의 기능을 추가해 준것입니다.

이를 위해 이전 노드와 다음 노드를 가리키는 변수를 두게 됩니다.

---

참고

지금까지 Set 인터페이스, HashSet + LinkedHashSet 에 대해 다루어봤습니다!! 이해하시는데 도움이 되었으면 좋겠습니다

틀린 내용에 대한 지적은 언제나 환영합니다 ^^

 

https://inpa.tistory.com/entry/JCF-🧱-Collections-Framework-종류-총정리#priorityqueue_클래스

https://st-lab.tistory.com/238

https://theheydaze.tistory.com/609

https://st-lab.tistory.com/258

---