14.HashSet

HashSet
: Set인터페이스를 구현한 가장 대표적인 컬렉션

* HashSet의 특징
1. 중복을 허용하지 않는다.
2. 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야한다.
3.add와 contain메소드의 시간복잡도는 O(1), next의 시간복잡도는 O(h/n)이다.
* O(h/n)의 이유는 엘리먼트에 비해 해시버킷의 수가 늘어나면 해시버킷으로 사용하는 배열의 대부분은 비어있게 되고, 엘리먼트가 담겨 있는 해시버킷을 찾기 위해 매번 비어있는 해시버킷을 방문해야하기 때문에 h 가 들어갔다.  또한 엘리먼트의 숫자가 늘어나면 해시버킷이 비어있을 가능성이 줄어들게 되고, O(1)에 근접하게 된다. 이런 의미에서 H/N 이라는 시간복잡도를 써 놓은 것 같다.
hashes 시간복잡도 참조블로그 :https://soft.plusblog.co.kr/74

* HashSet의 중복체크

import java.util.*;
class HashSetEx {
	public static void main(String[] args){
    	HashSet set = new HashSet();
        
        set.add("abc");
        set.add("abc");
        set.add(new Person("David",10));
        set.add(new Person("David",10));
        
        System.out.println(set);
        // 실행결과 [abc, David:10, David:10]
    }
}

class Person {
	String name;
    int age;
    
    Person(String name, int age) {
    	this.name = name;
        this.age = age;
    }
    public String toString(){
    	return name + ":" + age;
    }

}

위의 소스를 보면 인스턴스 변수의 값이 같은 두 객체는 hashset에서 중복체크시 서로 다른 것으로 인식되고 있다. 

HashSet의 add 메소드는 새로운 요소를 추가하기 전에 기본에 저장된 요소와 같은 것인지 판별하기 위해 추가하려는 요소의 

equals()와 hashCode()를 호출하기 때문에 

클래스 생성시 hash 비교를 감안하여 equals()와 hashCode()의 오버라이딩을 고려해봐야한다. 

 

* hashCode() 오버라이드

public int hashCode() {
	return Objects.hash(변수1, 변수2, 변수3...);
}

 

JDK1.8 이상의 버전에서는 java.util.Objects클래스의 hash()를 이용하여 작성하면 된다. 오버라이딩을 통해 작성된 hashCode()은 다음의 세 가지 조건을 충족시켜야한다. 

 

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

Person p = new Person("David",10);

int hc1 = p.hashCode();
int hc2 = p.hashCode(); // hc1과 hc2의 값은 항상 일치해야한다. 

p.age = 20;
int hc3 = p.hashCode(); // hc1나 hc2와의 값은 달라도 된다.

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

Person p1 = new Person("David", 10);
Person p2 = new Person("David", 10);

boolean b = p1.equals(p2); // b가 true라면

int hc1 = p1.hashCode();
int hc2 = p2.hashCode();   // hc1과 hc2의 값은 반드시 같아야한다.

3. equals메서드를 이용한 비교에서 결과값 false를 얻은 두 객체의 hashCode()를 호출해서 얻은 결과가 같은 경우가 있어도 괜찮다.

하지만 해싱을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int값을 반환하는 것이 좋다.

 

* HashSet의 메소드

https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/HashSet.html#method-summary

HashSet (Java SE 19 & JDK 19)