[알고리즘] 해시

• 해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다.
• 보통은 인덱스를 활용하지만 해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 활용해 데이터에 바로 접근한다.
• 해시의 특징
  • 단방향으로 동작: 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없다.
  • 찾고자 하는 값을 O(1)로 찾음: 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 불필요.
  • 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.
• 해시를 사용하는 경우와 사용하지 않는 경우는 이렇게 차이가 난다.

 

• 해시를 활용하면 순차 탐색할 필요 없이 해시 함수를 활용해 특정 값이 있는 위치를 바로 찾을 수 있어 효율이 좋다.
• 해시 테이블: 키와 대응한 값이 저장되어 있는 공간
• 버킷: 해시 테이블의 각 데이터
• 해시의 특성은 데이터를 저장하고 검색하거나, 보안이 필요한 때에 활용된다.
• 코딩 테스트에서는 특정 데이터를 탐색하는 횟수가 많을 경우 해시를 고려하면 좋다.
• 코딩 테스트에서는 해시 함수를 직접 구현하는 문제가 나오지는 않고, 해시와 거의 동일하게 동작하는 파이썬 딕셔너리 자료형을 활용하여 해시를 쉽게 사용할 수 있다.
• 충돌: 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미. 최대한 방지할 수 있는 해시 함수를 써야한다.