[LeetCode] - 706. Design HashMap

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Design HashMap" 문제입니다.

--> https://leetcode.com/problems/design-hashmap/description/

 

문제 : 

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class :

• MyHashMap() initializes the object with an empty map.
• void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

---

Example 1 :

Input : ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] Output : [null, null, null, 1, -1, null, 1, null, -1]

Explanation :

MyHashMap myHashMap = new MyHashMap();

myHashMap.put(1, 1); // The map is now [[1,1]]

myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]

myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]

myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]

myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)

myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]

myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]

myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

 

Constraints :

• 0 <= key, value <= 10^6
• At most 10^4 calls will be made to put, get, and remove.

---

이 문제는 내장 해시 테이블 라이브러리를 사용하지 않고 해시맵을 구현하는 것입니다. 해시맵은 키-값 쌍을 저장하는 자료구조로, 평균적으로 O(1) 시간 복잡도로 데이터를 검색, 삽입 및 삭제할 수 있습니다.

class MyHashMap {
    private List<Integer> keys;
    private List<Integer> values;    
    
    public MyHashMap() {
        this.keys = new ArrayList<>();
        this.values = new ArrayList<>();
    }
    
    public void put(int key, int value) {
        int index = keys.indexOf(key);
        if (index != -1) {
            values.set(index, value); // Update value if key already exists
        } else {
            keys.add(key);           // Add new key
            values.add(value);       // Add new value at the same index
        }
    }
    
    public int get(int key) {
        int index = keys.indexOf(key);
        if (index != -1) {
            return values.get(index); 
        } else {
            return -1;
        }
        
    }
    
    public void remove(int key) {
        int index = keys.indexOf(key);
        if (index != -1) {
            keys.remove(index);
            values.remove(index); 
        }
    }
}

 

이 코드는 두 개의 리스트(keys와 values)를 사용하여 해시맵을 구현합니다. keys 리스트는 키를 저장하고, values 리스트는 키에 대응하는 값을 저장합니다. 두 리스트의 인덱스를 통해 키와 값을 연결합니다.

주요 메소드 설명

1. 생성자 (MyHashMap) :
   • keys와 values 리스트를 초기화합니다.
2. put 메소드 :
   • 키가 이미 존재하는지 keys 리스트에서 찾습니다.
   • 존재하면, 해당 인덱스의 값을 업데이트합니다.
   • 존재하지 않으면, 키와 값을 각각 keys와 values 리스트에 추가합니다.
3. get 메소드 :
   • 키가 존재하는지 keys 리스트에서 찾습니다.
   • 존재하면, 해당 인덱스의 값을 반환합니다.
   • 존재하지 않으면, -1을 반환합니다.
4. remove 메소드 :
   • 키가 존재하는지 keys 리스트에서 찾습니다.
   • 존재하면, 해당 인덱스의 키와 값을 모두 제거합니다.

이 구현은 리스트를 사용하여 해시맵을 만들지만, 시간 복잡도가 O(n)으로 효율적이지 않습니다. 키를 찾는 데 O(n) 시간이 걸리기 때문입니다. 그래서 사실상 제 코드는 아주 별로인 코드입니다. 

---

생각해 보니 그냥 바로 배열을 써도 될 것 같아서 간단하게 개선해 봤습니다 : 

class MyHashMap {
  int[] map = new int[1000001];

  public MyHashMap() {
    Arrays.fill(map, -1);
  }
  
  public void put(int key, int value) {
    map[key] = value;
  }
  
  public int get(int key) {
    return map[key];
  }
  
  public void remove(int key) {
    map[key] = -1;
  }
}

 

 

이 코드는 배열을 사용하여 해시맵을 구현합니다. 키의 범위가 0부터 1,000,000까지로 제한되어 있기 때문에, 배열의 인덱스를 키로 사용하여 값을 저장할 수 있습니다. 이렇게 하면 해시 충돌 문제를 고려할 필요 없이 O(1) 시간 복잡도로 접근할 수 있습니다.

주요 메소드 설명

1. 생성자 (MyHashMap) : 
   • 크기가 1,000,001인 배열 map을 초기화합니다.
   • map 배열의 모든 요소를 -1로 초기화합니다. 이는 해당 인덱스에 값이 없음을 나타냅니다.
2. put 메소드 :
   • 주어진 키에 해당하는 인덱스에 값을 저장합니다.
   • map[key] = value로 구현됩니다.
3. get 메소드 :
   • 주어진 키에 해당하는 인덱스의 값을 반환합니다.
   • 값이 없으면 -1을 반환합니다.
4. remove 메소드 :
   • 주어진 키에 해당하는 인덱스의 값을 -1로 설정하여 값을 제거합니다.

이렇게 해서 시간, 공간 복잡도가 모두 O(1) 인 이쁜 코드가 나옵니다.

---

내 코드들의 Runtime 결과