[Java] 자바의 정석 독서 #23 - HashSet과 HashMap

평일에 책을 읽으면 5일 중에서 자바 2 자바스크립트 2 C 계열 1로 가져가려고 했는데, 자바는 재밌어. 자바 3 자바스크립트 2 C 계열 0으로 가져가버렸다ㄷㄷ

 

https://dev-dx2d2y-log.tistory.com/127

[CS] 자바의정석 독서 #18 - 컬렉션은 무엇인가?

https://dev-dx2d2y-log.tistory.com/128

[CS] 자바의정석 독서 #19 - ArrayList, Vector, LinkedList

https://dev-dx2d2y-log.tistory.com/130

[CS] 자바의 정석 독서 #20 - 스택과 큐 in Java

https://dev-dx2d2y-log.tistory.com/131

[CS] 자바의 정석 독서 #21 - 이터레이터

https://dev-dx2d2y-log.tistory.com/141

[CS] 자바의 정석 독서 #22 - Arrays로 배열 다루기

암튼 지금까지는 컬렉션 프레임웍에 대해서 다뤘고 컬렉션의 간단한 소개와 컬렉션의 상위에 있는 이터레이터, 그리고 하위에 있는 클래스 중에 List에 대해서 다뤘다. 이번에는 나머지 하위클래스 중 하나인 Set에 대해서 다뤄볼 예정이다.

 

저번에 스택과 큐를 할 때 했던 것처럼, Set 요소들도 특정 기준만 만족시키면 Set의 하위클래스로 들어간다. Set의 특정 기준은 '중복 요소의 추가 방지'이다. 이 기준만 만족하면 내부적으로 순서가 있든, 순서 없이 무작위적으로 요소가 저장되든 아무 상관없다.

---

HashSet

HashSet은 Set의 구현체 중 가장 대표적인 컬렉션이다. Set을 사용하고 싶을 때 주로 사용한다. HashSet은 해싱함수를 통해 얻은 해시값으로 해당 요소가 이미 Set 내부에 존재하는지 여부를 판단하기 때문에 HashSet이라는 이름이 붙었다.

 

다만 HashSet은 저장순서를 유지하지 않으므로 유지하려면 LinkedHashSet을 이용해야한다. 이름에서 알 수 있듯이 LinkedArrayList와 비슷하게 순서를 유지한다.

 

//저장된 객체의 개수 반환
public int size()

//Set이 비었는지 확인
public boolean isEmpty()

//해당 요소가 Set에 있는지 확인
public boolean contains(Object o)

//요소추가
public boolean add(E e)

//요소제거
public boolean remove(Object o)

//복사
public Object clone()

//여러 스레드가 동시 작업수행하게 함
public Spliterator<E> spliterator()

//객체배열의 형태로 반환
public Object[] toArray()

//주어진 객체 배열에 저장된 객체를 담는다
public <T> T[] toArray(T[] a)

이정도 메서드가 있다. 거의 컬렉션과 Set에서 상속받은게 대부분이다.

여기 적힌 메서드 이외에 추가로 컬렉션, 이터레이터에서 상속받은 iterator() 메서드가 포함되어있다.

생성자는 아무것도 없거나 (Set 형성), 컬렉션을 주거나 (컬렉션을 포함하는 Set 객체 생성), int 값을 주거나 (초기용량 설정), int와 floate를 넘겨주거나 (int는 초기용량, float는 저장공간의 float만큼 차면 용량이 두 배로 늘어난다. 기본값 0.75)

 

Integer[] arr = {1,2,3,4,5,6,7,7,7,8,9,1,2};
HashSet<Integer> sets = new HashSet<>(Arrays.asList(arr));

System.out.println(sets);		//[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

과연 중복을 허용하지 않는다.

 

Integer[] arr = {103, 54,33, 55, 64, 46,33,101};
HashSet<Integer> sets = new HashSet<>(Arrays.asList(arr));

System.out.println(sets);		//[64, 33, 101, 54, 103, 55, 46]

중복도 허용하지 않고, 순서도 없기 때문에 넣은 순서와는 아무 상관없이 출력된다.

만약 HashSet을 출력했는데 요소들이 정렬되어서 출력됐다면 우연이다.

 

Integer[] arr = {103, 54,33, 55, 64, 46,33,101};
LinkedHashSet<Integer> sets = new LinkedHashSet<>(Arrays.asList(arr));

System.out.println(sets);		//[103, 54, 33, 55, 64, 46, 101]

만약 넣은 순서를 유지하고 싶다면 LinkedHashSet을 사용하면 된다.

 

