[TIL] 스파르타) CS 강의 수강 (HashMap, HashSet)

 

 > 8강. 자료구조를 수강하고, 이전에 잘 몰랐던 부분을 이해한대로 정리해보았다.

 

학습 키워드: data structure, hashmap, chaining, open addressing, hashset

 

1. HashMap

1) What is it?:

 - Key-value로 맺어진 pair 를 저장하는 Map 자료 구조에서 hash가 더해진 방식이다.

 

2) How does it work?:

출처: 강의 노트

 - 임의의 길이를 가진 key 값이 주어지면 이 key를 hash 함수를 통해 고정 길이를 가지는 hash로 변환한다. 변환된 hash값을 이용해 hash table의 해당 hash 주소에 value를 저장하는 방식으로 동작한다.

 - key와 value가 모두 고유한 일반적인 map과는 다르게, hashmap의 경우엔 value의 중복을 허용한다.

 - 위의 이미지 처럼 간혹 서로 다른 key의 hash 함수로 도출된 hash 값이 동일한 경우가 생긴다. 이를 hash의 collision이라고 부른다. Hash 충돌 현상을 방지하는 대표적인 방법으로는 chaining과 open addressing이 있다.

 - chaining: hash 테이블을 array 대신 LinkedList로 구현하는 방법이다. Hash collision시 주소에 새로운 노드를 연결(chaining)한다.

 - open addressing: hash 함수로 얻은 hash 주소 외에 다른 주소에 자료를 저장하는 것을 허용하는 방식이다. Linear probing, double hashing 등 여러가지 probing strategy가 존재한다.

 - linear probing: h(k, i) = (h'(k) + i) % m 으로, h'(k)가 hash 함수, m이 테이블의 크기다. 매번 중복이 발생할 때 마다 다음 빈 슬롯을 찾아 데이터를 저장하는 방식인데, 이런 식으로 하면 테이블이 커져감에 따라 연속적으로 데이터가 기록되는 구간이 생기는 clustering 현상이 발생하고, 그 구간이 점점 커지면서 탐색 시간이 점점 길어지는 현상이 발생한다.

 - double hashing: h(k, i) =(h1(k) +i·h2(k)) % m 으로, h1 과 h2 로 두 개의 hash 함수를 운용하는 방법이다.

 - key 값을 통해 데이터를 지울 때 여러모로 난점이 많다.

 

3) Why use it?:

 - HashMap을 사용하면 적은 메모리로도 많은 양의 데이터를 관리할 수 있으며, 시간 복잡도가 O(1)로 상당히 빠르다.

 

2. HashSet

1) What is it?:

 - Set은 중복과 순서가 존재하지 않는, 수학에서의 집합과 같은 개념의 자료구조다. Set의 기본 구현은 프로그래밍 언어별로 다른데, Java의 경우 hash table을 이용하는 HashSet, Binary Search Tree를 이용하는 TreeSet, 순서를 추가해주는 LinkedHashSet 등으로 구현되어 있다.

 

2) How does it work?:

 - 위의 세 가지 구현중 가장 빠른 것은 HashSet이다. 저장할 데이터의 hash 값을 구하고, bucket이라고 불리우는 공간에 해당 데이터를 저장한다. Hash로 저장하는 방식답게 hash값으로 변환 -> 조회로 시간 복잡도가 O(1) 이어서 look up 속도가 매우 빠르다. 중복이 있을 수 없기 때문에, null 값 또한 단 하나만 존재할 수 있다. 반면에 HashMap에서는 key값에 null의 중복이 있을 수 없지만, value의 null은 중복이 가능하다.

 

3) Why use it?:

 - 순서와 상관없이 데이터를 저장하지만, 중복은 없어야하는 경우에 주로 사용된다. 예를 들면, '이벤트 응모자 목록'은 응모자의 응모 순서와 관계없이 누가 응모했는지만 알면 되지만 응모자의 중복이 없어야한다.

 

 

--

 

REFERENCES:

 

8강. 자료구조의 동작과 활용 | Notion

 > 강의 노트, 8강. 자료구조~

Separate Chaining Collision Handling Technique in Hashing - GeeksforGeeks

 > GeeksForGeeks, chaining 참고

Difference between HashMap and HashSet - GeeksforGeeks

 > GeeksForGeeks, HashMap vs HashSet

Index of /6.006/fall11/lectures

 > MIT, 'lecture10.pdf' open addressing 부분 일부 참고