[자바] 리트코드 706 - Design HashMap

HashMap은 Map을 구현한 클래스이기 때문에, <key, value> 형태로 데이터가 들어간다. 항상 주어진 라이브러리를 사용만 했기 때문에, 어떻게 구현되어 있는지에 대해서는 고민해보지 않았는데 덕분에 bucket이라는 개념도 알게 되었다. 

이번 문제는 공부하는 차원에서 푼 것이기 때문에, 바로 풀이들을 좀 찾아 보았다. 

 

첫 번째 Solution

어차피 key의 범위가 0부터 1,000,000, 즉 백만이기 때문에 배열을 생성해서 구현해도 문제가 없다. 

MyHashMap 클래스 생성 시에, 크기 1000001인 배열을 선언한 다음에 index를 키값처럼 생각해서 구현하면 된다. 

• 시간 복잡도 : O(1) (get, remove, put 모두에 해당된다)
• 공간 복잡도 : O(n)

class MyHashMap {
    
    int[] map;
    
    /** Initialize your data structure here. */
    public MyHashMap() {
        
        map = new int[1000001];
        Arrays.fill(map, -1);
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        map[key+1] = value;
        
    }
    
    /** Returns the value to which the specified key is mapped, 
    or -1 if this map contains no mapping for the key */
    public int get(int key) {
        return map[key+1];
        
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        map[key+1] = -1;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

 

 

두 번째 Solution

조금 더 복잡하다. Bucket의 개념을 이용하는데, Bucket을 구현하기 위해서는 LinkedList를 사용한다. 

이 풀이법은 아래 블로그를 참조했다. 정말 잘 설명해놓았다! 

developer-hongjoo.tistory.com/33?category=815694

[알고리즘] Hash Table 구현하기

읽으면서 실제 HashMap  구현 로직과 헷갈리지 않도록 유의해야 할 부분이 있다고 생각했다. 

현재 로직에서는 key값이 위치할 bucket의 index를 결정짓기 위해  임의로 key를 BUCKET_CAPACITY로 나누었다. 이처럼 하면 BUCKET_CAPACITY에 따라 시간 복잡도가 달라질 것 같은데, 실제 Hash Function이 어떻게 구성되는 지도 궁금하다. 

※ 만약 BUCKET_CAPACITY = 2라면, bucket 배열 하나에 최대 2개의 node만 들어갈 수 있기 때문에, 성능이 좋아질 수 밖에 없다. 

index	key
0	0~99
1	100~199
~	~
9,999	999,900~999,999
10,000	1,000,000

 

두 가지 내가 수정한 부분이 있다.

첫 번째로, remove()에서 bucket[index]에 달린 노드가 딱 1개였을 때에는 bucket[index] 자체를 null로 초기화하여서(line #89) put할 때에 아무 문제 없이 new Bucket으로 값을 집어넣을 수 있도록 했다. 

두 번째로, bucket 배열의 크기를 10001로 늘렸다. 들어올 수 있는 값의 범위가 [0,1000000]면 1000000이 key로 들어왔을 때에는 index가 10000이어야 하기 때문이다. 

 

현재 로직상에서는 시간 복잡도와 공간 복잡도가 trade-off 관계에 있고, BUCKET_CAPACITY에 따라 시간 복잡도가 크게 바뀔 것 같다. 

• 시간 복잡도 :  O(BUCKET_CAPACITY) 
• 공간 복잡도 :  O(n/BUCKET_CAPACITY)  ← 여기에서의 n은 key로 들어올 수 있는 최대값

class MyHashMap {

    static final int BUCKET_CAPACITY = 100;
    static Bucket[] buckets;
    
    class Bucket{
        Node node;
        public Bucket(Node node){
            this.node = node;
        }
    }
    
    class Node{
        int key;
        int value;
        Node next;
        
        public Node(int key, int value, Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    
    /** Initialize your data structure here. */
    public MyHashMap() {
       buckets = new Bucket[10001];     
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        int index = key/BUCKET_CAPACITY;
        
        if(buckets[index] == null){
            buckets[index] = new Bucket(new Node(key,value,null));
        }else{
            Node node = buckets[index].node;
            
            
            while(node!=null){
                if(node.key==key){
                    node.value = value;
                    return;
                }
                
                if(node.next==null){
                    node.next = new Node(key,value,null);
                    return;
                }
                
                node = node.next;
            }
        }
    }
    
    /** Returns the value to which the specified key is mapped, 
    or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int index = key/BUCKET_CAPACITY;
        
        if(buckets[index]==null){
            return -1;
        }else{
            Node node = buckets[index].node;
            while(node!=null){
                if(node.key==key) return node.value;
                node = node.next;
            }
            
            return -1;
        }
    }
    
    /** Removes the mapping of the specified value key 
    if this map contains a mapping for the key */
    public void remove(int key) {
        int index = key/BUCKET_CAPACITY;
        
        if(buckets[index]==null) return;
        else{
            Node node = buckets[index].node;
            Node prev = null;
            
            while(node!=null){
                if(node.key==key){
                    if(prev==null){ //딱 첫번째 노드가 remove하려는 값일때
                        //Bucket에 node가 딱 1개였을 때는, 
                        //Bucket 자체도 clear 시켜준다. 
                        buckets[index].node = node.next;
                        if(node.next==null) buckets[index] = null; 
                        return;
                    }else{
                        prev.next = node.next;
                        return;
                    }
                    
                }else{
                    prev = node;
                    node = node.next;
                }
            }
        }
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */