[알고리즘] 해시 Hash

Hash 

Key : Value 의 형태를 갖는 하나의 자료구조

 

ex) 해시 = 전화번호부. 이름 : key, 번호 : value

 

해시의 특징 : 모든 데이터 타입으로 접근이 가능하다. 

 

해시 문제들

백준 10816 숫자 카드 2

프로그래머스 - 완주하지 못한 선수

신고 결과 받기

위장

 

예) 프로그래머스 - 완주하지 못한 선수

n명이 마라톤 참가. n-1명만 완주. 완주하지 못한 1명을 찾는 문제

Hash를 사용하면 아주 간단하게 해결 가능

HashMap 생성. 

HashMap.put("A", true);

HashMap["A"] = true; 와 똑같은 동작

bool fin = hashmap.get("A");

bool fin = hashmap["A"]; 와 같은 동작

getOrDefault 함수 getOrDefault("A", false)

A가 있다면, A의 Value를 반환. A가 없다면, false를 반환

: Key가 없을 때의 예외처리를 한 함수 내에서 처리해주는 것. 

 

get / put / getOrDefault 만 알아두면 

 

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

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

 

1. 완주하지 못한 선수

선수 이름 -> 완주 여부

String -> Hash

String Key : bool Value 해시맵 만들어 풀기

2. 신고 결과 받기

게시판 사용자. 신고 당한 사람을 기준으로 신고자들의 목록을 관리해야. 

신고 당한 사람의 이름이 String -> Hash를 써야

String Key : ArrayList<String> Value 로 신고자 목록 만들기

3. 위장

옷의 종류에 따라 몇 개의 옵션이 있는지 

옷의 종류가 정수가 아니라 얼굴 / 상의 / 하의 / 겉옷

String Key : Integer Value 만들어

 

String을 기준으로 정보를 기록하고 관리하려면 단순 배열을 쓸 수 없으니 Hash를 활용하자. 

 

cf) 자료구조 Map ? 

왜 String은 자꾸 배열에 담을 수 없다함? 

해시와 딕셔너리 차이? 

 

배열 & 해시 테이블 시간복잡도 비교

단순 배열을 사용해 하나씩 비교하면서 원하는 값을 찾으려면 Linear Time(선형시간) O(n) 이 걸린다. 

아이템이 많을 수록 찾는 시간도 오래걸림. 

Hash Table의 시간복잡도는 O(1) 즉, Constant Time(상수시간)

어떤 항목을 찾아도 소요되는건 한 단계로 같음. 따라서 배열에 비해 월등히 빠르다. 

 

그런데 애초에 Hash Table의 내부에도 배열같은 구조가 있다. 그러면 어떻게 Hash Table이 더 빠를 수 있는가? 

Hash Function 해시 함수 때문!

해시함수가 내가 저장하고 싶은 key를 숫자(index)로 바꿔버림. 

Key를 해시함수에 넣고, 해시함수가 준 숫자(index)에 Value를 저장하는 방식. 

값을 찾을때는 바로 index를 찾아 value를 가져옴. 

그러나, 서로 다른 key에 대해 해시함수가 동일한 index 값을 부여해버리는 경우가 있음. 이게 바로 Collision(해시충돌)

충돌을 해결하는 방법은 여러가지. 그중 하나는 해당 index에 또다른 배열을 넣는 것. 거기에 두 쌍을 저장. 

key를 해시함수에 보내고 index 숫자를 주면 해당 index로 가서 해당 값을 찾을때까지 선형검색을 하게 됨. 

이 때문에 해시테이블 검색이 언제나 상수시간인 것은 아님. 충돌이 있을 수 있고, 그 경우 선형검색을 해야하니깐. 

그치만 평균적으로 해시테이블의 시간복잡도는 O(1)에 수렴한다고 볼 수 있음. 

 

이미 대부분의 언어에서 해시테이블과 해시함수는 이미 구현이 되어있음. Swift에서는 어케 쓰지? 

 

 

 

---

참고 : youtube - 개발자로 취직하기, youtube 노마드코더 - 해시테이블,