HashSet

📝자바의 정석 연습문제를 풀다가 주제가 재밌어서 작성한다

다음 예제의 빙고판은 1~30사이의 숫자들로 만든 것인데, 
숫자들의 위치가 잘 섞이지 않는다는 문제가 있다. 
이러한 문제가 발생하는 이유와 이 문제를 개선하기 위한 방법을 설명하고,
이를 개선한 새로운 코드를 작성하시오.

예제:
(1) 1~30범위의 랜덤값을 만들고
(2) 랜덤값 25개를 HashSet에 저장
(3) HashSet에 저장된 데이터를 순서대로 출력
*기존 작성된 코드를 요약한겁니다

결과:
숫자들이 제대로 섞이지 않은 것을 확인할 수 있다

HashSet은 순서유지를 하지 않으며, 해싱기법을 사용하기 때문에 비슷한 값들이 비슷한 위치에 저장된다는 것은 대충 알 것이다. 그럼 실제 내부동작은 어떨까..?

---

🔍코드 살펴보기

이제 코드를 파고들어가보자,,,🔍🔍🔍

HashSet()

hashSet 먼저 생성⛏️

/**
* Constructs a new, empty set; the backing {@code HashMap} instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
    map = new HashMap<>();
}

: HashSet은 기본적으로 배열 크기가 16이고 load factor는 0.75로 생성한다고 한다

• load factor
  : 언제 배열 크기를 늘릴 지 결정하는 기준으로 16*0.75=12개가 저장되면 크기가 증가된다는 것이다

add()

이제 데이터를 추가해보자!⛏️

/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element {@code e} to this set if
* this set contains no element {@code e2} such that
* {@code Objects.equals(e, e2)}.
* If this set already contains the element, the call leaves the set
* unchanged and returns {@code false}.
*
* @param e element to be added to this set
* @return {@code true} if this set did not already contain the specified
* element
*/
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}


// Dummy value to associate with an Object in the backing Map
static final Object PRESENT = new Object();

: 저장하려는 요소가 포함되어있다면 추가한 다음 true를 반환하고 이미 존재해서 추가를 하지 않은 경우 false를 반환한다고 한다

🤔 저 PRESENT는 뭐지?

HashSet은 내부적으로 HashMap을 기반으로 만들어져있는데 HashMap은 (key,value)를 저장하지만 HashSet은 key만 사용하기 때문에 value에는 더미데이터를 넣는 것!

put()

더 들어가보자~⛏️

/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
*         {@code null} if there was no mapping for {@code key}.
*         (A {@code null} return can also indicate that the map
*         previously associated {@code null} with {@code key}.)
*/
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

: 간단하게 설명하자면 key에 매핑된 value가 없는 경우에는 null을 반환하거나 기존에 저장되어있던 value를 반환한다는 것이다.

⭐ hash()

그리고 여기서 hash(key)가 호출되는 것을 알 수 있다.

• 해당 key 객체의 hashCode() 메서드 호출
• 상위 16비트와 하위 16비트를 XOR (충돌을 줄이기 위함)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

🤔 근데 기본형은 hashCode()를 안가지고 있는데?

애초에 HashSet은 HashSet<Object>로 기본형을 받지 않아 래퍼 클래스를 전달해줘야 한다. 근데 set.add(10)는 어떻게 가능한거지..?

public class Main {
    public static void main(String[] args) {
        HashSet<int> set = new HashSet<>();
        set.add(10);
    }
}

위 코드를 컴파일한 파일을 읽으면 다음과 같다

$ javap -verbose Main
public class Main
  minor version: 0
  major version: 64
  flags: (0x0021) ACC_PUBLIC, ACC_SUPER
  this_class: #20                         // Main
  super_class: #2                         // java/lang/Object
  interfaces: 0, fields: 0, methods: 2, attributes: 1
