Java 자료구조 3 - Map

Java 자료구조 1 - 톺아보기
Java 자료구조 2 - Set
Java 자료구조 3 - Map
Java 자료구조 4 - List
Java 자료구조 5 - Collection
Java 자료구조 6 - Stack
Java 자료구조 7 - Queue, Comparator
Java 자료구조 8 - Deque

 

Map은 인터페이스이며, 이를 상속하는 대표적인 구현 클래스는 HashMap, LinkedHashMap, TreeMap이 있습니다.

---

Module java.base

Package java.util

Interface Map<K,V>

Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values
All Known Subinterfaces: Bindings, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, NavigableMap<K,V>, SortedMap<K,V>
All Known Implementing Classes: AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, Headers, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap

---

위 document에서 볼 수 있듯, Map 인터페이스는 Collection 인터페이스를 상속받지 않습니다. Map은 중복을 허용하지 않는 Key와 중복 가능한 Value가 각각 쌍을 이루어 저장되는 자료구조입니다. 삽입, 삭제, 조회 연산이 굉장히 빠르지만, 순서를 보장하지 않고 정렬이 불가하다는 단점을 가지고 있습니다.

특징

• Key 중복 불가, Value 중복 가능
• 순서 보장 불가
• 정렬 불가(TreeMap 가능)
• Thread-safe 불가능, 불안정함

 

1. HashMap

해시 함수를 이용한 Map입니다. 삽입, 삭제, 조회 연산이 아주 빠른 자료구조이며, 삽입 데이터의 순서를 보장하지 않습니다. 정렬이 불가합니다.

