Java의 HashMap에 대하여 딱 이만큼만

HashMap은 매우 유용한 자료형(?)이다.

 

Java에서 HashMap과 HashTable의 비교하는 글은 인터넷에 많이 있으므로 따로 정리하지 않겠다.

HashMap은 key 와 value로 구성되는데 Map이라는 자료구조를 사용한다.

 

Map은 key와 value을 연결하는 개념의 자료구조이다. 아래과 같은 식이다.

"korea" --> "seoul"
"japan" --> "tokyo"

Java에서 Map은 interface이다.
즉 먼가 내부적으로 구현되어있는 것이 아니고 역활과 기능을 정리한 개념이라는 뜻이다.

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

 

Map은 하나의 key에 하나의 value가 mapping된다.

그외에도 여러가지 개념과 조건들이 있다.

 

하지만 쉽게 생각해서 사용자가 입력한 key를 바로 Map의 구현체에서 key로 사용하기에는 어려움이 많다.

만일 내부적으로 array을 사용한다면 array의 index는 숫자형이 된다.

 

HashMap은 사용자가 입력한 key를 Hash함수로 계산된 값을 index로 사용하는 배열에 value를 담는 개념으로 Map 구현한 자료형이다.

만일 아래와 같이 저장되어야 하고

key = “korea”
value = “seoul”

hash(“korea”) 의 결과가 1이면

arr[1] = “seoul”로 저장한다는 것이다.

 

한줄로 요약하면 arr[hash(“korea”)] = “seoul” 이다.

 

그런데 hash함수와 array로는 모든 key들을 다 포함할 수 없다.

어느 순간부터 hash함수로는 처리못하거나 hash함수의 결과로 같은 값이 나올수가 있는데 이것을 해시충돌(hash collision)이라고 한다.

 

Open-addressing

해시 충돌이 일어나면 테이블 내의 새로운 주소를 계산하여 입력하는 것.

• 선형 탐사(Linear Probing)
• 제곱 탐사(Quadratic Probing)
• 이중 해싱(Double Hashing)

Chaining

해시 테이블의 각 버킷은 연결리스트(또는 트리)로 구성되며 해시 충돌 발생시 리스트에 추가하는 것

Resizing

해시 테이블의 크기를 더 크게 만들고, 새로운 크기에 맞추어 가지고 있던 모든 데이들을 다시 해싱하는 것

자세한 설명은 여기참조

 

java의 HashMap은 이러한 해시충돌을 줄이고자 크게 2가지를 사용한다.

• 보조 해시 함수 여기참조
• Separate Channing

 

일반적으로 위에서 언급한 Map이라는 interface 조건을 충족하기 위해서는 아래의 method들이 제공되어야한다.

• containsKey(String key)
• get(String key)
• remove(String key)
• put(String key, String value)
• toString()

솔찍히 더 있어야한다. https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

 

실제 구현은 아래와 같다.

우선 class를 먼저 선언해야한다.

// MyHashMap. 클래스명으로 나쁘지 않다.
public class MyHashMap { }

 

그리고 class를 사용할 main함수를 구현한다.

온라인 쇼핑몰이라고 하자..

public static void main(String[] args) {
        MyHashMap items = new MyHashMap();
        items.put("Apple", "50000");
        items.put("Banana", "30000");
        items.put("Mellon", "80000");
        items.put("PineApple", "100000");
 
        System.out.println("Initial map" + items);
        System.out.println("The price of Mango is: " + (items.containsKey("Mango") ? items.get("Mango") : "Unknown"));
        System.out.println("The price of PineApple is: " + (items.containsKey("PineApple") ? items.get("PineApple") : "Unknown"));
         
        System.out.println("Removing the price of Banana: " + items.remove("Banana"));
        System.out.println("Removing the price of PineApple: " + items.remove("PineApple"));
        System.out.println("Map after removals: " + items);
}


이제는 하나씩 구현해 나가자. MyHashMap을 구현하기 시작한다.

public class MyHashMap {
    // key가 array의 index가 아닌것 처럼 value도 링크드리스트class 의 value로 들어간다.
    class Entry {
        private String key;
        private String value;
        private Entry next; // Separate Channing를 위한
    }
 
    private final int INITIAL_SIZE = 10;    // 초기사이즈
 
    private Entry[] buckets;
 
    public MyHashMap(){
        buckets = new Entry[INITIAL_SIZE];
    }
 
