Map과 HashTable 알아보고 Java의 HashMap 코드 뜯어보기

https://www.youtube.com/watch?v=ZBu_slSH5Sk 

유튜브 쉬운코드의 맵, 해시테이블 설명을 보고나서 추가로 궁금한 부분들을 정리해보았습니다.

영상의 설명이 너무 좋아 같이 봤으면 해서 영상도 같이 올립니다.

---

Map

• key-value pair들을 저장하는 ADT
• 같은 key를 가지는 pair는 최대 1개만 존재
• associative array, dictionary라고 불리기도 함
• 구현체
  • Hash Table
  • Tree-based

💡 ADT (Abstract Data Type, 추상 데이터 타입)
데이터와 해당 데이터에 적용되는 연산들을 묶어놓은 개념.
데이터 내부 구현을 감추고 데이터와 연산의 인터페이스만을 노출시켜 코드의 모듈성과 재사용성 향상을 목표로 함.
ex) Stack, Queue, List, Map, Set, Graph

 

Hash Table (Hash Map)

• 배열과 해시 함수(hash function)를 사용하여 Map을 구현한 자료구조
• (일반적으로) 상수 시간으로 데이터에 접근하기 때문에 빠름
  • 해시충돌이 발생할 경우 더 걸릴 수 있음. 아래에서 따로 설명
• Java8부터는 HashTable보다는 HashMap을 권장함
• HashMap은 Node<K, V>[] 타입의 배열을 사용
• 해시테이블의 크기는 capacity,  각 칸을 bucket, slot이라고 부름

 

Hash function

• 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
• (Hash Table에서) 임의의 데이터를 정수로 변환하는 함수. 해시함수가 리턴하는 정수를 Hash라고 한다

💡 Hash와 HashCode는 비슷한 개념이지만 약간의 차이가 있다
- Hash : 데이터를 변환하여 얻은 고정된 길이의 값. 데이터 변환 과정을 나타냄
- HashCode : 객체나 데이터를 고유하게 식별하기 위해 사용하는 정수 값. java에서 객체를 print할 때는 16진수로 변환한다

 

Hash와 HashCode의 관계가 궁금해 코드로 확인해봤습니다

궁금하신 분들은 더보기 눌러주세요

Member member = new Member("집사킴");
int hashCode = member.hashCode();
String hexString = Integer.toHexString(hashCode);
String memberString = member.toString();

System.out.println(hashCode); // 1164440413 (10진수)
System.out.println(hexString); // 4567f35d (16진수)
System.out.println(memberString); // com.example.project.Member@4567f35d
// toString 시 클래스명+@+16진수의 해시코드로 출력

// toString의 구현 방식. hashCode를 16진수로 변환한다
public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}

// HashMap의 해시 함수
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // key의 hashCode를 받아서 비트 연산으로 해시값을 만든다
}

정리하자면, Java HashMap의 경우

- 해시 함수에서 해시코드를 이용하여 해시를 만든다

- 해시와 해시코드는 다르다

- 객체를 toString 할 땐 해시코드를 16진수로 변환한다

 

Java Object의 toString() 메소드에서 해시코드를 16진수로 변환하는 이유

1. 가독성 : 10진수보다 짧아 가독성이 올라간다.
2. 정보 제공 : 객체의 메모리 주소와 연관이 있어 다른 객체와 비교할 때 빠르게 식별 가능
   (but, 해시코드 16진수 ≠ 메모리 주소)

 

해시 충돌 (Hash Collision)

• 서로 다른 key가 같은 bucket에 할당되는 것

해시 충돌 처리 방법

• Seperate Chaining : 충돌 발생 시 같은 해시 버킷 내에 LinkedList를 사용하여 데이터를 저장
  • Java HashMap의 경우 LinkedList의 사이즈가 임계치에 도달하면 이진트리로 변환함
• Open Addressing : 빈 슬롯을 찾아 데이터를 저장하는 방법
  • Linear probing : 충돌이 발생한 슬롯 다음의 슬롯을 차례로 검사. 빈 슬롯을 찾을 때 까지 계속 탐색
  • Quadratic Probing : 충돌이 발생한 슬롯 다음의 슬롯부터 제곱 값의 간격으로 탐색. (ex. 1, 4, 9, 16, …)
  • Double Hashing : 2개의 해시 함수를 사용하여 충돌이 발생한 슬롯 다음의 슬롯을 찾아감. 하나는 충돌 해결용, 또하나는 다음 탐사 위치 결정용.
  • Random Probing : 충돌 발생 시 랜덤한 간격으로 빈 슬롯을 찾아가는 방식

Hash table resizing

• 테이블의 데이터가 차면 capacity를 늘려주는 것
• Java의 HashMap의 경우 capacity의 3/4 이상 데이터 존재 시 resize처리
• new capacity로 해시 재배치

 

Capacity가 2의 승수인 이유

• 해시 함수의 균등한 분배 : 모듈러 연산을 비트 연산으로 대체하여 해시값들이 골고루 퍼질 수 있음
• Open Addressing의 효율성 : 충돌 처리 시 빈 슬롯을 찾기 위한 탐사를 비트연산으로 빠르게 가능
• 자료구조의 크기 조절 : 해시테이블 리사이즈 시 비트연산으로 간단하게 할 수 있음