/**
 * 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);
}

HashMap을 put 하면, key를 hash 해서 putVal을 호출합니다.

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash의 경우, key로 전달받은 값을 Object class에 존재하는 hashCode를 통해 객체의 해시 코드 값을 리턴합니다. Object class의 hashCode의 경우 java 버전에 따라 내용이 조금 다른데, java 13부터 아래와 같이 변경되었습니다.

Object class의 hashCode

위 내용 중 @implSpec으로 표기된 내용을 보면 아래와 같은 내용을 확인할 수 있습니다.

실용적인 이유로, Object class의 hashCode 메소드는
고유한 Object에 대해 고유한 integer 값을 리턴합니다.

 

hashCode를 만드는 것도 상당히 재미있는데, 추후 별도의 페이지에서 다루겠습니다. (List의 hashCode 메소드를 보면 매 단계마다 각 원소의 hashCode를 더하고 31일 곱하는 점 등)

List 의 hashCode

 

hashCode를 통해 integer 값을 전달받고, right shift 연산(">>>"는 주어진 비트 수만큼 이동하며, 앞에 비어있는 빈칸은 0으로 채우는 연산자)으로 16비트 이동한 값과 ^(XOR)하여 사용할 hash값을 만들어냅니다.

이렇게 얻어진 hash 값과, key, value를 전달하여 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;
}

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

putVal 메소드에서 멤버 변수인 table 값을 체크해서 없는 경우 resize()를 호출하게 됩니다.

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize()에서 확인할 수 있듯이 이미 table이 초기화되어 있지 않으면 새로운 배열을 생성하며, 기존의 배열이 있다면 index 위치를 재조정해 줍니다. 

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

여기서 HashMap은 내부적으로 사실상 LinkedList로 이루어진 배열임을 알 수 있습니다.

resize()를 거친 후 아래 putVal method 내용과 같이 "(n - 1) & hash"의 index에 아무런 값이 들어 있지 않으면 새로운 노드를 저장합니다.

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

newNode는  아래와 같이 새로운 Node를 만들어 해당 배열에 넣습니다.

// Create a regular (non-tree) node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

이후 처리 과정은 다시 putVal로 돌아가서 확인해 보면 아래와 같이 3가지가 있습니다.

1. hash 값과 실제 값이 같다면 기존에 있던 값을 교체합니다.
2. TreeNode인 경우 putTreeVal method를 통해 TreeNode에 값을 넣습니다
3. 하나의 인덱스에 들어있는 값이 많아지면 마지막 노드(p.next 가 null)에 새로운 노드를 넣어줍니다.(TreeNode)

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

따라서 HashMap의 put을 하는 경우 키값을 Hashing 하여 Node<K, V>[Hasing 키값 & 배열 크기 -1] 에 값이 들어가고, key가 같고 value가 다르면 LinkedList의 자료구조로 이어서 저장되는 것임을 알 수 있습니다.

참고로 위 내용에는 생략되었지만, put을 할 때 저장공간을 초과하게 되면 (default initial capacity=16 and the default load factor=0.75) 현재 크기의 2배로 재산정합니다.

/**
 * Constructs an empty {@code HashMap} with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

remove의 경우는 보다 단순한데, key값을 기준으로 탐색하여 해당 key값에 대한 value가 존재하면 삭제하고, 존재하지 않는 경우 null을 반환합니다.

/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @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 remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

/**
 * Implements Map.remove and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

node에 값이 있는 경우 해당 node를 지우고, 값이 없는 경우 null을 리턴하는 것을 확인할 수 있습니다.

위와 같은 이유들로 HashMap은 비교적 저장의 속도는 떨어지지만, 데이터를 검색하는 데는 뛰어난 성능을 보입니다. 아울러 키값은 중복이 불가능 하지만, 값은 중복이 가능하며, 하나의 키값에 새로운 값을 추가 시 값이 추가되는 구조로 만들어져 있습니다.

 

2. LinkedHashMap

HashMap은 Node를 꺼낼 때 넣은 순서를 보장하지는 않습니다. HashMap의 KeySet을 확인하면 아래와 같은 내용을 확인할 수 있습니다.

final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }

    public Object[] toArray() {
        return keysToArray(new Object[size]);
    }

    public <T> T[] toArray(T[] a) {
        return keysToArray(prepareArray(a));
    }

    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (Node<K,V> e : tab) {
                for (; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

forEach를 보면, 0부터 순회하여 hash값(integer)이 낮은 순서부터 순회하게 되며, loadFactor를 넘어가는 순간 hashCode의 재분배가 일어나서 순서가 뒤바뀌게 되기 때문에 순서가 보장되지 않는 것입니다.

LinkedHashMap은 기존 HashMap에서 LinkedList를 활용하여 키를 세팅할 때(foreah로 순회할 때) 넣은 순서를 유지할 수 있도록 해주는 차이가 있습니다.

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    /*
     * Implementation note.  A previous version of this class was
     * internally structured a little differently. Because superclass
     * HashMap now uses trees for some of its nodes, class
     * LinkedHashMap.Entry is now treated as intermediary node class
     * that can also be converted to tree form. The name of this
     * class, LinkedHashMap.Entry, is confusing in several ways in its
     * current context, but cannot be changed.  Otherwise, even though
     * it is not exported outside this package, some existing source
     * code is known to have relied on a symbol resolution corner case
     * rule in calls to removeEldestEntry that suppressed compilation
     * errors due to ambiguous usages. So, we keep the name to
     * preserve unmodified compilability.
     *
     * The changes in node classes also require using two fields
     * (head, tail) rather than a pointer to a header node to maintain
     * the doubly-linked before/after list. This class also
     * previously used a different style of callback methods upon
     * access, insertion, and removal.
     */

    /**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    @java.io.Serial
    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;
    
...

LinkedHashMap은 HashMap을 상속받고 있으며, 특이점으로 head와 tail, 그리고 before, after라는 변수가 추가되었습니다. (이 변수들을 이용하여 Map에 들어온 순서를 기억할 수 있습니다.)

put을 하는 경우, 기존 HashMap의 put과 putVal을 사용합니다. 위에서 HashMap관련 내용을 확인하던 중, putVal 메소드 내부에 "newNode(hash, key, value, null)", "afterNodeAccess(e)",  "afterNodeInsertion(evict)" 와 같은 메소드가 있음을 확인할 수 있습니다.

newNode가 실행되면 LinkedHashMap의 Node인스턴스를 하나 생성하고 기존에 들어있는 마지막 Node와 새로 추가한 노드를 연결해줍니다.

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

afterNodeAccess는 HashMap의 Key가 중복된다면 이전 Node를 향하고 있는 linkNode를 새로운 node를 향하도록 변경합니다.

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

afterNodeInsertion는 Node를 정리합니다.

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

HashMap과 다르게 KeySet(LinkedKeySet)을 할 때 forEach문의 순환 시 head에서 시작해서 e.after가 null이 될 때까지 반복하여 순서를 보장해 줄 수 있게 합니다.

final class LinkedKeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<K> iterator() {
        return new LinkedKeyIterator();
    }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator()  {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED |
                                        Spliterator.DISTINCT);
    }

    public Object[] toArray() {
        return keysToArray(new Object[size]);
    }

    public <T> T[] toArray(T[] a) {
        return keysToArray(prepareArray(a));
    }

    public final void forEach(Consumer<? super K> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.key);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

 

remove의 경우도 HashMap의 remove를 사용하며, 이 중 "afterNodeRemoval(node)"가 실행되어,  LinkedHashMap의 아래 method가 실행됩니다.(HashMap에는 "void afterNodeRemoval(Node<K,V> p) { }"로 존재)

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

이를 통해 LinkedHashMap에서 삭제 노드에 대해서 before와 after의 연결을 끊어줍니다.

순서가 보장되나, LinkedList과 동일하게, 조회 시 시간 복잡도가 증가하기 때문에 순서가 보장되어야 하는 상황이 아니라면 HashMap을 사용하면 됩니다.

 

3. TreeMap

 HashMap은 hashCode()를 이용하여 hashing 된 key값을 연산 과정을 거쳐 index로 이용하며, index가 겹치는 경우 LinkedList를 통해 덧붙이는 구조입니다. 따라서 HashMap의 경우 순서가 보장되지 않습니다.

TreeMap의 경우 이진트리를 기반으로 한 Map Collection입니다. (같은 구조로 이루어진 TreeSet과의 차이점은 TreeSet은 단순히 값만 저장하나, TreeMap은 키와 값이 저장된 Map, Entry를 저장한다는 차이가 있습니다.)

TreeMap은 내부적으로 Red-Black Tree 구조로 이루어져 있습니다. 이는 이진 탐색 트리의 문제점을 보완한 트리구조입니다. 이진 탐색 트리의 문제점은 한쪽으로 치우쳐진 경우 기존 O(logN)의 탐색 속도가 최악의 경우 O(N)으로까지 떨어질 수 있습니다.

Red-Black Tree는 balanced binary search tree로, 항상 넣을 때와 뺄 때, 그리고 순회에 대해서 모두 O(logN)을 만족합니다. 루트부터 리프 노트까지의 블랙 노드의 개수와 레드 노드의 개수가 같도록 유지합니다.

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    @SuppressWarnings("serial") // Conditionally serializable
    private final Comparator<? super K> comparator;

    private transient Entry<K,V> root;
    
    ...

HashMap과 동일하게, AbstractMap을 상속받으나, NavigableMap을 implements 받고 있습니다.(NavigableMap은 정렬된 Map에서 여러 가지 방법의 탐색을 제공합니다.)

내부 변수는 정렬을 위해 사용되는 comparator가 존재하며, Entry는 Tree에 맞게 root라는 이름을 가지고 있습니다.

put 하는 경우, Red-Blakc Tree 구조로 데이터를 입력합니다. (자세한 내용은 링크된 wiki 참조)

private V put(K key, V value, boolean replaceOld) {
    Entry<K,V> t = root;
    if (t == null) {
        addEntryToEmptyMap(key, value);
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else {
                V oldValue = t.value;
                if (replaceOld || oldValue == null) {
                    t.value = value;
                }
                return oldValue;
            }
        } while (t != null);
    } else {
        Objects.requireNonNull(key);
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else {
                V oldValue = t.value;
                if (replaceOld || oldValue == null) {
                    t.value = value;
                }
                return oldValue;
            }
        } while (t != null);
    }
    addEntry(key, value, parent, cmp < 0);
    return null;
}

put과 마찬가지로 remove시에도 Red-Blakc Tree 구조로 데이터를 제거합니다.

/**
 * Removes the mapping for this key from this TreeMap if present.
 *
 * @param  key key for which mapping should be removed
 * @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}.)
 * @throws ClassCastException if the specified key cannot be compared
 *         with the keys currently in the map
 * @throws NullPointerException if the specified key is null
 *         and this map uses natural ordering, or its comparator
 *         does not permit null keys
 */
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

/**
 * Delete node p, and then rebalance the tree.
 */
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

put 삭제 시에도 remove시에도 Tree를 재조정해 주어야 합니다.

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
    Objects.requireNonNull(action);
    int expectedModCount = modCount;
    for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
        action.accept(e.key, e.value);

        if (expectedModCount != modCount) {
            throw new ConcurrentModificationException();
        }
    }
}

/**
 * Returns the successor of the specified Entry, or null if no such.
 */
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

순환 시에는 왼쪽 노드는 부모보다 작고, 오른쪽 노드는 부모보다 값이 크기 때문에 오름차순으로 순환하기 위해서는 중위 순환으로 트리를 탐색합니다. 즉, 왼쪽 노드 -> 부모 -> 오른쪽 노드 순서로 반환합니다.

위에서 설명한 것과 같이 일반적으로 저장, 삭제 시에도 정렬된 상태로 Map을 유지하기 때문에 HashMap보다 성능이 떨어지나, 정렬된 데이터를 조회하거나 범위 검색이 필요한 경우 TreeMap이 유리할 수 있습니다.