해시

-1) 해시의 개념

해시 : 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조

-> 키를 통해서 데이터에 바로 접근 가능

해시의 특징

1. 단방향으로 작동 -> 값을 통해 키를 찾을 수는 없음
2. 찾고자 하는 값을 O(1)에 바로 찾을 수 있음
3. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야함

+빠르게 원하는 값을 검색할 수 있다는 장점

-2) 해시함수

파이썬에서는 딕셔너리라는 자료형을 제공하고 이는 해시와 거의 동일하기 때문에 해시 함수를 직접 구현할 필요는 거의 없음

해시 함수를 구현할 때 고려해야할 내용

1. 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안됨
2. 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야함

자주 사용하는 해시함수

1. 나눗셈법
   키를 소수로 나눈 나머지를 활용 (모듈러 연산 사용)
2. 곱셈법
   키에 황금비를 곱하고 - 모듈러 1을 취하고 - 매핑할 테이블 크기 m을 곱함

문자열 해싱

키의 자료형이 문자형일 때
각 문자열의 문자들을 적절한 숫자로 변경한 다음 해시 함수를 적용

(a+b)%c = (a%c+b%c)%c
-> 덧셈을 전부한 다음 모듈러 연산을 하면 오버플로우가 발생할 수 있으므로 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로우 방지 가능

충돌 방지

서로 다른 두 키가 해시 함수를 적용해 같은 해시값이 나온 경우

1. 체이닝으로 처리하기
   링크드리스트로 같은 해시값을 가지는 데이터를 연결
   -공간 활용성이 떨어지고 검색 성능도 떨어짐

2. 개방 주소법으로 처리하기
   빈 버킷을 찾아 충돌값을 삽입

코딩테스트 문제에서 해시 문제의 핵심은 키와 값을 매핑하는 과정이다 !
특정 값이나 정보를 기준으로 빈번한 검색을 해야하거나, 특정 정보와 매핑하는 값의 관계를 확인해야 하는 작업이 문제에 있으면 해시를 고려해야 !