JAVA Hash 그리고 HashMap 과 HashTable - 자료구조(7)

1. 배경

---

이전 자료구조에서 자료구조 안에 있는 특정 값을 찾기 위해서 배열(array)은 인덱스(Index)를, 리스트(list)는 노드를 순회해서 해당 값을 찾았다. 배열은 접근은 빨랐지만 데이터 추가 삭제 시 각 값을 이동시켜야 하므로 시간이 많이 걸렸고, 리스트는 데이터 추가 삭제는 빨랐지만 조회할 때 순회하는데 시간이 많이 걸렸다.

 

데이터 접근은 배열처럼 인덱스로 바로 하면서 삽입 삭제는  리스트처럼 하는 자료구조는 없을까? 그러려면 배열의 인덱스와 데이터 사이에 일정한 관계가 있어야 한다.

 

데이터를 이용하여 배열의 인덱스로 만드는 것이 Hash이다.

 

 

---

 

 

2. Hash 란 무엇인가?

---

출처 - https://www.youtube.com/watch?v=Vi0hauJemxA

해쉬는 임의의 길이를 갖는 데이터(Key)를 해쉬 함수를 통해 고정된 길이의 데이터 즉, 해시 코드로 매핑하는 것이다.

해시함수가 동일하다면 환경에 상관없이 동일한 해시 코드를 만든다. 이 해시 코드를 배열(hash table)의 주소(index)로 변환시켜 사용한다.

 

배열은 한정적이기 때문에 다른 해시 코드 값이더라도 같은 인덱스를 가질 수 있고, 해시 코드의 길이는 제한되어 있기 때문에 다른 키가 같은 해쉬 코드를 가질 수 있다. 이런 두 경우를 충돌(Collision)이라고 한다. 이런 경우는 배열 내부는 리스트로 되어 있기 때문에 리스트에 추가해주면 된다. 즉, array로 주소를 찾고 node로 데이터를 추가 삭제하는 것이다.

때문에 잘 만들어진 해시 함수는 데이터가 배열에 골고루 퍼져서 배열 하나에 하나의 데이터만 있기 때문에 시간 복잡도가 O(1)이고, 한 인덱스에 데이터가 다 몰릴 경우(최악)는 배열 안의 리스트에서 데이터를 찾아야 하니 시간 복잡도가 O(n)이 된다.

 

해시의 성능에 영향을 주는 요인은 용량과 부하율 이 두 가지다. 용량은 해시 테이블에 있는 배열의 크기다. 부하율은 해시 테이블의 용량이 자동으로 증가하기 전에 해시 테이블이 얼마나 가득 차도록 허용되는지를 측정한 것이다. 해시 테이블의 항목 수가 부하율과 현재 용량의 곱을 초과하면 해시 테이블이 약 2배의 버킷 수를 갖도록 해시 테이블을 다시 생성합니다.

ex) 자바 컬렉션 프레임워크 HashMap 1.2 버전의 값으로 설명해보자면

• 디폴트 초기 용량은 16
• 디폴트 부하율을 0.75

이므로 해시 테이블의 항목수가 16 x 0.75 = 12 가 초과하면 용량이 32 이가 되도록 해시 테이블을 다시 만든다.

 

 

---

 

 

3. HashTable과 HashMap

---

 

HashTable과 HashMap 둘 다 키와 값 쌍을 해쉬 테이블에 저장한다. 그렇다면 이 둘의 차이는 무엇일까. 자바 컬랙션 프레임워크의 HashMap 클래스의 설명에서 이 차이에 대해서 설명한다.

/*
Hash table based implementation of the Map interface. 
This implementation provides all of the optional map operations, 
and permits null values and the null key. 
(The HashMap class is roughly equivalent to Hashtable, 
except that it is unsynchronized and permits nulls.)

...

Note that this implementation is not synchronized. 
If multiple threads access a hash map concurrently, 
and at least one of the threads modifies the map structurally, 
it must be synchronized externally.

...

*/
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
	
	...
	
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

	...

}

3.1 null 사용 유무

HashTable은 null 이 아닌 모든 객체를 key와 value로 사용

HashMap은 null 도 허용

 

3.2 멀티 스레드 유무

HashTable 은 멀티 스레드를 지원

HashMap은 멀티 스레드 미지원

 

3.3 상속의 차이

