[알고리즘] 해시맵(HashMap)

해시(Hash) 개념

해시(Hash)는 Key : Value의 형태를 갖는 자료구조로 

배열과 달리 String 타입이나 다른 어떤 데이터형을 기반으로 자료구조를 접근하고 데이터를 관리할 수 있음

해시는 모든 데이터 타입으로 접근이 가능하다.

 

예시)

N명이 마라톤에 참가하였을 때 N-1명만 완주하여 완주하지 못한 1명의 선수를 찾는 문제가 있다고 하자.

선수를 A, B, C가 있고 A, C 선수만 완주했다고 하면

각 선수가 완주했을 때마다 true로 바꿔주고 이 과정이 끝났을 때도 false로 남아있는 선수를 찾아주면 된다.

finished["A"] = true;
finished["B"] = false;
finished["C"] = true;

 

해시(Hash)의 함수

put

HasMap.put("A", true) 는 곧,
HashMap["A"] = true

 

get

bool fin = hashmap.get("A")는 곧,
bool fin = hashmap["A"] 를 의미함

 

getOrDefault

getOrDefault("A", false) : A가 있다면 A의 Value를 반환하고 A가 없다면, false를 반환

즉, Key가 없을 때의 예외처리를 한 함수 내에서 처리

(만약, hashmap.get("A")를 호출했는데 A라는 키값이 없다면 Error 발생함)

 

어떤 문제에서 해시를 써야할까?

String을 기반으로 정보를 기록하고 관리해야될 때

 

예시) 

1. 완주하지 못한 선수

각 선수의 이름(String Key)을 기준으로 완주 여부 (bool Value)를 관리

2. 신고 결과 받기

게시판 사용자 중 신고 당한 사람 (String Key)을 기준으로 신고자들의 목록(ArrayList<String> Value)을 관리

3. 위장

옷의 종류(상의/ 하의/ 겉옷 -> String Key) 에 따라 각각 몇 개의 옵션이 있는지 카운팅(Integer Value)해야함