Constant pool:
   #1 = Methodref          #2.#3          // java/lang/Object."<init>":()V
   #2 = Class              #4             // java/lang/Object
   #3 = NameAndType        #5:#6          // "<init>":()V
   #4 = Utf8               java/lang/Object
   #5 = Utf8               <init>
   #6 = Utf8               ()V
   #7 = Class              #8             // java/util/HashSet
   #8 = Utf8               java/util/HashSet
   #9 = Methodref          #7.#3          // java/util/HashSet."<init>":()V
 👉#10 = Methodref          #11.#12        // java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
  #11 = Class              #13            // java/lang/Integer
  #12 = NameAndType        #14:#15        // valueOf:(I)Ljava/lang/Integer;
  #13 = Utf8               java/lang/Integer
  #14 = Utf8               valueOf
  #15 = Utf8               (I)Ljava/lang/Integer;
  #16 = Methodref          #7.#17         // java/util/HashSet.add:(Ljava/lang/Object;)Z
  #17 = NameAndType        #18:#19        // add:(Ljava/lang/Object;)Z
  #18 = Utf8               add
  #19 = Utf8               (Ljava/lang/Object;)Z
  #20 = Class              #21            // Main
  #21 = Utf8               Main
  #22 = Utf8               Code
  #23 = Utf8               LineNumberTable
  #24 = Utf8               main
  #25 = Utf8               ([Ljava/lang/String;)V
  #26 = Utf8               SourceFile
  #27 = Utf8               Main.java
{
  public Main();
    descriptor: ()V
    flags: (0x0001) ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 3: 0

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=2, locals=2, args_size=1
         0: new           #7                  // class java/util/HashSet
         3: dup
         4: invokespecial #9                  // Method java/util/HashSet."<init>":()V
         7: astore_1
         8: aload_1
        👉9: bipush        10
        👉11: invokestatic  #10                 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
        14: invokevirtual #16                 // Method java/util/HashSet.add:(Ljava/lang/Object;)Z
        17: pop
        18: return
      LineNumberTable:
        line 5: 0
        line 6: 8
        line 7: 18
}
SourceFile: "Main.java"

🧐???이게 뭐지... 싶겠지만 위에서 관련된 부분만 가져오면 이해가 쉽다

(1) #10 = Methodref          #11.#12        // java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
(2) bipush        10
(3) invokestatic  #10                 // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;

(1) #10은 Integer.valueOf(int) 메서드를 참조
(2) int 타입의 10을 스택에 푸시
(3) invokestatic #10은 #10 메서드를 호출하라는 것으로 스택에서 10을 꺼내서 #10에 정의된 Integer.valueOf(10)을 실행하여 Integer 객체로 래핑된 10을 반환

💡이러한 과정을 오토박싱, 언박싱이라고 한다

putVal()

더더 들어가보자⛏️

    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

전체적인 흐름은 다음과 같다