Java HashMap의 default capacity은 16

// Java HashMap의 put()메소드 내부
if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
// capacity-1과 hash를 비트 AND 연산하여 put할 버킷의 인덱스 찾음


// Java HashMap의 resize() 내부
newCap = oldCap << 1
// oldCapacity에서 왼쪽으로 1칸 옮겨서(=2^n+1) new capacity를 정의
// ex) oldCapacity가 16(=2의 4승)일 경우 newCapacity는 32(=2의 5승)

// Java HashMap의 default capacity은 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

💡 Capacity가 반드시 2의 승수여야 하는 것은 아님
Python dict, Java7이하, C++ unordered_map/unordered_set, Ruby Hash는 2의 승수가 아닌 capacity도 가질 수 있다고 함

 

---

Java의 HashMap 뜯어보기

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

	// 중략
	transient Node<K,V>[] table; // Node<K,V>[] 타입의 배열로 테이블을 관리한다

	// ...

// Node객체는 hash, key, value, next를 갖는다
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value; 
    Node<K,V> next; // 해시충돌 발생할 때 Seperate Chaining 방식으로 쓸 다음 노드 (Linked List)

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

 

put(key, value)

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

// 해시 함수
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // key의 hashCode를 받아서 비트 연산 수행
}

// put 처리
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; // 배열이 비어있을 경우 resize하여 배열 생성
    if ((p = tab[i = (n - 1) & hash]) == null) 
    	// (n-1) & hash : capacity-1과 hash를 비트 AND 연산하여 put할 버킷의 인덱스 찾기.
        tab[i] = newNode(hash, key, value, null);
        // 버킷이 비어있을 경우 hash, key, value 삽입
        // 제일 오른쪽 null은 next필드. 해시충돌날 경우 linkedList로 값을 관리하는 영역
    else { // 버킷이 비어있지 않을 경우
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 버킷의 key와 인자로 받은 key를 비교하여 같으면 value 교체 준비 (아래에서 처리)
				
        // 해시충돌 발생 - 버킷이 TreeNode 타입인 경우 이진트리에 값을 넣음
        // Java는 Seperate Chaning 처리 시 특정 조건에서 이진트리도 함께 사용
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { 
            // 해시충돌 처리
            // 버킷의 next영역을 연결된 순서대로 탐색한다 (LinkedList 원리)
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 버킷의 next가 비어있을 경우 충돌한 새 노드를 저장
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                        // binCount가 임계치에 도달할 경우 LinkedList에 보관했던 데이터를 트리로 변경
                    break;
                    // next에 새 노드 저장 후 탐색 종료
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                    // LinkedList에서 hash, key가 일치하는 노드를 발견하면 LinkedList 탐색 종료
                p = e;
                // 현재버킷노드인 p를 next노드인 e로 변경 (해시테이블에서 노드를 아예 교체하는 건 아님)
                // next의 next를 탐색하기 위해 (chaining)
            }
        }
				
        // value 교체
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue; // 교체하기 전의 oldValue를 리턴
        }
    }
    // 기존값 교체처리 외의 삽입 작업 후의 후처리
    ++modCount; // hashMap 수정 횟수 1 증가. HashMap의 필드임
    if (++size > threshold) // size:맵의 요소 갯수, threshold: 해시테이블 리사이징 임계치
        resize();
    afterNodeInsertion(evict); 
    // 노드 삽입 후 수행할 추가작업 수행. 필요 시 오버라이드 해서 사용할 수 있는 메소드임
    return null;
}

value 교체 시 oldValue를 리턴하는걸 보고 직접 찍어봤음

Map<String, Integer> map = new HashMap<>();
System.out.println(map.put("haha", 1)); // null
System.out.println(map.get("haha")); // 1
System.out.println(map.put("haha", 2)); // 1 (값을 교체해서 oldValue인 1을 리턴)
System.out.println(map.get("haha")); // 2

 

resize()

직접 호출할 순 없고 put 등의 처리 과정에서 내부적으로 동작함

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;
        }
        // new capacity = oldCapacity의 2배(=왼쪽 1칸 시프트 연산)
        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) { // oldTable이 비어있지 않은 경우
        for (int j = 0; j < oldCap; ++j) { // oldTable을 탐색
            Node<K,V> e;
            if ((e = oldTab[j]) != null) { // oldTable의 버킷이 비어있지 않은 경우
                oldTab[j] = null;
                if (e.next == null)  // 해시충돌로 보관한 next값이 없을 경우
                    newTab[e.hash & (newCap - 1)] = e; // newCapacity로 다시 비트 AND연산하여 재배치
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 트리노드일 경우 split
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do { // next값이 있을 경우 연결리스트 순회하며 재배치
                        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; // 새 해시테이블 리턴

 

---

면접에서 해시충돌 질문에 대답을 제대로 못한 게 너무 슬퍼서 열심히 팠습니다 😭

영상을 보면서 궁금한 게 많았는데, 코드를 뜯어보니까 어렵긴 해도 의문이 많이 풀리네요

비트연산자에 대해서도 더 알게되어서 유익했습니다 😁

 

java 표준 라이브러리도 코드는 그닥 클린하지 않은듯,,,,,,,