Hash 기반 자료구조

이전에 해시에 대해서 알아보았으니, 자바에서 해시를 활용한 자료구조는 무엇이 있는지 각 특징은 무엇인지 코드를 통해 한번 알아보려고 한다.

2024.11.08 - [Language/Java] - Hash에 대해서

Hash에 대해서

---

HashTable

해시 함수와 배열을 기반으로 데이터를 key-value 쌍으로 저장하는 자료 구조이다.

 

해시 테이블은 key, hash function, hash, value, index, bucket 으로 이루어져있다.

• key : 고유한 값으로, 해시 함수의 입력값이다.

• hash function : 주어진 입력값(key)을 받아서 고유한 해시값(hash)로 생성하는 함수이다. 키를 고정된 크기의 값으로 변환하는 역할을 한다.

• hash : 해시 함수의 출력값으로, 주어진 입력값(key)에 대해 계산된 고유한 값이다. 인덱스를 계산할 때 사용된다.

• index : hash를 기반으로 계산된 해시 테이블 내의 인덱스이다. 이 인덱스를 통해 bucket을 찾는다.

• value : key에 매핑된 실제 값으로, key와 함께 bucket에 저장된다.

• bucket : key-value 쌍을 저장하는 공간이다.

 

Entry 배열 기반이다.

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable {
        /*
        * 버킷이 배열로 선언되어있다.
        * Entry는 버킷을 의미한다.
        */
        private transient Entry<?,?>[] table;
        
        private static class Entry<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Entry<K,V> next;
        ...
        }
}

해시 테이블은 Entry 객체들을 배열로 관리한다.

즉, 해시 테이블에 저장되어있는 버킷은 전부 연속적인 메모리에 할당되어있다.

 

해시 값과 인덱스

해시 테이블의 버킷에 접근하려면 인덱스가 필요하다.

다음은 해시 테이블의 put 함수의 일부 코드이며, 어떻게 인덱스를 계산하여 버킷에 접근하는지 보여준다.

public synchronized V put(K key, V value) {
    ..
    Entry<?,?> tab[] = table;
    int hash = key.hashCode(); (1)
    int index = (hash & 0x7FFFFFFF) % tab.length; (2)
    Entry<K,V> entry = (Entry<K,V>)tab[index]; (3)
    ..
}

(1) 입력된 key의 해시값을 가져온다.

(2) key의 해시값을 기반으로 인덱스를 계산한다.

(3) 계산된 인덱스를 사용하여 배열로 선언된 테이블에서 버킷을 찾는다.

인덱스를 계산하는 방법은 해시테이블에 정의된 모든 메서드에서 동일하다. 그렇지 않으면 버킷을 탐색하지 못하고 데이터를 조작하는 과정에서 문제가 발생할 수 있기 때문이다.

 

데이터 저장 순서는 무작위다.

배열 기반으로 인덱스와 버킷의 순서는 유지되지만, 데이터를 저장할 인덱스는 입력값인 key로부터 해시 함수를 통해 계산되기 때문에 배열의 특정 위치에 저장된다.

즉, 배열 자체에는 순서가 있지만 배열에 저장되는 데이터의 순서는 해시 함수에 따라 달라진다.

 

HashMap

Map 컬렉션의 구현체로, key-value 쌍을 저장하는 해시 기반의 자료구조이다.

 

노드 배열 기반이다.

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    transient Node<K,V>[] table;
    
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
    }
}

해시 테이블은 Node 객체들을 배열로 관리한다.

 

HashSet

Set 컬렉션의 구현체로, 중복을 허용하지 않고 순서와 관계없이 데이터를 저장하는 자료구조이다.

내부적으로 해시 맵을 사용한다.

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
        private transient HashMap<E,Object> map;
        
        public HashSet() {
            map = new HashMap<>();
        }
}

기본 생성자 뿐만 아니라, 매개변수를 갖는 생성자 또한 해시맵 객체를 생성한다.

 

중복을 허용하지 않는다.

