Hash (해시)

해싱의 기본 개념

해시 함수 (짦게는 그냥 해시)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말한다.
Key - Value 쌍으로 가지는 자료구조의 형태이며, 해쉬 함수는 Hash(k) = V 로 표현할 수 있다. Hash Function을 통해 K를 입력하면, 값 V가 출력된다. 이때 K가 같으면 항상 같은 V가 출력된다.

1. 해시 테이블 (Hash Table)

• key와 value를 가지는 자료구조의 종류 중 하나 (ex. 대표적으로 JS에서 Object, Map, Set 등)
• Hash Function을 통해 빠른 탐색이 가능하다.(키 값을 통해 바로 접근 가능하므로) 따라서 시간복잡도는 O(1)
  

2. 문제 유형

ex) https://programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

위 프로그래머스 문제는 해시 관련 Level 2 문제이다.

* 구현

위 문제의 경우 해시 테이블로 자료구조 Map을 사용하여 구현하였다.

★ 해시는 알고리즘 풀이에 자주 나오기도 하고 타 알고리즘에 비해 어렵지 않은 개념이기 때문에 숙지하자!
또한 대표적인 해시 테이블 Object, Map, Set 의 기본 제공 함수들을 숙지하자!

 

* 참고 https://www.joinc.co.kr/w/man/12/hash

해시 - hash