Java - map의 개념과 hash table 동작원리

 

 

프로그래머스 코테 lv.1 달리기 경주 풀이 중에 코드는 통과됐는데 시간초과로 안넘어간게 있어서

구글링하던 도중 새롭게 알게된 개념 정리 포스팅. 위 동영상 요약내용임ㅋ

---

Map

- key-value를 저장하는 추상자료형 ADT(Abstract data type)

- 같은 key를 가지는 쌍은 1개만 존재(key 중복x)

- associative array, dictionary라고 불리기도 함

 

ex) 전화번호-이름 저장, 인기투표 할 때의 데이터 저장구조

 

Hash table

- 배열과 해시함수를 사용하며 map을 구현한 자료구조

- *일반적으로 상수시간으로 데이터에 접근하기 때문에 빠름

상수시간이란 bigO표기법에 의하면 O(N)으로 시간복잡도 성능이 가장 좋음

 

Hash function

- 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수

- (hash table에서) 임의의 데이터를 정수로 변환하는 함수

 

인터스텔라라는 값은 hash값이 20033 임

 

Hash function의 기본동작

PUT

데이터가 들어오면 hash function을 돌려 나온 hash값을 *capacity 8로 모듈러 연산을 돌린다.

그래서 나온 값 2로인해 2번 *bucket에 데이터가 저장되는 것.

 

* capacity : 배열 크기

* bucket, slot : 배열 각각의 공간

 

GET

데이터를 get할때도 hash function을 돌려 나온 hash값을 모듈러 연산을 돌림.

그럼 2에 들어있는 값에 equals 비교를 수행하는데, key-value 값이 일치하지 않아 데이터가 없으면 False return.

 

 

여기서 문제! Hash collision 발생

- key는 다른데 hash가 같을 때

- key도 hash도 다른데 모듈러 연산한 hash % map_capa 결과가 같을 때

 

 

해결방법 1. separate chaining

데이터를 해시테이블에 저장하던 중 같은 모듈러 연산 값 도출로 인해 hash 충돌이 발생.

그럼 이미 들어있는 데이터와 input데이터를 비교 후, 값이 다르면 bucket 하나하나를 linked list로 관리한다.

다음 노드를 가르키는 reference를 저장하고 다음 노드에 값을 저장함

 

값을 꺼내올 때는 다음 노드의 key-value pair도 같이 조회해서 일치하는 값을 가져온다.

값을 삭제 후 노드가 비어있으면 다음노드를 땡겨온다.

 

* containsKey : key값이 있는지 boolean형식으로 return

* get : 해당 값이 있으면 key or value값 return  | ex) get("010-1010-1001")  -> 이진수

* containsValue : value값이 있는지 boolean형식으로 return

* delete : 비교 후 일치하면 해당 값을 삭제

 

해결방법 2. open addressing - linear probing

 

저장해야할 bucket에 데이터가 이미 있으면 바로 다음에 비어있는 공간을 활용한다.

get이나 contains operation을 수행할 때는 다음 버킷까지 비교해서 값을 return함.

 

get이 위처럼 작동되기때문에 delete 수행 후 빈 버킷에 더미 값을 넣어주거나 다음 저장돼있는 값을 비어있는 버킷으로 땡겨줘야함.

 

 

Hash table resizing

전체 capacity의 일정부분 이상 bucket이 차면 사이즈를 자동으로 늘려줌.

capacity가 늘어난만큼 16으로 모듈러연산 수행하고 확장 빼애애애앰~~

 

 

Java, Python 사용예제와 비교