Integer[] arr = {103, 54,33, 55, 64, 46,33,101};
LinkedHashSet<Integer> sets = new LinkedHashSet<>(Arrays.asList(arr));
Collections.sort(sets);		//여기서 에러

System.out.println(sets);

Integer[] arr = {103, 54,33, 55, 64, 46,33,101};
LinkedHashSet<Integer> sets = new LinkedHashSet<>(Arrays.asList(arr));

LinkedList<Integer> lists = new LinkedList<>(sets);
Collections.sort(lists);
sets = new LinkedHashSet<>(lists);

System.out.println(sets);		//[33, 46, 54, 55, 64, 101, 103]

다만 아무리 순서가 있더라도 Set의 구현체들은 정렬메서드는 제공하지 않는다. 만약 정렬메서드를 사용하고 싶다면 List로 변환한 후에 Collections 클래스에 정의된 List의 배열을 사용하면 된다. Collections는 Collection이 아니다!

저번에 Comparator와 Comparable에 대해서 다뤘는데 Collections의 정렬메서드에서 동일하게 적용할 수 있다. 자세한 것은 11장 끝부분에서 다룰 예정

---

원시값인 경우에는 단순 값비교를 통해 중복된 요소가 있는지 확인할 수 있으나, 참조변수, 객체인 경우에는 어떻게 중복된 요소를 걸러낼까?

 

public class Main {
    public static void main(String[] args) {
        MyNumber m1 = new MyNumber(1);
        MyNumber m2 = new MyNumber(1);

        Set<MyNumber> s = new HashSet<>(Arrays.asList(m1, m2));
        System.out.println(s);		//[ 1, 1 ]
    }
}

class MyNumber {
    int number;

    public MyNumber(int number) {
        this.number = number;
    }

    public String toString() {
        return String.valueOf(number);
    }
}

이전에도 다뤘지만 객체는 단순히 == 연산자 또는 equals() 연산자를 사용하면 힙메모리의 주소값을 비교하기 때문에 객체의 상태가 동일하더라도 다른 객체라고 판단한다.

 

앞서 HashSet은 해시코드를 기반으로 값이 동일한지를 구분한다고했는데, 그렇기 때문에 HashCode에 값을 추가하려면 equals()와 hashCode() 메서드를 호출하여 값이 중복되는지 검사한다.

 

https://dev-dx2d2y-log.tistory.com/122

[CS] 자바의 정석 독서 #15 - java.lang 패키지와 Object 클래스

저번에 Object 클래스에 대해서 다룰 때 hashCode()와 equals()에 대해 다룬 것을 참고하면 좋다.

 

HashSet은 해시코드를 기반으로 값의 중복을 검사하므로 먼저 hashCode() 메서드를 통해 같은 해시코드값이 있는지 검사한다. 만약 해시코드 중복이 없다면 HashSet에 요소를 추가.

해시코드가 동일한게 있을 때에는 equals() 메서드를 호출하여 값이 같은지 여부를 검사한다. 만약 equals() 메서드의 실행결과가 true일 경우에는 추가하지 않고, false일 경우에는 Set에 추가하는 방식으로 동작한다. 왜냐하면 다른 객체더라도 해시 값이 같은, 즉 해시충돌의 경우가 가능하기 때문이다.

 

그렇기 때문에 커스텀 객체를 만들 때에는 hashCode()와 equals() 메서드를 모두 구현해두는 것이 좋다.

 

public class Main {
    public static void main(String[] args) {
        MyNumber m1 = new MyNumber(1);
        MyNumber m2 = new MyNumber(1);

        Set<MyNumber> s = new HashSet<>(Arrays.asList(m1, m2));
        System.out.println(s);		//[1]
    }
}

class MyNumber {
    Integer number;

    public MyNumber(int number) {
        this.number = number;
    }

    @Override
    public String toString() {
        return String.valueOf(number);
    }

