Hash란

해시(hash)란 단방향 암호화 기법으로 해시함수(해시 알고리즘)를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미한다.

해시함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정을 해싱(hashing)이라고 한다.

 

Collosion이 일어날 경우 해결방법

• Chaining 
  • 충돌이 일어날 경우 동일한 버킷에 저장하는데 이를 포인터로 리스트 형태로 저장
  • 최악의 경우 한 버킷에 몰리게 되며 시간 복잡도로 따지면 O(n)이다.
• Open Addressing
  • 그 다음 비어잇는 주소에 저장하는 방식
  • 비어있는 주소를 찾는 방식을 탐사 한다고 하는데 선형함사, 제곱탐사, 이중해싱이 있다.