[JAVA] HashSet, TreeSet, 해싱

HashSet

• 중복된 요소를 저장하지 않는다.
• 내부적으로 HashMap을 이용해 만들어졌다.
• 저장순서를 유지하지 않으므로 중복을 제거하고 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야 한다.

공식문서

 

public class Person{
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String toString(){ // Overrides method in Object
        return name + " : " + age;
    }
}

 

import java.util.*;
public class Test {

    public static void main(String[] args) {
        Set hashSet = new HashSet();

        hashSet.add("Lionel");
        hashSet.add("Lionel");
        hashSet.add(new Person("Messi",35));
        hashSet.add(new Person("Messi",35));

        System.out.println(hashSet);
    }
    
}

 

실행 결과:

[Messi : 35, Messi : 35, Lionel]

 

이름과 나이가 같아도 다른 인스턴스를 참조하기 때문에 다르게 인식한다.

 

👉 HashSet의 add메서드는 새로운 요소를 추가하기 전에 equals()와 hashCode()를 호출하여 기존에 저장된 요소와 같은지 판별을 하기 때문에 위 예제에서는 equals()와 hashCode()를 아래와 같이 목적에 맞게 오버라이딩해야 한다.

 

public boolean equals(Object obj){
    if(obj instanceof Person){
        Person person = (Person) obj;
        return name.equals(person.name) && age == person.age;
    }
    return false;
}
public int hashCode(){
    // return (name+age).hashCode();
    return Objects.hash(name, age);
}

 

오버라이딩을 통해 작성된 hashCode()는 다음 세 가지 조건을 만족시켜야 한다.

 

1. 동일한 객체에 대해서 여러 번 hashCode()를 호출해도 동일한 int값을 리턴해야 한다. 하지만 실행할 때마다 동일한 int값을 반환할 필요는 없다.

 

👉 String클래스는 문자열의 내용으로 해시코드를 만들기 때문에 같은 문자열은 항상 동일한 해시코드를 반환하지만, Object 클래스는 객체의 주소로 해시코드를 만들기 대문에 실행할 때마다 해시코드 값이 달라질 수 있다.

 

2.  equals메서드를 이요한 비교에서 true를 얻은 두 객체에 대해 hashCode()를 호출해서 얻은 결과는 반드시 같아야 한다.

 

3. equals메서드를 이요한 비교에서 false를 얻은 두 객체에 대해 hashCode()를 호출해서 같은 값을 반환하는 경우가 있을 수 있지만, hashing을 사용하는 컬렉션의 성능 향상을 위해서는 다른 int값을 반환하는 것이 좋다.

 

👉 서로 다른 객체에 대해서 해시코드값이 중복되는 경우가 많아질수록 해싱을 사용하는 HashTable, HashMap과 같은 컬렉션의 검색속도가 떨어진다.

 

🔎 Hashing

해싱에서 사용하는 자료구조는 배열과 링크드 리스트의 조합으로 이루어져 있다.

출처: 구글

 

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그곳에 연결되어 있는 링크드 리스트에 저장하게 된다.

 

HashMap에 저장된 데이터를 조회하는 과정은 아래와 같다.

1. 검색하고자 하는 값을 키로 해시함수를 호출한다.

2. 해시함수의 계산결과 (HashCode)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다.

3. 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.

 

링크드 리스트는 검색에 불리한 자료구조이기 때문에 링크드 리스트의 크기가 커질수록 검색 속도가 떨어진다. 반면에 배열은 크기가 커져도 인덱스를 통해 주소값을 얻기 때문에 빠르게 원하는 값을 찾을 수 있다. 따라서 링크드 리스트에 최소한의 데이터만 저장되게 해시함수의 알고리즘을 구현해야 한다. 

TreeSet

• 이진 검색 트리 (binary search tree)라는 자료 구조의 형태로 데이터를 저장하는 컬렉션 클래스
• 이진 검색 트리의 성능을 향상시킨 'Red-Black tree'로 구현되어 있디.
• 중복된 데이터를 저장하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지 않는다.
• 저장위치를 찾아서 저장해야하고, 삭제하는 경우 트리의 일부를 재구성해야 하므로 LinkedList보다 데이터의 추가/삭제 시작은 더 걸린다.
• 배열이나 LinkedList에 비해 검색과 정렬 기능이 더 뛰어나다.

HashSet vs TreeSet 로또 번호 생성:

 

import java.util.*;

public class Test {

    public static void main(String[] args) {
        Set hashSet = new HashSet();
        Set treeSet = new TreeSet();
        for (int i = 0; hashSet.size() < 6; i++) {
            int num = (int)(Math.random()*45) + 1;
            hashSet.add(num);
            treeSet.add(num);
        }
        List hashList = new LinkedList(hashSet);
        List treeList = new LinkedList(treeSet);
        System.out.println(hashList); // [16, 1, 21, 6, 44, 30]
        System.out.println(treeList); // [1, 6, 16, 21, 30, 44] 

        Collections.sort(hashList);
        System.out.println(hashList); // [1, 6, 16, 21, 30, 44]
    }

}

 

 

---

참고: 자바의 정석 - 남궁성

 

🤞자바의 정석 스터디  p631-668🤞