맵(map)과 해시 테이블(hash table)

1. Map

• key-value 쌍을 저장하는 ADT
• key는 중복 불가, value는 중복 가능
• 언제 주로 사용하는가
  • 1대1로 대응되는 정보를 저장할 때 ex) 이름 - 전화번호
  • 특정 정보에 대한 카운팅을 할 때 ex) 이름 - 득표 수

 

• 구현체
  • Hash Table
  • Tree 기반 자료구조

 

2. Hash Table (Hash Map)

• 배열과 해시 함수를 이용해서 Map을 구현한 자료구조
  
  • 해시 함수란?
    • 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
    • Hash Table에서 해시 함수는 주로 임의의 데이터를 정수로 변환하는 역할을 담당함
    • 특정 데이터를 해시 함수에 넣어서 나온 정수값을 '해시(hash)'라고 부른다.

 

• 데이터에 접근하는 시간이 상수 시간으로 매우 빠른 편에 속함

 

• 해시 테이블 동작 원리

 

• 해시 충돌
  • key가 다른데 hash가 같을 때
  • key, hash가 다 다른데 hash % map_capacity가 같을 때

 

 

 

 

해시 충돌 해결 방법

 

 1. Seperate Chaining

 

해시 충돌이 발생했을 때 충돌이 일어나고 있는 버킷 옆에 연결 리스트 형태로 새로운 데이터를 저장하는 방식(자바에서 사용하는 방식)

 

2. Open Addressing (linear probing)

 

값을 저장하려는 버킷에 이미 값이 있고 그 값의 key가 현재 저장하려는 데이터의 key와 다를 때 현재 저장하려는 값을 바로 다음 버킷에 저장하는 방식. 

 

ex) 해시 % map의 capacity 결과가 2 -> 2번 버킷에 저장하려고 하는데 이미 값이 있음 -> 해시 충돌이 발생한 것을 확인 -> 3번 버킷에 값을 저장함

 

 

해시 테이블 Resizing

 

데이터가 많이 차게 되면 크기를 늘려주는 것. 자바의 HashMap 같은 경우에는 Map Capacity의 75%가 차게 되면 2배 크기의 새로운 배열을 만들어준다. 그리고 이전에 있었던 데이터를 새로운 Map Capacity로 또 나눠준 후에 새로 만들어진 배열에 값을 집어넣는다.

 

 

 

 

 

 

[Thanks to]

- 유튜브 쉬운코드