Hash / Hash Table / Hash Function 및 백준 문제

해시 함수(Hash Function)

• 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수. → 해시 함수를 구현하는 방법에 따라서 서로 다른 문자열이 같은 고정 문자열로 되기도 하는데, 이를 충돌이라고 한다.
• key를 해쉬한 결과를 배열의 index로 사용하게 된다.

해시 충돌(Hash Collision)

• 서로 다른 문자열을 Hash한 결과가 동일한 경우
• 해시 함수를 H()라고 했을 때 , H(s1) = H(s2)인 경우
• Chaining 또는 Open Addressing을 통해서 해결해야 한다.
• index가 겹치면 선형 검색을 하는 경우도 있음 → Hash가 항상 O(1)을 보장하는 것은 아님.

해시 테이블(Hash table)

• Key, Value로 된 쌍을 저장하는 구조

Hash table VS Array

• Array는 처음부터 끝까지 체크 O(n)
• Hash Table은 키와 Value로 체크 O(1)

Hash Tabel이 Array 보다 빠를 수 있는 이유 → Hash Function

key를 index로 변환

Reference

• https://twpower.github.io/139-hash-table-implementation-in-cpp
• https://www.youtube.com/watch?v=HraOg7W3VAM&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=6

 

 

백준 문제집

https://www.acmicpc.net/workbook/view/201