---

해시(Hash)

---

1. 해시

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

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

• 하지만, 결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생한다.(collision 현상)

2. 해시 테이블을 쓰는 이유

• 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해

• 하드디스크, 클라우드 등에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다.

• 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해진다.

• 시간복잡도 : O(1)

3. 충돌 문제 해결

• 체이닝
  -> 연결리스트로 노드를 계속 추가해나가는 방식(제한 없이 계속 연결 가능하지만 메모리 문제가 발생할 수 있다.)

• Open Addressing
  -> 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용한다.(해당 키 값에 저장되어 있으면 다음 주소에 저장한다.)

• 선형 탐사
  -> 정해진 고정 폭으로 옮겨 중복을 피한다.

• 제곱 탐사
  -> 정해진 고정 폭을 제곱수로 옮겨 중복을 피한다.