• 테이블 생성
• tab[i = (n - 1) & hash 확인
  • 비었다면 값 추가
  • 안비었다면 해당 연결 리스트 순차적으로 확인
    • 다음 노드가 비었다면 (key,value) 추가
    • 동일한 키를 찾았다면 종료
  • 이미 키가 존재한다면 value 덮어쓰고 이전 value 반환
• 현재 size가 16*0.75=12개보다 크다면
  • 크기를 2배 확장 newThr = oldThr << 1
  • 재배치 인덱스는 (확장한 크기 - 1) & hash로 다시 계산한다

⭐여기서 중요한 것만 보자면 인덱스를 다음과 같이 구한다는 것을 볼 수 있다
tab[i = (n - 1) & hash

🤔근데 이게 뭐지?.?

static final int TREEIFY_THRESHOLD = 8;

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

binCount >= TREEIFY_THRESHOLD - 1라면 연결리스트를 Red-Black Tree로 변환하여 O(n) -> O(log n)으로 탐색 성능을 높이는 것
-> 이 부분은 인지만 하고 나중에 더 자세히 알아보자

• binCount: 같은 인덱스의 충돌 수

---

🧐그래서 데이터가 어떻게 저장되는지 보고싶어

위에서 ⭐를 바탕으로 보면 다음과 같이 인덱스가 구해지는데 이걸 이용해서 테스트 코드를 작성해보자

• h = key.hashCode()
• hash = h ^ (h >>> 16)
• i = (n - 1) & hash

import java.util.*;

public class test {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();

        set.add("1");
        set.add("2");
        set.add("3");
        set.add("4");
        set.add("5");
        set.add("6");
        set.add("7");
        set.add("8");
        set.add("9");
        set.add("10");
        set.add("11");
        set.add("12");

        int n = 16; // HashMap 기본 크기
        int h, hash, index;

        System.out.printf("%-6s | %-12s | %-20s | %-10s\n", "Key", "hashCode", "hash (h ^ (h >>> 16))", "Index");
        System.out.println("---------------------------------------------------------------");

        for (String str : set) {
            h = str.hashCode();
            hash = h ^ (h >>> 16);
            index = (n - 1) & hash;

            System.out.printf("%-6s | %-12d | %-20d | %-10d\n", str, h, hash, index);
        }
    }
}

💡결과
Key    | hashCode     | hash (h ^ (h >>> 16)) | Index     
---------------------------------------------------------------
11     | 1568         | 1568                 | 0         
1      | 49           | 49                   | 1         
12     | 1569         | 1569                 | 1         
2      | 50           | 50                   | 2         
3      | 51           | 51                   | 3         
4      | 52           | 52                   | 4         
5      | 53           | 53                   | 5         
6      | 54           | 54                   | 6         
7      | 55           | 55                   | 7         
8      | 56           | 56                   | 8         
9      | 57           | 57                   | 9         
10     | 1567         | 1567                 | 15       

🔍데이터가 13개 이상이라면?

현재 크기 * 2가 되므로 크기가 16일 경우와 32일 경우의 인덱스를 구했다

<import java.util.*;

public class test {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();

        set.add("1");
        set.add("2");
        set.add("3");
        set.add("4");
        set.add("5");
        set.add("6");
        set.add("7");
        set.add("8");
        set.add("9");
        set.add("10");
        set.add("11");
        set.add("22");
        set.add("21");
        set.add("24");
        set.add("50");
        set.add("13");
        set.add("12");

        // 테이블 크기 (16 -> 32로 증가)
        int oldCapacity = 16;
        int newCapacity = oldCapacity + (oldCapacity >> 1);

        System.out.printf("%-6s | %-12s | %-20s | %-10s\n", "Key", "hashCode", "hash (h ^ (h >>> 16))", "Index (Old -> New)");
        System.out.println("---------------------------------------------------------------");

        for (String str : set) {
            int h = str.hashCode();
            int hash = h ^ (h >>> 16);

            // 리사이즈 전 인덱스 (16 크기일 때)
            int oldIndex = (oldCapacity - 1) & hash;

            // 리사이즈 후 인덱스 (32 크기일 때)
            int newIndex = (newCapacity - 1) & hash;

            System.out.printf("%-6s | %-12d | %-20d | %-10d -> %-10d\n", str, h, hash, oldIndex, newIndex);
        }
    }
}

💡결과
Key    | hashCode     | hash (h ^ (h >>> 16)) | Index (Old -> New)
---------------------------------------------------------------
11     | 1568         | 1568                 | 0          -> 0         
22     | 1600         | 1600                 | 0          -> 0         
12     | 1569         | 1569                 | 1          -> 1         
24     | 1602         | 1602                 | 2          -> 2         
13     | 1570         | 1570                 | 2          -> 2         
1      | 49           | 49                   | 1          -> 17        
2      | 50           | 50                   | 2          -> 18        
3      | 51           | 51                   | 3          -> 19        
4      | 52           | 52                   | 4          -> 20        
5      | 53           | 53                   | 5          -> 21        
6      | 54           | 54                   | 6          -> 22        
7      | 55           | 55                   | 7          -> 23        
8      | 56           | 56                   | 8          -> 16        
9      | 57           | 57                   | 9          -> 17        
50     | 1691         | 1691                 | 11         -> 19        
10     | 1567         | 1567                 | 15         -> 23        
21     | 1599         | 1599                 | 15         -> 23      

---

p.s 요즘,, 초록초록한게 좋아서 썸네일을 바꿨다,,ㅎㅎ