99클럽 코테 스터디 11일차 TIL + 706. Design HashMap

오늘의 학습 키워드

• 자바 HashMap 자료구조
• Key-Value 구조 데이터 처리
• 직접 구현을 통한 자료구조 원리 이해

[706. Design HashMap]

문제 요약

HashMap 자료구조를 직접 구현해보는 문제

 

해결 방법

"가변적인 ArrayList"를 사용해서 HashMap 함수를 직접 구현

고정 배열이 아닌 ArrayList 활용

알고리즘 동작 방식

1. put(key, value)
   • 기존 key가 있는지 탐색
   • 있으면 value 덮어쓰기
   • 없으면 새로 추가
2. get(key)
   • key를 찾아서 value 리턴
   • 없으면 -1
3. remove(key)
   • key를 찾아서 삭제

Java 코드 구현

public class MyHashMap {
    ArrayList<ArrayList<Integer>> map;

    public MyHashMap() {
        map = new ArrayList<>();
    }

    public void put(int key, int value) {
        for (ArrayList<Integer> pair : map) {
            if (pair.get(0) == key) { // 키가 있으면
                pair.set(1, value); //값입력
                return;
            }
        }
        //없으면 새로운 객체로 입력
        ArrayList<Integer> newPair = new ArrayList<>();
        newPair.add(key);
        newPair.add(value);
        map.add(newPair);
    }

    public int get(int key) {
        for (ArrayList<Integer> pair : map) {
            if (pair.get(0) == key) {
                return pair.get(1);
            }
        }
        return -1;
    }

    public void remove(int key) {
        for (int i = 0; i < map.size(); i++) {
            if (map.get(i).get(0) == key) {
                map.remove(i);
                return;
            }
        }
    }
}

오늘의 회고 

What?

HashMap 자료구조의 핵심은 Key-Value 매칭 

How?

ArrayList 안에 [key, value] <- [0,1] 형태로 데이터를 저장하여 직접 구현