    @Override
    public boolean equals(Object o) {
        if (o instanceof  MyNumber) {
            return this.number.equals(((MyNumber) o).number);
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return number.hashCode();
    }
}

equals와 hashCode를 재정의하면 개발자의 입맛에 맞게 값이 같은지 여부를 조정할 수 있다.

 

@Override
public int hashCode() {
    return Objects.hash(number);
}

JDK8부터는 java.util.Objects 클래스의 hash() 함수를 통하여 해시코드를 만들 수 있다. 인자로 인스턴스 변수 여러 개를 전달할 수 있다는 것을 제외하면 Object 클래스의 hashCode() 함수와 크게 다를 것은 없다.

 

암튼 이렇게 hashCode()를 재정의하면 반드시 세 가지 요건을 지켜야한다.

 

1. 동일한 객체에서 여러 번 hashCode() 메서드를 호출시킬 때 값이 모두 같아야한다. 다만 몇 번을 실행하든 언제나 같은 해시값을 반환할 필요는 없다. 그냥 실행 중에서만 동일하게 반환되기만하면 된다.

 

2. equals() 메서드의 실행결과가 true인 두 객체는 반드시 같은 hashCode() 메서드의 반환값이 같아야한다.

 

3. equals() 메서드의 실행결과가 false인 두 객체는 hashCode() 호출에 대해 같은 반환값을 가져도 상관없으나 (애초에 해시코드로 나올 수 있는 값이 저장가능한 메모리 수보다 적다) 해싱을 사용하는 컬렉션 (HashSet과 같은)의 성능을 위해서 다르게 하는 것이 좋다.

- hashCode()를 통해 얻어지는 값이 중복되는 경우가 많아질 수록 HashMap, HashSet과 같은 해싱함수를 이용한 컬렉션의 성능이 떨어진다. hashCode() 값이 같다면 equals()까지 호출해야 중복여부를 제대로 조사할 수 있기 때문에 호출할 메서드의 수가 많아지기 때문이다.

 

앞서 설명했듯이 해싱함수를 통해 값의 중복여부를 조사하는 컬렉션들은 hashCode()를 통해 해시코드를 조사한 후에 equals() 메서드를 호출한다. 따라서 equals()가 true라면 반드시 두 객체의 해시코드는 같아야한다. 해시코드가 다르면 애초에 equals() 메서드도 호출되지도 않고 중복되지 않는다고 판단하기 때문이다.

반대로 해시코드가 같다고해서 equals() 메서드가 true일 필요는 없다.

 

그래서 원칙상으로는 hashCode()를 재정의하면 equals() 메서드도 재정의하는 것이 원칙이다.

---

HashMap과 Hashtable

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    @java.io.Serial
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    private static final Object PRESENT = new Object();

	public HashSet() {
        map = new HashMap<>();
    }
}

HashSet의 내부를 살펴보면 내부적으로는 HashMap을 사용하고 있다.

Map의 구현체를 사용하려할 때 가장 기본적으로 사용되는 구현체이다.

key-value 형태의 자료구조이기 때문에 RDBMS를 사용하지 않은 예제에서 데이터를 저장하는 곳으로 사용되기도 한다.

 

https://dev-dx2d2y-log.tistory.com/127

HashMap은 전반적인 컬렉션에 대해 공부할 때 다룬 Map의 특징을 그대로가진다. key-value 형태로 이루어진 entry로 데이터를 저장한다. 앞에 Hash가 붙었으므로 해싱을 사용하는데, 그렇기 때문에 많은 양의 데이터를 검색하는데 성능이 좋다.

 

public class HashMap<K, V> extends AbstractMap<K, V>{
	transient Node<K, V>[] table;
    
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;

            return o instanceof Map.Entry<?, ?> e
                    && Objects.equals(key, e.getKey())
                    && Objects.equals(value, e.getValue());
        }
    }
}

HashMap은 Map 인터페이스의 내부 인터페이스인 Entry의 구현체로 Node를 사용한다.

즉, key-value 형태의 한 개의 entry를 Node 클래스의 형태로 저장한다. 즉, HashMap 내부에서는 Key와 value를 담은 entry가 하나의 노드.

 

노드의 key와 value는 Object 타입을 사용하기 때문에 어느 객체든 HashMap의 key와 value로 저장될 수 있다. 제너릭을 사용하여 처음에 key와 value 타입만 잘 지정해주기만 된다. 제너릭은 뒤에 나올 예정. 그렇기 때문에 value로 HashMap을 전해줄 수도 있다.

 

HashMap의 key는 반드시 유일해야한다. key를 가지고 HashMap 내부에서 값을 찾아야하기 때문에 그렇다.

만약 중복된 key를 가지고 HashMap에 저장하면 가장 마지막으로 저장한 객체가 덮어쓰기되게 된다.

---

추가로, 위의 코드에서 알 수 있듯이 HashMap은 내부적으로 노드의 배열을 사용하는데, key 값을 해싱함수를 넣어 나온 결과로 배열의 인덱스를 결정한다. 즉, 기존 배열처럼 앞에서부터 하나하나 살펴보는게 아니라, key 값과 해싱함수 식만 있다면 그 노드가 저장된 위치를 바로 알 수 있다. 그리고 해싱함수 식은 모든 HashMap들이 공유하고.

---

//HashMap의 크기 반환
//후자는 HashMap의 저장된 모든 값을 컬렉션의 형태로 변환
public int size()
public Collection values()

