Java hashmap 설명

hashMap 과 hashcode 의 동작 원리

• hashMap 에서 get, put 할 때, hashCode 함수를 호출해서 해시 값을 얻어서 key 로 사용.

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

public V get(Object key) {
    Node<K,V> e;    
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

hashcode

• 아래와 같이 구현돼있고, key, value 를 ^ 하는 것.
• key, value 가 String 이라면 String 의 hashcode 를 가져다 쓰는 것임.

  public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
  }

hashMap 충돌 시 (같은 hashcode)

• 해시 충돌이 날 시 해결하는 방안은 2가지
  • Open Addressing : 데이터 충돌 시 다른 해시 영역에 데이터를 넣음.
  • Separate Chaning : 데이터 충돌 시 해당 값의 영역에 링크드 리스트 넣어서 링크드 리스트에 값을 이어 붙이기. (이 말은 하나의 값 뒤에 다음 값의 주소를 가지고 있다는 것)
• Separate Chaning 이 효율적. Open Addressing 은 데이터가 많아질수록 느려짐.
• 자바 8에서는 Separate Chaning 에 LinkedList 대신 트리를 사용
• LinkedList 를 이용해서 O(n) 만큼 찾는게 아니라 log(N) 으로 찾겠다는거지.