먼저 HashSet의 중복 허용하지 않는다는 특징을 이해하려면 먼저, HashMap의 put 메서드의 동작 방식을 먼저 알아야 한다.

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
        public V put(K key, V value) {
            //구현 내용
        }
}

HashMap의 put 메서드는 동일한 키에 새로운 value를 추가하면 이전에 저장한 value는 새로운 value로 대체되며 key에 해당하는 value를 리턴한다.

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E,Object> map;
    
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
}

HashSet은 HashMap에 value를 추가할 때 더미 객체인 Object를 저장하고 있다.

HashMap에는 항상 동일한 value인 Object를 받기 때문에, 값은 대체되지 않을 것이며 그로인해 map.put 메서드를 나오는 값은 항상 Object 객체이거나 null 일 것이다.

 

 

HashTable 과 HashMap 차이

우선, HashSet을 제외하고 HashTable과 HashMap 을 비교하는 이유는 HashSet은 내부적으로 HashMap을 사용하기 때문이다.

해시 테이블과 해시 맵은 모두 key-value 쌍을 저장하는 자료구조이다.

첫 번째 차이점은 사용 관점이다. 해시 테이블은 컴퓨터 과학에서의 기본적인 자료구조로, 어플리케이션이나 언어에 관계없이 통용적으로 사용된다. 예를 들어, 기본적인 데이터베이스의 인덱싱, 네트워크 해시 테이블 등에 사용된다.

하지만 해시 맵은 해시 테이블의 구체적인 구현체로, 언어에 따라 다르게 구현될 수 있다. 예를 들어, 자바에서는 HashMap으로 구현되지만 파이썬에서는 dictionary로 구현된다.

 

두 번째 차이점은 메서드의 동기화 여부이다. 해시 테이블은 동기화 처리가 되어있는 반면에 해시 맵은 동기화 처리가 되어있지않다. 멀티 스레드 환경에서 해시 맵을 사용할 때에 동기화 처리를 해야한다면, ConcurrentHashMap을 사용해야한다.

 

해시기반 자료구조에서 hashCode와 equals의 동작

2024.11.05 - [Language/Java] - Object 클래스

Object 클래스

객체에서 hashCode와 equals 메서드를 재정의를 잘 구현하는 것이 해시 기반 자료구조에 이점을 가져다 준다고 Object 클래스에서 언급하였었다. 두 메서드 다 객체의 동등성을 비교하기 위해 재정의를 한다.

해시 테이블의 put 메서드 구현 내용을 보면서 이해해본다.

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        ⭐️ if ((entry.hash == hash) && entry.key.equals(key)) { ⭐️
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

데이터를 저장할 때 특정 인덱스의 버킷에 데이터가 저장되어있거나 충돌 이슈로 인해서 LinkedList에 데이터가 존재할 때 hashCode를 통해 생성된 해시값과, equals 메서드가 사용된다.

저장하고자 하는 객체의 해시값과 이미 저장되어있는 해시값을 비교하고, 해시값이 같다면 두 객체의 key 값을 비교한다.

이 두 조건이 true 일 때에 두 객체는 동등 객체로 버킷에 저장하지 않고 데이터를 꺼내서 리턴한다. 즉, hashCode와 equals의 결과값이 둘 중에 하나라도 false 이면 다른 객체로 버킷에 저장한다는 것이다.

 

따라서 동등성을 비교하기 위해서 equals 메서드뿐만 아니라 hashCode도 함께 재 정의해야한다. 이는 해시 기반 자료구조에서 객체를 key로 사용하기 위한 필수 조건이다.

---

해시를 알아가는 과정에서 단순히 동등성 비교하기 위한 메서드로만 생각했던 equals와 hashCode에 대해 해시 자료구조에서 어떻게 활용되는지, 그리고 필요성에 대해 알게되었다.

내가 사용하고자 하는 자료구조의 대한 원리를 제대로 이해해야, 그 필요성과 사용 이유를 명확하게 알 수 있을 것 같다.