📌 해시(Hash)

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

해시 함수

• 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.
• 매핑 전 원래 데이터 값을 key, 매핑 후 데이터의 값을 해시 값(value)라고 하며,
• 매핑하는 과정 자체를 해싱이라고 합니다.
• 데이터가 많아지게 된다면, 다른 key 가 같은 해시 값으로 인해 충돌(Collision) 나는 현상이 발생합니다.

해시 테이블

해시 함수를 사용하여 키를 해시 값으로 매핑하고, 해시 값을 index 나 주소 삼아 데이터의 값을 키와 함께 저장하는 자료구조를 해시 테이블이라고 합니다.

하지만, 데이터가 많아진다면 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생합니다. -> 'collision' 현상

📌 해시 충돌

충돌 문제가 있지만 해시 테이블을 사용하는 이유

적은 자원으로 많은 데이터를 효율적으로 관리할 수 있기 때문입니다.

하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(key)들을 유한한 개수의 해시 값으로 매핑함으로써 작은 크기의 캐시 메모리로도 프로세스를 관리할 수 있게 됩니다.

언제나 동일한 해시 값을 return 하고, 해당 index 만 알면 해시 테이블의 크기에 상관없이 데이터에 아주 빠르게 접근할 수 있습니다.

하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해지고, 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해집니다.

해시테이블의 시간복잡도 O(1) - (이진탐색트리는 O(logN))

충돌 해결 방안

체이닝 (Chaining)
체이닝은 해시 테이블의 각 버킷마다 연결 리스트(또는 다른 자료구조)를 사용하여 충돌된 데이터들을 그룹화하는 방식입니다.
충돌이 발생하면 해당 버킷에 연결 리스트에 데이터를 추가하는 방식으로 충돌을 해결합니다.

장점: 구현이 간단하며, 동적인 크기 조절이 용이합니다.
단점: 많은 데이터가 동일한 버킷에 모이면 성능이 저하될 수 있습니다.

오픈 어드레싱 (Open Addressing)
오픈 어드레싱은 해시 테이블 내 다른 위치에 데이터를 찾아서 저장하는 방식입니다.

충돌이 발생하면 다른 위치를 찾아보며 데이터를 삽입합니다.
선형 탐사, 제곱 탐사 등이 이에 해당합니다.

선형 탐사 (Linear Probing)
선형 탐사는 충돌이 발생하면 바로 다음 위치를 확인하고, 계속해서 다음 위치로 이동하며 빈 공간을 찾는 방식입니다. 정해진 고정 폭으로 옮겨 해시값의 중복을 피합니다.

장점: 구현이 비교적 간단합니다.
단점: 클러스터링 문제가 발생할 수 있어 일부 버킷에 데이터가 몰리는 현상이 발생할 수 있습니다.

제곱 탐사 (Quadratic Probing)
제곱 탐사는 충돌이 발생하면 일정 간격만큼 이동하며 빈 공간을 찾는 방식입니다. 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피합니다.

장점: 선형 탐사의 클러스터링 문제를 어느 정도 해결할 수 있습니다.
단점: 특정 패턴에서는 같은 위치를 계속해서 탐사할 수 있어 일부 상황에서 성능 저하가 발생할 수 있습니다.

참고

• https://gyoogle.dev/blog/computer-science/data-structure/Binary%20Search%20Tree.html
• https://yoongrammer.tistory.com/71
• https://choidr.tistory.com/entry/Hash-란

피드백 및 개선점은 댓글을 통해 알려주세요😊