[Map]
- JS 내에 존재하는 key-value 쌍의 데이터를 저장할 수 있는 자료구조로 ADT(Abstract Data Type)라고도 한다.
(ADT란 Abstract Data Type의 약자로 추상적인 자료구조 형태로 구현 방법이 명시되어 있지 않고 자료구조의 특성들과 어떤 동작들이 있는지를 설명하는 형태이다. ADT의 예로는 Map, Stack, Queue 등이 있다.)
- key는 중복될 수 없지만 value는 중복이 가능하다.
- Associative Array, Dictionary(파이썬)라고도 불린다.
- key-value 쌍의 데이터를 매핑할 때, 각기 다른 정보에 대한 카운팅 할 때(투표) 등 사용된다.
Map의 구현체 즉, Map 자료구조를 구현할 수 있는 자료구조에는 Hash Table(해시 테이블)과 Tree-Based(트리)가 있다.
Hash와 Map은 서로 특이한 관계를 갖고 있는데 Hash 입장과 Map의 입장으로 보면 이해가 쉬울 것이다.
<Hash의 입장>
- JavaScript로 Hash를 구현하고 싶다. Hash를 구현하기 위해서는 배열에 해싱된 데이터 값을 저장해야 하는데 다른 언어에서 동작하는 배열과 다르게 JS에서의 배열은 희소배열이다. 희소 배열이란, 배열 내부에 여러가지 자료형을 담을 수 있는 배열이다. 따라서 배열의 한 슬롯, 버킷이 차지하는 공간이 불규칙할 수 있기 때문에 연속적으로 나열되지 않는 자료 구조 형태를 띄고 있을 수도 있다. 그래서 Hash 입장에서는 JS에서 구현되기 위해서 Map이 필요한 존재인 것이다.
<Map의 입장>
- Hash 입장에서 JS 생태계에서는 Map이 자신의 구현 방법이라고 생각하는데 Map 입장에서는 Hash가 자신의 구현체이다. Map은 추상적 자료구조이기 때문에 명확한 구현 방법이 명시되어 있지 않다. 따라서 Hash는 구현체로써 필요한 존재가 된다.
[Hash Table(Hash Map)]
- 배열과 해시 함수를 사용하여 Map을 구현한 자료구조
- 일반적으로 시간 복잡도가 O(n)로 데이터 접근에 매우 빠르다
[Hash Function]
- 임의의 크기를 가지는 타입의 데이터를 고정된 크기의 데이터로 변환하는 함수
- Hash Table(해시 테이블)에서는 임의의 데이터를 정수로 변환하는 역할을 한다.
- 특정 데이터가 Hash Function(해시 함수)를 거쳐서 나온 정수, Hash Function(해시 함수)의 아웃풋 값을 Hash(해시)라고 한다.
정리하자면,
1. Hash Table(해시 테이블)이라는 데이터 저장 방식의 자료 구조가 존재하며 JS에서는 Map 자료구조를 통해 구현한다.
2. 데이터를 Hash Table 내부의 저장 공간인 배열에 저장하기 위해서는 데이터 크기를 압축하고 저장 공간을 지정해 주는 과정이 필요한데 그 과정을 Hashing(해싱)이라고 한다.
3. Hashing 과정에 동작하는 함수가 Hash Function(해시 함수)이다.
4. Hash Function을 통해 나온 값을 Hash(해시)라고 한다.
5. Hash를 데이터 저장 공간인 배열 크기로 모듈러 연산을 한 결과값이 배열 내에 저장될 인덱스를 가리키게 된다.
Hash fucntion의 동작 원리
[Set]
- 데이터의 key 값이 해시 함수를 거쳐서 해시 형태로 반환된다.
- 해시 데이터가 저장될 배열의 크기를 capacity(크기), 배열의 한 칸을 bucket(버킷), slot(슬롯)이라고 한다.
- 해시 데이터를 배열의 capacity로 모듈러 연산을 해준다.
- 모듈러 연산을 통해 나온 값이 배열의 인덱스 값이 되고, 해당 인덱스 즉, 해당 슬롯에 key-value, Hash 값이 저장된다.
[Get]
- 찾고자 하는 데이터의 값이 해시 함수를 거쳐서 해시 형태로 반환된다.
- 해시 데이터를 배열의 capacity로 모듈러 연산을 해준다.
- 모듈러 연산을 통해 나온 값을 통해 배열의 인덱스로 가게 되고, 해당 슬롯에 key 값이 호출한 key 값과 일치한다면 호출하고 그렇지 않다면 종료된다.
[Hash Collision(해시 충돌)]
- key 값은 다르지만 Hash 값이 같은 경우
- key 값과 Hash 값이 모두 다르지만 모듈러 연산 결과값(hash % map_capa)이 같은 경우
- 충돌 처리 방법 : open addressing, separate chaining
Hash Collision 처리 방식
separate Chaining
- 같은 슬롯에서 linked list 형태로 key-value 쌍을 이어서 저장하는 충돌 처리 방식이다.
- 데이터를 호출할 때 Hash 값이 동일하여 같은 슬롯에 데이터가 Linked List 형태로 저장되어 있는 경우는 List를 차례로 조사하여 호출한 key 값과 일치한 데이터를 찾아서 반환한다.
Open Addressing(linear probing)
- 할당받은 슬롯의 다음 인덱스에 해당하는 슬롯을 찾아 데이터를 저장하는 충돌 처리 방식이다.
- Open Addressing 방식으로 처리하였을 경우 특정 key 값의 데이터를 호출할 때에는 key의 Hash 값은 변하지 않기 때문에 기존에 할당 받은 슬롯의 위치로 데이터를 찾으러 간다. 만약 이전에 해당 슬롯의 데이터가 호출되어 나간 경우 해당 슬롯은 비어있을 수도 있다. 이런 경우 오류가 발생할 수 있기 때문에 기존 슬롯 위치의 데이터가 없다면 dummy data를 넣어두어 다음 슬롯까지 찾도록 동작한다.
[Hash Table Resizing]
- 데이터가 많이 차게 되면 저장 공간, Hash Table의 크기를 늘려주어야 한다.
- 데이터를 Set하는 과정에서 key-value 쌍과 함께 저장된 Hash 값을 이용해서 바로 모듈러 연산을 하여 확장된 크기의 저장 공간의 새로운 위치에 데이터를 저장해준다.