[Hash] 해시란?

해시(Hash)

해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행된다. 데이터를 검색할 때 사용할 Key와 실제 데이터의 값(Value)이 한 쌍으로 존재하고, Key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 된다.

즉 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것

해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.

해시 함수, 해시 알고리즘, 해시코드 

데이터의 value값을 배열의 인덱스인 정수로 변환하기 위해서는 일련의 과정이 필용하다. 예를들어 데이터를 문자열로 받게 되었을 때 문자 한글자 한글자 아스키 코드값을 더하는 과정으로 문자열을 정수 값으로 변환할 수 있다.

(만약 hello라는 문자열을 정수형 key값으로 바꾼다면, h+e+l+l+o ->104+101+108+108+111=532라는 해시코드로 변환 할 수 있다.)

개발자마다 해시 함수를 구현하는 건 다르겠지만 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 출력하는 함수라고 생각하면 된다.

해시 충돌

Lee → 해싱함수 → 5
Kim → 해싱함수 → 3
Park → 해싱함수 → 2
...
Chun → 해싱함수 → 5 // Lee와 해싱값 충돌

데이터가 많아지면 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생한다. 

충돌 문제 해결

1. 체이닝 : 연길리스트로 노드를 계속 추가해나가는 방식

2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용한다.

3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피한다.