Set - HashSet 이론과 구현

📌 Set<E> 컬렉션의 특징

- 집합의 개념으로 인덱스 정보를 포함하고 있지 않다.

- 중복저장 불가 -> 인덱스 정보가 없기 때문에, 중복된 원소 중 특정 위치 값을 거낼 방법이 없다.

 

 

 

---

📌 Set<E>  주요 메서드

구분	리턴타입	메서드 이름	기능
데이터 추가	boolean	add(E element)	매개변수로 입력된 원소를 리스트에 추가
	boolean	addAll(Collection <? Extends E> c	매개변수로 입력된 컬렉션 전체를 추가
데이터 삭제	boolean	remove<Object o)	원소 중 매개변수입력과 동일한 객체 삭제
	void	clear()	전체 원소 삭제
데이터 정보추출	boolean	isEmpty()	Set 객체가 비워져있는지 여부 리턴
	boolean	contains(Object o)	매개변수로 입력된 원소가 있는지 여부를 리턴
	int	size()	리스트 객체 내에 포함된 원소의 개수
	iterator<E>	iterator()	Set 객체내의 데이터를 연속하려 꺼내는 Iterator 객체 리턴
Set 객체 배열 반환	Object[]	toArray()	리스트를 Object 배열로 변환
	T[]	toArray(T[] t)	입력매개변수로 전달한 타입의 배열로 변환

 

 

 

---

📌 HashSet<E>

- Set<E> 인터페이스를 구현한 클래스

- 수집한 원소를 집합의 형태로 관리하여 저장용량(capacity)을 동적관리 (capacity default : 16)

- 입력의 순서와 출력의 순서는 동일하지 않을 수 있음

 

예시코드)

public class HashSetMethod {
    public static void main(String[] args) {

        Set<String> hSet1 = new HashSet<>();

        //#1. add(E element)
        hSet1.add("가");
        hSet1.add("나");
        hSet1.add("가");
        System.out.println(hSet1.toString()); //[가, 나]

        //#2. addAll(다른 set 객체)
        Set<String> hSet2 = new HashSet<>();
        hSet2.add("나");
        hSet2.add("다");
        hSet2.addAll(hSet1);
        System.out.println(hSet2.toString()); //[가, 다, 나] 입력 순서대로 출력되진 않음

        //#3. remove(Object o)
        hSet2.remove("나");
        System.out.println(hSet2.toString());

        //#4. clear
        hSet2.clear();
        System.out.println(hSet2.toString());

        //#5. isEmpty
        System.out.println(hSet2.isEmpty()); //true
        
        //#6. contains (Object o)
        Set<String> hSet3 = new HashSet<>();
        hSet3.add("가");
        hSet3.add("나");
        hSet3.add("다");
        System.out.println(hSet3.contains("나")); //true
        System.out.println(hSet3.contains("라")); //false

        //#7. size
        System.out.println(hSet3.size()); //3

        //#8. iterator
        Iterator<String> iterator = hSet3.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //#9 toArray : 배열로 바꾸기
        Object[] objArray = hSet3.toArray();
        System.out.println(Arrays.toString(objArray));

        //#10. toArray(T[] t)
        String[] strArray1 = hSet3.toArray(new String[0]); //컴파일러가 알아서 저장공간을 늘려준다.
        System.out.println(Arrays.toString(strArray1)); //[가, 다, 나]

        String[] strArray2 = hSet3.toArray(new String[5]);
        System.out.println(Arrays.toString(strArray2)); //[가, 다, 나, null, null]
    }
}

 

 

 

---

 

📌 Set의 중복확인 매커니즘

 

 

#case 1) hashcode, equals 메서드 오버라이딩 X

- Object의 equals()은 ==와 동일한 연산 (저장 번지 비교)

class A {
    int data;
    public A(int data) {
        this.data = data;
    }
}

public class HashSetMachanism {
    public static void main(String[] args) {

        //#1. 어떤 것도 오버라이딩 하지 않은 경우
        Set<A> hashSet1 = new HashSet<>();

        A a1 = new A(3);
        A a2 = new A(3);
        System.out.println(a1 == a2); //false
        System.out.println(a1.equals(a2)); //false
        System.out.println(a1.hashCode() + " " + a2.hashCode()); //990368553 1096979270

        hashSet1.add(a1);
        hashSet1.add(a2);
        System.out.println(hashSet1.size()); //2 : 다른객체로 판단, 동일하지 않음.

    }
}

 

 

#case 2) equals() 오버라이딩

- equals를 오버라이딩하여 값이 같으면, true를 반환하도록 설정

- 하지만 hashcode값이 다르기 때문에, 여전히 다른 객체로 판단

class B {
    int data;
    public B(int data){
        this.data = data;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj instanceof B){
            this.data = ((B)obj).data;
            return true;
        }
        return false;
    }
}

public class HashSetMachanism {
    public static void main(String[] args) {
    
        //#2. equals() 오버라이딩
        Set<B> hashSet2 = new HashSet<>();
        B b1 = new B(3);
        B b2 = new B(3);
        System.out.println(b1 == b2); //false
        System.out.println(b1.equals(b2)); //true
        System.out.println(b1.hashCode() + " " + b2.hashCode()); //2129789493 668386784

        hashSet2.add(b1);
        hashSet2.add(b2);
        System.out.println(hashSet2.size()); //2

    }
}

 

 

