[코딩테스트] 1-1. 해시(hash)

해시(hash) ?

(vector, 배열처럼) 번호로 주어진 index가 아닌 문자열 같은 다른 것으로 접근할 수 있는 자료구조

 

- 해시 테이블(hash table) : 저장공간

- 해시 버킷(hash bucket) : 해시 테이블 안의 각 칸

- 해시(hash) : key들이 해시 테이블의 어디 위치에 있을지 정해서 값들을 저장하는 구조

- 해시 함수(hash function) : key들이 몇번째 칸에 들어가야하는 지 결정하는 것

 ㄴ 가급적 서로 다른 칸에 들어갈 수 있도록 함

 

 

if, 같은 해시 버킷에 mapping 되는 경우 = 충돌(collision)

옆으로 버킷들을 연달아 저장할 수 있음

 

c++ STL에서의 hash table

언어 자체에 key:value 쌍을 나타낼 수 있는 데이터 타입이 존재하지 않음

그렇지만, 많은 사람들이 필요로할 것 같은 자료구조는 STL(Standard Template Library)로 제공함

 

-STL은 템플릿 형태이기 때문에 여러가지 데이터형과 class들에 대해 유연하게 적용이 가능한 라이브러리

-> 우리가 다루려 하는 key:value와 같은 자료구조는 map, unordered_map이 존재함

 

c++ 코드로 직접 사용해보기