컴퓨터공부/Kotlin & Java

String.hashCode()는 같은 값을 리턴합니다. 근데 왜 HashMap에서 쓰나요?

achivenKakao 2021. 3. 5. 03:25

결론 먼저..

String.hashCode()는 중복된 값을 리턴할 수 있습니다. 하지만 HashMap에서 key로 String을 쓰셔도 됩니다.
왜냐면, HashMap은 hashCode(), == and equals() 를 이용해서 값을 저장할 entry lookup 을 선정하기 때문입니다.
즉, hashCode()값이 같아도, == 이나 equals() 함수를 통해서 다른 entry lookup으로 분기 된다는 것입니다.

-------------------------------------------------------------------------------------------------------------------------

HashMap의 key를 String으로 쓸 기회가 있어서.. 이거 안전한건가?? 하고 생각이 들어서 검색을 좀 했습니다.

그랬더니, blog.ggaman.com/916 이런 글이 나오더군요.

그래서 좀 더 검색해 봤더니, 아래의 두가지 글이 더 나왔습니다.

stackoverflow.com/questions/25736486/is-the-int-value-of-string-hashcode-unique/46686127 ( String.hashCode()는 중복된 값을 리턴한다.)

stackoverflow.com/questions/1894377/understanding-the-workings-of-equals-and-hashcode-in-a-hashmap (String.hashCode()는 중복된 값을 리턴하지만 HashMap의 key로 사용해도 된다.)

살짝 발취하면 이렇습니다.

HashMap uses hashCode(), == and equals() for entry lookup. The lookup sequence for a given key k is as follows:

  • Use k.hashCode() to determine which bucket the entry is stored, if any
  • If found, for each entry's key k1 in that bucket, if k == k1 || k.equals(k1), then return k1's entry
  • Any other outcomes, no corresponding entry

 

아무튼... 그래서... 뭐래는 건지 알겠는데... 그냥 넘어가기 찝찝해서.. 코드를 까봤습니다.

map.put()을 호출 하면 결국엔 putVal을 호출하는데 거기에서 ==, equals()를 사용해서 같은 key인지 확인 합니다.

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    
    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;
    }