Hashtable은 Dictionary Legacy 클래스를 확장하지만 다시 엔지니어링 되어 이제 Map 인터페이스도 구현합니다.

HashMap 클래스는 Map 인터페이스를 구현하고 AbstractMap 클래스를 확장합니다.

 

3.4 초기 용량

Hashtable은 11

HashMap은 16

 

3.5 관리 여부

Hashtable은 구현에 거의 변화가 없음

HashMap은 현재까지도 지속적으로 개선

 

결론

멀티 스레드를 사용하지 않는다면 HashMap을 권장한다.

 

 

---

 

 

4. 직접 구현

---

java 1.1의 HashMap을 보고 핵심적인 메서드만 구현해보겠다.

https://docs.oracle.com/javame/config/cdc/ref-impl/fp1.1.2/jsr219/java/util/HashMap.html

HashMap (Foundation Profile, version 1.1.2)

직접 만든 코드와 이를 테스트한 테스트 코드는 GitHub에 올려두었다.

 

import java.util.LinkedList;

public class MyHashMap {

    private static final int DEFAULT_CAPACITY = 16;

    private LinkedList<Node>[] table;
    private int capacity;
    private int size;

    public MyHashMap() {
        this(DEFAULT_CAPACITY);
    }

    public MyHashMap(int capacity){
        this.capacity = capacity;
        this.table = new LinkedList[capacity];
        this.size = 0;
    }

    static class Node{
        String key;
        String value;

        Node(String key, String value){
            this.key = key;
            this.value = value;
        }

    }

    public String put(String key, String value) {

        Node newNode = new Node(key, value);

        int hashCode = getTableIndex(key);

        if(table[hashCode] == null){
            LinkedList<Node> list = new LinkedList<>();
            table[hashCode] = list;
        }

        return addNode(table[hashCode], newNode);
    }

    public String get(String key) {
        int hashCode = getTableIndex(key);

        LinkedList<Node> list = table[hashCode];

        if(list == null) return null;

        for (Node node: list) {
            if(node.key.equals(key)) return (String) node.value;
        }

        return null;
    }

    public boolean containsKey(String key){
        int hashCode = getTableIndex(key);
        LinkedList<Node> list = table[hashCode];

        if(list == null) return false;

        for (Node node: list) {
            if(node.key.equals(key)) return true;
        }

        return false;
    }

    public boolean containsValue(String value){


        for (int i = 0; i < table.length; i++) {
            LinkedList<Node> list = table[i];
            if(list == null) continue;

            for (Node node: list) {
                if(node.value.equals(value)) return true;
            }
        }

        return false;
    }

    public boolean isEmpty(){

        for (int i = 0; i < table.length; i++) {
            if(table[i] != null && !table[i].isEmpty()) return false;
        }

        return true;
    }

    public String remove(String key){
        int hashCode = getTableIndex(key);

        LinkedList<Node> list = table[hashCode];
        for (Node node: list) {
            if(node.key.equals(key)) {
                String oldValue= node.value;
                list.remove(node);
                size--;
                return oldValue;
            }
        }
        return null;
    }

    public int size(){
        return size;
    }

    private String addNode(LinkedList<Node> nodes, Node newNode) {
        size++;
        for (Node oldNode: nodes) {
            if(oldNode.key.equals(newNode.key)){
                String oldValue = (String) oldNode.value;
                oldNode.value = newNode.value;
                return oldValue;
            }
        }

        nodes.add(newNode);
        return null;
    }

    private int getTableIndex(String key) {
        return (key ==null) ? 0 : Math.abs(key.hashCode()) % capacity;
    }


}

 

 

---

자료구조 시리즈

1. 자료구조의 종류와 개념 - 자료구조(1)

2. JAVA ArrayList - 자료구조(2)

3. JAVA LinkedList - 자료구조(3) 

4. JAVA ArrayList와 LinkedList 성능 비교 - 자료구조(4)

5. JAVA Queue 그리고 offer, poll , peek - 자료구조(5)

6. JAVA 왜 Stack 은 Array로, Queue는 LinkedList로 구현 했을까? - 자료구조(6)

7. JAVA Hash 그리고 HashMap 과 HashTable - 자료구조(7)

8. JAVA HashMap 과 HashSet의 성능 비교 - 자료구조(8)

9. JAVA HashMap의 용량은 왜 2의 거듭제곱일까? - 자료구조(9)