//HashMap이 비었는지 확인
public boolean isEmpty()

//key를 통해 value를 가져옴
//못찾으면 null 반환
public V get(Object key)

//key를 통해 value를 가져옴
//못찾으면 매개변수를 통해 전해진 객체 반환
public V getOrDefault(Object key, V defaultValue)

//key가 HashMap에 포함되어있는지 반환
public boolean containsKey(Object key)

//key-value 추가
//전자는 key와 value를 추가
//후자는 Map에 저장된 요소들을 HashMap에 추가
public V put(K key, V value)
public void putAll(Map<? extends K, ? extends V> m)
public V putIfAbsent(K key, V value)

//key를 통해 요소 제거
public V remove(Object key)

//key를 통해 접근한 값의 value 교체
//후자를 사용하면 매개변수로 주어진 value와 지정된 key의 value가 같아야만 교체
public V replace(K key, V value)
public boolean replace(K key, V oldValue, V newValue)

//비우기
public void clear()

//value값이 HashMap에 있는지 확인
public boolean containsValue(Object value)

//모든 key를 Set으로 반환
public Set<K> keySet()

//복제
public Object clone()

HashMap의 메서드는 대략 이렇다.

 

기본적인 메서드는 Map의 메서드와 비슷하다.

HashMap의 상속트리에는 Map와 HashMap 사이에 AbstractMap이 있기 때문에 여기서도 메서드가 몇 개 추가되었다.

---

이렇게 HashSet과 HashMap에 대해서 간단히 알아봤다.

HashMap은 해싱함수를 이용하여 key-value 형태로 값을 저장하는 대표적인 Map 인터페이스의 구현체이다.

HashSet은 해싱함수를 통하여 중복을 허용하지 않고 요소들을 저장하는 대표적인 Set 인터페이스의 구현체이다.

 

    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    public boolean isEmpty() {
        return map.isEmpty();
    }

HashSet은 내부적으로 HashMap을 사용하는데, 그렇기 때문에 HashSet의 메서드들은 HashMap의 메서드와 기능이 겹치는 경우 HashMap의 메서드를 호출하는 편이 많다. iterator()도 마찬가지

 

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

또, HashSet의 add 메서드를 사용하면, 내부 HashMap에 key = Set에 넣으려는 객체, value = Object 타입의 더미데이터 형태로 내부 HashMap에 추가된다.

 

HashMap에서 key 값은 중복이 허용되지 않으므로 HashSet은 add() 메서드를 통해 추가하려는 객체를 HashMap의 key 값으로 넘겨주어 요소의 중복을 방지한다. 천재적인 발상ㄷㄷ...

 

    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

iterator() 메서드 역시 HashMap에 있는 이터레이터를 호출한다. Map 자료구조의 상속트리에는 이터레이터가 존재하지 않으나,

public class HashMap<K, V> extends AbstractMap<K, V> {
	public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
}

HashMap의 keySet(key로 이루어진 Set)을 통하여 이터레이터를 호출할 수 있다.

final class KeySet extends AbstractSet<K> {
	...
    public final Iterator<K> iterator()     { return new KeyIterator(); }
	...
}

KeySet 클래스는 HashMap 내부에 구현체로 있는데, 여기서 이터레이터를 호출할 수 있다.

    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

그럼 이터레이터 호출에서 불러와지는 KeyIterator는 next 등의 이터레이터 메서드를 제공한다.

abstract class AbstractHashMap<K, V> {
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
}

HashIterator도 HashMap 내부 구현체로 자리잡고 있다.

그럼 최종적으로는 위의 nextNode() 메서드가 호출됨으로 next() 메서드가 실행된다.

 

위의 첫 번째 조건문은 CME를 발생시키는데, 이것은 List에 대해 다룰 때 했던 내용과 크게 다를 바 없고,

두 번째 조건문은 next()를 통해 불러와지는 값지 null일 경우 발생시키는 에러다.

(next는 AbstractHashMap이 내부클래스이기 때문에 외부클래스에서 인덱싱 등을 통해 가져온 값이다.)

 

그리고나서 노드들이 저장된 배열 (table)에서 인덱스의 범위 내에서 null 값이 아닐 때까지 반복문을 타고 table을 순회하며 next가 될 노드를 찾는다. 즉, HashMap의 다음 노드를 찾는 과정이라고 볼 수 있다.

 

 

자바 공식 API문서를 볼 때마다 진짜 절묘하게 추상화를 시켜놓은 것을 보면 경외감이 들 때가 있다.ㄷㄷ 대단하다..

암튼 HashSet, HashMap 끝