[Item10] Collection의 contains 메서드는 equals 메서드를 사용

[IAGREEBUT]

책 59page

onUnitCircle에서 사용한 Set을 포함하여 대부분의 컬렉션은 이 작업(contains)에 equals 메서드를 이용하는데, CounterPoint의 인스턴스는 어떤 Point와도 같을 수 없기 때문이다.

라는 문장이 있는데 대부분의 Collections 의 contains에 equals 메서드가 어떻게 사용되고 있는지 예시를 하나 들어서 설명해주시면 좋을 것 같습니다

[ForteEscape]

Q.

대부분의 Collections 의 contains에 equals 메서드가 어떻게 사용되고 있는지 예시를 하나 들어서 설명해주시면 좋을 것 같습니다.

A.

/**
     * Returns {@code true} if this list contains the specified element.
     * More formally, returns {@code true} if and only if this list contains
     * at least one element {@code e} such that
     * {@code Objects.equals(o, e)}.
     *
     * @param o element whose presence in this list is to be tested
     * @return {@code true} if this list contains the specified element
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index {@code i} such that
     * {@code Objects.equals(o, get(i))},
     * or -1 if there is no such index.
     */
    public int indexOf(Object o) {
        return indexOfRange(o, 0, size);
    }

    int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

• 해당 코드는 Java.Collection의 ArrayList 자료구조의 구현 코드입니다.
• 해당 코드의 contains 메서드를 보시면 indexOf 메서드를 사용하며 내부적으로 indexOfRange 메서드를 사용하고 있습니다.
• indexOfRange(0, size)로 해당 ArrayList의 모든 요소를 순회하면서 o.equals(es[i])로 입력으로 들어온 객체 o와 ArrayList의 내부 es[i]가 동일한가를 확인합니다.
• LinkedList의 경우에도 유사하게 동작합니다.
• HashSet, HashMap의 경우에는 조금 다른데 객체의 HashCode를 사용하여 비교하는 형식입니다. 이 때문에 HashMap 또는 HashSet에 자신이 만든 객체를 넣어야 하는 경우, HashCode를 반드시 구현해야 한다는 제약이 있으며, 이는 item 11과도 이어지는 내용입니다.

[zpqmdh]

ArrayList 자료 구조의 contains 메서드를 예로 들어주셔서 저는 HashSet 의 contains 메서드를 가져왔습니다.

/**
* Returns {@code true} if this set contains the specified element.
* More formally, returns {@code true} if and only if this set
* contains an element {@code e} such that
* {@code Objects.equals(o, e)}.
*
* @param o element whose presence in this set is to be tested
* @return {@code true} if this set contains the specified element
*/
public boolean contains(Object o) {
   return map.containsKey(o);
}

/**
* Returns {@code true} if this map contains a mapping for the
* specified key.
*
* @param   key   The key whose presence in this map is to be tested
* @return {@code true} if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
    return getNode(key) != null;
}

/**
* Implements Map.get and related methods.
*
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
          (first = tab[(n - 1) & (hash = hash(key))]) != null) {
          if (first.hash == hash && // always check first node
              ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
      if ((e = first.next) != null) {
            if (first instanceof TreeNode)
            return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
            if (e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
        } while ((e = e.next) != null);
            }
        }
    return null;
}

equals 메서드 내부에서 호출되는 getNode 메서드는 주어진 키에 해당하는 노드를 찾아서 반환하거나, 주어진 키에 해당하는 노드가 없을 경우 null 을 반환합니다.

서로 다른 두 개의 키가 동일한 해시 값을 가지는 경우를 해시 충돌 이라 하고, 이러한 충돌을 해결하기 위해 일반적으로 연결 리스트(Linked List)나 최근에는 트리(Tree) 구조를 사용합니다.

위의 사진이 바로 해시 충돌의 예이며, 이럴 경우 연결 리스트나 트리 구조를 사용하여 버킷의 같은 인덱스 값에 들어가게 됩니다.

getNode 메서드의 내부 동작을 살펴보면 다음과 같습니다.

1. 주어진 키에 대한 해시 값을 계산 → hash = hash(key)

2. Hash Map의 테이블이 비어 있지 않고, 해당 해시 값에 해당하는 bucket에 노드가 존재하는 경우

   → bucket의 인덱스 = 해시 값

3. 주어진 키와 해시 값이 일치하는 첫 번째 노드가 존재하는 경우, 해당 노드 반환 -> 이때 키값과 해시 값을 비교할 때 equals 메서드를 사용하고 있습니다.

4. 그렇지 않은 경우, 연결 리스트나 트리를 순회하면서 해당 키와 일치하는 노드 찾기

5. 일치하는 노드 찾으면 반환, 그렇지 않으면 null

만약 HashSet 내부의 모든 객체가 같은 해시코드를 가진다면, 같은 버킷안에 연결 리스트 혹은 트리 구조로 저장 되어, 평균 수행 시간에 O(1)인 해시 테이블이 최악의 경우 O(n)으로 느려질 수도 있습니다. 따라서, 좋은 해시함수라면 서로 다른 인스턴스에 다른 해시코드를 반환한다고 책에 언급하고 있습니다 (책 68페이지).