treecode

코드스쿼드 미션으로 게시판을 구현해보는데 이전에 혼자 게시판을 만들어 볼 때는 구현하기 급급했다면 이번에는 왜 이걸 썼는지 좀 생각하면서 구현을 해보려고 한다.

먼저 DB 연동 없이 자바 코드로 Repository를 구현하면서 동시성 처리를 위해 ConcurrentHashMap을 사용했는데 대충 알고 쓰는 것 같아서 정리를 하기 위해 HashMap의 구조부터 학습을 했다.

해싱(Hashing)이란 해시 함수를 이용해서 데이터를 해시 테이블에 저장하고 검색하는 방법으로 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 알고리즘 함수이다.

HashMap은 해싱을 구현한 컬렉션 자료구조로 키에 대한 해시 값을 사용하여 값을 저장하는 Associate array(key-value의 형태로 키를 통해 연관되는 값을 얻을 수 있는 자료 구조)이다.

HashMap은 배열 + 링크드 리스트의 조합으로 되어 있는데 링크드 리스트는 데이터의 삽입, 삭제와 같은 동작에는 효율적이지만 검색 속도는 비효율적이다. 하지만 HashMap은 Node를 배열(버킷)로 가지고 있는 형태이기 때문에 조회 속도가 O(1)로 빠른 편이다.

그런데 왜 HashMap은 왜 배열 + 링크드 리스트 구조로 되어 있을까? 자바의 HashMap은 객체의 hashCode()를 해시 함수로 사용하는데 Object 클래스의 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시 코드를 만들어 내며 int 값을 반환한다. 하지만 HashMap 배열(버킷)의 용량이 값을 모두 수용할 수 없으며 메모리 효율 문제도 있기 때문에 해시 코드 값에 나머지 연산을 활용하여 버킷의 index를 구한다. (균등하게 index를 분포하기 위해 보조 해시 함수도 사용한다고 한다.)  그렇게 되면 중복된 key 값을 가지는 경우가 생기는데 이를 해시 충돌이라 한다.

해시 충돌이 발생할 경우를 대비해여 Open Addressing, Separate Chaining 이 있다.

HashMap은 Separate Chaining 방식을 사용하는데 같은 Key를 가지는 경우 equals()를 비교해서 같으면 동일 객체로 판단하여 교체를 하고 다르면 Chaining으로 연결을 한다.

Java8 부터는 데이터가 많아질 경우 개수에 따라 Tree로 변환한다.

HashMap의 버킷 용량이 동적으로 확장될 때마다 모든 key-value를 읽어서 Separate Chaining을 재구성해야 하기 때문에 상황에 따라 생성자로 initialCapacity, loadFactor를 정의해주는 것도 좋을 것 같다.

[참고]

https://d2.naver.com/helloworld/831311

HashMap을 사용할 때, put(key, value)으로 데이터를 저장할 수 있는데 HashMap의 경우 key 값이 존재할 경우 value 값을 대체하고 기존의 value 값을 반환해준다. 하지만 key 값이 존재하지 않는 경우에는 새로 데이터를 저장하고 null을 반환한다. (기존 value 값이 없기 때문)

put()으로 데이터를 저장하고 반환된 value 객체를 참조할려고 하니 NullPointerException이 발생한다는 경고를 보고 어떻게 구현이 되어있나 확인해보았다.

HashMap에서 해싱이란 해시 함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 방식을 말하는데 해시함수가 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있다.

해싱에서 사용하는 자료구조는 배열과 링크드 리스트의 조합으로 되어 있는데 key 값을 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장이 된다.

해시함수의 계산 결과인 해시코드로 해당 값이 저장되어 있는 링크드 리스트를 찾고, 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다. (링크드 리스트는 검색에 불리하기 때문에 해시코드가 서로 중복되지 않도록 하는 전략이 좋다.)

HashMap의 경우 Object 클래스에 정의된 hashCode()를 해시 함수로 사용하는데 이는 객체의 주소를 이용하는 알고리즘으로 모든 객체에 대해 hashCode() 결과가 서로 유일하게 된다. 

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

그래서 실제 HashMap의 put() 메서드를 보면 putVal() 메서드를 호출하면서 해시함수 hash(key)를 실행하고 해시 코드를 넘겨준다.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
	    ...
        
        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;
}

putVal() 메서드의 일부를 보면 key가 존재하는지 확인을 하고 value를 교체한 뒤 oldValue를 반환하거나 그렇지 않을 경우 null을 반환한다.