hash table

map

• key-value pair들을 저장하는 ADT(추상 자료형)
• 같은 key를 가지는 pair는 최대 한개만 존재
• associative array, dictionary 라고도 불림

map은 언제쓸까?

• 이름: 전화번호 처럼 입력할때
• A빵집에서 가장 맛있는 빵을 투표할 때

hash table

• 배열과 해시함수를 사용하여 map을 구현한 자료구조
• (일반적으로) 상수시간으로 데이터에 접근하기 때문에 빠름 -> 해시충돌 해결법에서 언급

hash function

• 임의의 크기를 가지는 type의 데이터를 고정된 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
• (hash table)에서 임의의 데이터를 정수로 변환하는 함수

hash table의 작동방법(입력)

1. 임의의 문자열을 hash function에 넣는다
2. hash function을 통과한 후 임의의 정수로 변환한다
3. 해시테이블은 n개의 배열을 가지고 있다.(capacity) → 수용할 수 있는 데이터가 n개다.
   1. 0~n-1개의 인덱스를 버켓(슬롯)이라 부른다.
4. 2번에서 나온 숫자를 capacity갯수로 나눈다.(모듈러 연산: 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산)
5. 나온 정수의 위치에 key, value, hash값을 저장한다.

hash table의 작동방법(출력)

1. 찾고 싶은 value의 key를 입력한다

2. hash function에 의해 임의의 수로 출력된다.

3. 2번값을 capacity갯수로 나눈다.(모듈러 연산 : 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산)

   3-1. 입력된 key값과 capacity의 key값이 같은지 확인한다.

4. 테이블의 3번값의 value값을 return 한다.

해시충돌 (hash collision)

• key는 다른데, hash가 같을때
• key, hash도 다른데 hash% map_capa결과가 같을때

해결방법

• open address (linear probing)
  • 충돌이 난다면 다음 버켓에 저장
• separate chaining
  • 링크드 리스트로 vlaue값을 저장
  • 리스트 형태로 여러개의 key-value pair를 연결시키는 방식
    (한집에 n명의 4인가족이 있고, 내가 찾고자 하는 가족을 찾을때까지 선형검색을 한다)
    -> hash table이 일반적이지 않을때 항상 시간복잡도가 상수시간이 아닌것임을 알 수 있다.
• value는 선형검색으로 찾음

hash table resizing

• 데이터가 많이 차게 되면 크기를 늘려줘야 한다.