#case 3) equals(), hashcode 오버라이딩

- equals(), hashcode를 매개변수 값이 같으면 각각 true, 같은 hash값을 반환하도록 설정.

- 같은 객체로 인식하여 Set 에 값이 하나만 들어간 것을 알 수 있음.

class C {
    int data;
    public C(int data){
        this.data = data;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj instanceof C){
            this.data = ((C)obj).data;
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(data); //이렇게 하면 data를 기반으로 hashcode를 만든다. Object의 hashcode는 위치를 기반으로 만듦.
    }
}


public class HashSetMachanism {
    public static void main(String[] args) {

        //#3. equals(), hashCode() 오버라이딩
        Set<C> hashSet3 = new HashSet<>();
        C c1 = new C(3);
        C c2 = new C(3);
        System.out.println(c1 == c2); //false
        System.out.println(c1.equals(c2)); //true
        System.out.println(c1.hashCode() + " " + c2.hashCode()); //34 34

        hashSet3.add(c1);
        hashSet3.add(c2);
        System.out.println(hashSet3.size()); //1

    }
}

 

 

---

 

💡 HashSet 구현

- set을 다음과 같이 구현하였다.

import java.util.HashMap;
import java.util.Iterator;

public class MyHashSet<E> {
    private final HashMap<E, Object> map;
    //HashMap 값으로 새용할 더미 객체
    private static final Object DUMMY_VALUE = new Object();

    public MyHashSet(){
        this.map = new HashMap<>();
    }

    public boolean add(E element) {
        //이미 존재하면 false반환, 새로 추가되면 true 반환
        return map.put(element, DUMMY_VALUE) == null;
    }

    public boolean remove(E element) {
        return map.remove(element) != null;
    }

    public boolean contains(E element) {
        return map.containsKey(element);
    }

    public int size() {
        return map.size();
    }

    public void clear(){
        map.clear();
    }

    public boolean isEmpty(){
        return map.isEmpty();
    }

    @Override
    public String toString() {
        return map.keySet().toString();
    }

    //Iterator구현
    public Iterator<E> iterator() {
        return new CustomIterator();
    }

    private class CustomIterator implements Iterator<E> {
        private final Iterator<E> iterator;
        public CustomIterator(){
            this.iterator = map.keySet().iterator();
        }

        @Override
        public boolean hasNext() {
            return iterator().hasNext();
        }

        @Override
        public E next() {
            return iterator.next();
        }
    }

}

 

---

 

 

필드, 생성자

 

- Key 값이 중복되지 않는 HashMap을 통해 구현한다. (실제 HashSet도 HashMap으로 구현)

- Value값으로 DUMMY값을 상수로 생성하여, 데이터 추가시 사용

 private final HashMap<E, Object> map;
    private static final Object DUMMY_VALUE = new Object(); // HashMap의 값으로 사용할 더미 객체

    public MyHashSet() {
        this.map = new HashMap<>();
    }

 

 

---

 

 

데이터 추가 (add)

 

- map에서 값을 저장할 시, key가 존재하면 해당 값을 업데이트하고, 기존의 값을 반환.

- 새로 저장 시 null을 반환하기 때문에 map.put(element, DUMMY_VALUE) == null은 새로 추가된 항목에 대해 true를 반환, 이미 존재할 때 false를 반환한다.

public boolean add(E element) {
    // 이미 존재하면 false 반환, 새로 추가되면 true 반환
    return map.put(element, DUMMY_VALUE) == null;
}

 

 

---

 

요소 제거 (remove)

 

- element가 map에 존재할 시, 해당 키-값 쌍이 삭제되고 그 키에 대응하는 값이 반환.

- 만약 element가 없으면 null을 반환한다.

- 이를 이용하여 삭제가 성공하면 true를 반환, 실패할 시 false를 반환한다.

public boolean remove(E element) {
    return map.remove(element) != null;
}

 

 

---

 

요소 포함여부 확인 (contains)

 

- HashMap에서 key 가 존재하는지 확인한다.

public boolean contains(E element) {
    return map.containsKey(element);
}

 

 

---

 

집합의 크기 반환 (size)

 

- HashMap의 크기를 반환한다.

public int size() {
    return map.size();
}

 

 

---

 

집합 비우기 (clear)

 

- HashMap의 모든 요소를 제거한다.

public void clear(){
    map.clear();
}

 

 

---

 

집합이 비어있는지 확인(isEmpty)

 

- HashMap이 비어있는지 확인하여 boolean 타입으로 반환한다.

public boolean isEmpty(){
    return map.isEmpty();
}

 

 

---

전체 요소 출력 (toString)

 

- HashMap의 KeySet()을 문자열로 변환하여 집합 요소를 출력한다.

@Override
public String toString() {
    return map.keySet().toString();
}

 

 

---

 

이터레이터 (Iterator)

 

- HashMap의 KeySet()을 순회하는 Iterator를 선언하여, Iterator인터페이스 구현

public Iterator<E> iterator() {
    return new CustomIterator();
}

private class CustomIterator implements Iterator<E> {
    private final Iterator<E> iterator;
    public CustomIterator(){
        this.iterator = map.keySet().iterator();
    }

    @Override
    public boolean hasNext() {
        return iterator().hasNext();
    }

    @Override
    public E next() {
        return iterator.next();
    }
}