    // HashMap을 만들려면 해시함수가 필요하다.
    // hashCode() 함수는 int 값을 리턴하는데, 기본적으로 객체의 메모리주소를 사용한다.
    private int hash(String key) {
        return key == null ? 0 : Math.abs(key.hashCode() % buckets.length);
    }
}

 

put함수를 구현한다.

해시함수의 결과값인 index를 이미 사용하고 있다면 링크드리스트의 마지막에 새로운 Entry를 추가한다.

public void put(String key, String value){
    int index = hash(key);
    Entry entry = new Entry();
    entry.key = key;
    entry.value = value;
 
    if(buckets[index] == null) {
        buckets[index] = entry;
    } else {
        Entry curEntry = buckets[index];
        while (curEntry.next != null){
            curEntry = curEntry.next;
    }
    curEntry.next = entry;
}

 

remove함수를 구현한다.

key와 일치하는 Entry를 링크드리스트에서 제거한다.

public boolean remove(String key){
    int index = hash(key);
 
    if(buckets[index] != null){
        Entry curEntry = buckets[index];
        // found in first entry
        if(curEntry.key == key) {
            buckets[index] = curEntry.next;
            return true;
        }
 
        while (curEntry.next != null) {
            if(curEntry.next.key == key) {
                curEntry.next = curEntry.next.next;
                return true;
            }
        }
    }
    return false;
}

 

나머지 함수들을 모두 구현한 최종 소스

public class MyHashMap {
    class Entry {
        private String key;
        private String value;
        private Entry next;
    }
 
    private final int INITIAL_SIZE = 10;
 
    private Entry[] buckets;
 
    public MyHashMap(){
        buckets = new Entry[INITIAL_SIZE];
    }
 
    public void put(String key, String value){
        int index = hash(key);
        Entry entry = new Entry();
        entry.key = key;
        entry.value = value;
 
        if(buckets[index] == null) {
            buckets[index] = entry;
        } else {
            Entry curEntry = buckets[index];
            while (curEntry.next != null){
                curEntry = curEntry.next;
            }
            curEntry.next = entry;
        }
    }
 
    public boolean remove(String key){
        int index = hash(key);
 
        if(buckets[index] != null){
            Entry curEntry = buckets[index];
            // found in first entry
            if(curEntry.key == key) {
                buckets[index] = curEntry.next;
                return true;
            }
 
            while (curEntry.next != null) {
                if(curEntry.next.key == key) {
                    curEntry.next = curEntry.next.next;
                    return true;
                }
            }
        }
        return false;
    }
 
    public String get(String key) {
        int index = hash(key);
 
        if(buckets[index] != null) {
            Entry curEntry = buckets[index];
            while (curEntry.key == key) {
                return curEntry.value;
            }
            curEntry = curEntry.next;
        }
        return null;
    }
 
    public boolean containsKey(String key) {
        int index = hash(key);
 
        if(buckets[index] != null) {
            Entry curEntry = buckets[index];
            while (curEntry != null) {
                if (curEntry.key == key) {
                    return true;
                }
                curEntry = curEntry.next;
            }
        }
 
        return false;
    }
 
    @Override
    public String toString(){
        StringBuilder builder = new StringBuilder();
 
        for(int i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                Entry curEntry = buckets[i];
                builder.append("[Index_" + i + "=");
                while (curEntry != null) {
                    builder.append(curEntry.key + ":" + curEntry.value + ",");
                    curEntry = curEntry.next;
                }
                // removes last comma
                builder.replace(builder.length()-1, builder.length(), "");
                builder.append("],");
            }
        }
 
        builder.replace(builder.length()-1, builder.length(), "");
        return builder.toString();
    }
 
    // Hash function
    private int hash(String key) {
        return key == null ? 0 : Math.abs(key.hashCode() % buckets.length);
    }
 
    public static void main(String[] args) {
        MyHashMap items = new MyHashMap();
        items.put("Apple", "50000");
        items.put("Banana", "30000");
        items.put("Mellon", "80000");
        items.put("PineApple", "100000");
 
        System.out.println("Initial map" + items);
        System.out.println("The price of Mango is: " + (items.containsKey("Mango") ? items.get("Mango") : "Unknown"));
        System.out.println("The price of PineApple is: " + (items.containsKey("PineApple") ? items.get("PineApple") : "Unknown"));
         
        System.out.println("Removing the price of Banana: " + items.remove("Banana"));
        System.out.println("Removing the price of PineApple: " + items.remove("PineApple"));
        System.out.println("Map after removals: " + items);
    }
}

 

참고 :

https://asfirstalways.tistory.com/332

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

https://cjred.net/2018-12-03-how-to-use-java-hashmap-effectively/