🚀 What I Will Learn

• 해시(Hash)에 대해 이해하기
• 해시가 활용되었을 때 효과적인?! 상황에 대해 공부하기

해시(Hash)란? 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조

---

해시(Hash)

1️⃣ 해시(Hash)란?

• 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조
• 해시를 사용하면 메모리 공간이 많이 소모되지만
• 매우 빠른 속도로 데이터를 처리할 수 있다
• 빠르게 데이터에 접근할 수 있다는 점에서 데이터베이스 등의 소프트웨어에서 활용된다

✔️ 해시(Hash)의 원리

• 예시)
  • 특정한 값 n이 입력되었을 때 10을 나눈 값을 Key로 접근

• 특정한 값(Value)를 찾고자 할 때는 그 값의 키(Key)로 접근할 수 있다
• 일반적으로 해시 함수는 모듈 등의 수학적 연산으로 이루어져 있으므로
• O(1)만에 값에 접근할 수 있다

✔️ 해시(Hash)의 충돌

• 해시 함수의 입력 값으로는 어떠한 값 등 모두 들어갈 수 있지만
• 해시 함수를 거쳐 생성되는 키(Key)의 경우의 수는 한정적이기 때문에 키(Key) 중복이 발생할 수 있다
• 해시 테이블에서 키(Key)가 중복되는 경우 충돌(Collision)이 발생했다고 표현한다

✔️ 해싱(Hashing)

• 해싱 알고리즘은 나눗셈 법(Division Method)이 가장 많이 활용된다
• 입력 값을, 데이블의 크기로 나눈 나머지를 키(Key)로 이용하는 방식
• 테이블의 크기는 소수(Prime Number)로 설정하는 것이 효율성이 높다

---

2️⃣ 충돌을 처리하는 방법

충돌을 처리하는 방법은 두 가지 유형으로 분류할 수 있다

1) 해시 테이블의 다른 위치에 저장

: 충돌을 발생시키는 항목을 해시 테이블의 다른 위치에 저장

• 선형 조사법, 이차 조사법 등

(1) 선형 조사법

• 해당 자리에 데이터가 있다면 그 다음 자리에 데이터 추가
• 그 다음 자리에도 데이터가 있다면 또 그 다음 자리에 추가

• 선형 조사법의 단점
  • 충돌이 발생하기 시작하면, 유사한 값을 가지는 데이터끼리 서로 밀집되는 집중 결합 문제가 존재
  • [해시 테이블의 크기]가 비약적으로 크다면, 다시 말해 메모리를 많이 소모한다면 충돌이 적게 발생하므로 매우 빠른 데이터 접근 속도를 가질 수 있지만
  • 일반적인 경우, 해시 테이블의 크기는 한정적이므로 충돌이 최대한 적게 발생하도록 해야한다

(2) 이차 조사법

• 선형 조사법을 약간 변형한 형태로 키 값을 선택할 때 완전 제곱수를 더해 나가는 방식
  • 해당 자리에 데이터가 있다면 1제곱한 값을 더한 위치에 데이터 추가
  • 또 해당 자리에 데이터가 있다면 2제곱한 값을 더한 위치에 데이터 추가

🔹 조사법의 테이블 크기 재설정

• 일반적으로 선형 조사법, 이차 조사법 등의 조사법에서 테이블이 가득 차게 되면 테이블의 크기를 확장하여 계속해서 해시 테이블을 유지할 수 있도록 한다

2) 버킷(Bucket)에 여러 개의 항목을 저장

: 해시 테이블의 하나의 버킷(Bucket)에 여러 개의 항목을 저장

• 체이닝(Chaining) 등

(3) 체이닝(Chaining)

• 연결 리스트를 활용해 특정한 키를 가지는 항목들을 연결하여 저장
• 연결 리스트를 사용한다는 점에서 삽입과 삭제가 용이
• 테이블 크기 재설정 문제는 동적 할당을 해결 가능하지만
  • 동적 할당을 위한 추가적인 메모리 공간이 소요된다는 단점이 있다

---

✨ tl;dr

• 해시(Hash)는 이론적으로 데이터의 삽입과 삭제에 있어서 𝑂(1)의 시간 복잡도를 가진다
• 해시는 데이터베이스 인덱싱 및 정보보안 관련 모듈 등에서 굉장히 다양하게 사용되고 있다

시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것을 의미