[항해99 취업 리부트 코스 학습일지] 3기 21일차 TIL(부제: Spring 강의를 열심히 들어요,,)

안녕하세요. delay100입니다.

팀원분들과 계속 이런저런 이야기 하면서 시간을 또 많이 보낸 날이에요!

그것과 별개로  오늘은 Spring강의를 정말 열심히 들었어요..

오늘 기술매니저님이 개인 사정이 있으셔서 못 오신다하여 내일 들을 Spring강의를 좀 땡겨서 들었어용,,ㅎㅎ

원래 목표가 5일동안 다 듣는거였는데 4일로 줄여서 듣는걸로...!  오랜시간 강의를 들으니까 피곤하네요..

---

오늘의 타임테이블

• 9시~10시 팀 스크럼(SI, SM, SERVICE 취업 관련 이야기)
• 10시~1시 4문제 해결
• 1시~2시 점심
• 2시~4시 Spring강의 (RestTemplate ~)
• 4시~6시 프로젝트 주차 발제 + 팀원끼리 이야기(팀 스터디)
• 6시~7시 Spring강의(RestTemplate 요청 주고받기 - 서버로 클라이언트처럼 소통해보기)
• 7시~8시 저녁
• 8시~11시30분 Spring강의(Naver 검색 API이용, DB Entity 연관관계, 지연로딩, 영속성 정의)

 

---

Q. 팀원끼리 한 CS 스터디

어제 스터디(Hash)의 연장선입니다!

[항해99 취업 리부트 코스 학습일지] 3기 20일차 TIL(부제: 팀 스터디 열정적으로 한 날)

 

A1. Set은 Map이다.

결국, Set은 Map임

Map에서 value를 안쓰는 것이 Set

Set 내부를 뜯어보면 Map이 나온다!

 

A2. HashMap은 배열 -> 트리가 된다. 

 

HashMap의 내부 구조와 동작 원리:

- 내부 구조

HashMap은 내부적으로 배열로 구현되어 있습니다. 이 배열의 각 위치는 "버킷"이라 불리며, 각 버킷은 여러 개의 요소를 저장할 수 있습니다. 요소가 추가될 때, 요소의 해시코드에 따라 적절한 버킷에 저장됩니다.

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;
    }
}

- 해시 충돌

서로 다른 두 키가 동일한 해시코드를 가질 때 해시 충돌이 발생합니다. 해시 충돌이 발생하면 같은 버킷에 여러 요소가 저장됩니다. 초기에는 이 요소들이 링크드 리스트로 저장됩니다.

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

- 트리로의 변환

 한 버킷에 저장된 요소의 개수가 8개를 초과하면, 해당 버킷의 구조는 링크드 리스트에서 트리(일반적으로 레드-블랙 트리)로 변환됩니다. 트리로 변환되면 요소 검색 속도가 O(log N)으로 향상됩니다.

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

 

 

이제 문제 상황을 하나 가정하겠습니다.

- 상황 설명

• fb1, fb2, ..., fb8의 해시코드가 모두 1이라고 가정합니다.
• 이들의 해시코드는 모두 동일하므로, 동일한 버킷에 저장됩니다.
• 한 버킷에 저장된 요소의 개수가 8개를 초과하면, 해당 버킷의 구조는 LinkedList에서 트리(일반적으로 레드-블랙 트리)로 변환됩니다.
• fb9를 추가한다고 가정해봅시다. fb9의 해시코드도 1입니다. 따라서 fb9 역시 동일한 버킷에 저장됩니다.
• 버킷이 이미 트리로 변환되어 있기 때문에, fb9는 트리 구조 내에서 저장됩니다.

트리로 변환된 후 fb9를 찾으려는 상황

- 트리로 변환 후의 검색 문제

트리로 변환된 후, 각 요소는 트리의 노드로 저장됩니다. 하지만, 트리의 노드에서 값을 비교할 때는 기본적으로 equals 메서드를 사용합니다. 

만약 요소들이 Comparable 인터페이스를 구현하지 않았다면, 트리 내에서 요소를 비교할 때, equals 메서드를 사용하게 되며, 요소를 찾지 못할 가능성이 있습니다. 이 경우, HashMap은 트리 내 모든 노드를 순회하여 값을 찾게 됩니다.

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

    static <K,V> TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

// 트리로 바꾸는 코드
    final void treeify(Node<K,V>[] tab) {
        TreeNode<K,V> root = null;
        for (TreeNode<K,V> x = this, next; x != null; x = next) {
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
            if (root == null) {
                x.parent = null;
                x.red = false;
                root = x;
            }
            else {
                K k = x.key;
                int h = x.hash;
                Class<?> kc = null;
                for (TreeNode<K,V> p = root;;) {
                    int dir, ph;
                    K pk = p.key;
                    if ((ph = p.hash) > h)
                        dir = -1;
                    else if (ph < h)
                        dir = 1;
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);

                    TreeNode<K,V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        root = balanceInsertion(root, x);
                        break;
                    }
                }
            }
        }
    }
}

 

 

결론

이로 인해 HashMap의 검색 시간이 O(N)이 될 수 있습니다. 따라서, 성능을 최적화하려면 키 클래스가 Comparable을 구현하거나, 커스텀 Comparator를 제공해야 합니다. 이렇게 하면 트리 내에서 요소를 효율적으로 찾을 수 있습니다.

public class MyKey implements Comparable<MyKey> {
    private final int id;
    public MyKey(int id) {
        this.id = id;
    }

    @Override
    public int compareTo(MyKey other) {
        return Integer.compare(this.id, other.id);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyKey myKey = (MyKey) o;
        return id == myKey.id;
    }

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

 

정리하면

• HashMap은 기본적으로 배열로 구현되어 있으며, 동일한 해시코드를 가진 요소들이 많아지면 트리로 변환됩니다.
• 트리로 변환되면 검색 성능이 O(log N)으로 향상되지만, 요소가 Comparable을 구현하지 않으면 성능이 저하될 수 있습니다.
• 이를 방지하려면 키 클래스가 Comparable을 구현하거나, HashMap에 적절한 Comparator를 제공해야 합니다.

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

[할인]란에 “추천왕 3기 백지연” 입력 시 10만원 할인
(*얼리버드, 타 혜택 중복 적용 가능)

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지