해시(hash) 와 해시 충돌(Hash Collision)

해시란?

해시는 임의의 데이터를 고정된 길이의 값으로 변환하는 과정을 말합니다. 이렇게 변환된 값은 해시 값 또는 해시 코드라고 불리며, 주어진 입력 데이터에 대해 유일하게 식별됩니다. 해시 함수를 통해 데이터를 해시 값으로 변환하면, 이 해시 값은 원래 데이터를 대표하는 짧고 고유한 식별자가 됩니다. 해시 함수와 테이블을 가집니다.

해시함수란?

해시 함수는 데이터를 해시 값으로 변환하는 알고리즘입니다. 이 함수는 입력 데이터를 고유한 해시 값으로 매핑하는 역할을 합니다.

해시테이블란?

해시 테이블은 해시 함수를 사용하여 데이터를 저장하는 자료구조입니다.

해시충돌이란?

해시 충돌(Hash Collision)은 해시 함수에서 서로 다른 입력 데이터가 같은 해시 값(출력값)을 생성하는 현상을 말합니다. 해시 함수는 일반적으로 무한한 입력 공간을 유한한 해시 값 공간으로 매핑하기 때문에, 다양한 입력 데이터들이 동일한 해시 값으로 매핑될 수 있습니다.

충돌 해결 방법:

1. 체이닝기법

   1.충돌이 발생하면 같은 해시 값에 대해 연결 리스트 형태로 데이터를 저장합니다.
   2.간단하고 구현하기 쉽지만, 메모리 소비가 크고 연결 리스트의 길이가 길어지면 검색 시간이 길어질 수 있습니다.

2. 개방 주소기법

   1.충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장합니다.
   2.선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 더블 해싱(Double Hashing) 등의 기법을 사용하여 충돌을 해결합니다.