1. 해시 = 🪢

: 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 해시 함수에 의해 얻어지는 값을 해시라고 한다. 해시는 테이블로 활용되어 매우 빠른 데이터 검색으로 사용된다.

2. 해시는 왜 필요할까

• 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 클라우드 등에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다.
• 해시테이블의 시간복잡도 : O(1)

3. 해시 충돌💥 & 해결법

Division, Multiplication 기법 등으로 해시가 가능하다. 단, 서로 다른 두 개의 입력값에 대해 해시 함수가 동일한 출력값을 발생한다면? 이를 해시 충돌이라고 한다.

1) Open Addressing(개방 주소법)

해시 충돌이 일어나면 해시 함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장함. 종류는 3가지가 존재함.

1-1) 선형 프로빙

: 순서대로 검사해서 처음으로 빈 슬롯에 저장하고 끝에 도달하면 다시 처음으로 순환하여 돌아감

• 데이터 탐색 시 : 순차적으로 검색하다가 못 참고 빈 슬록이 나오면 종료

• 단점 🧐

  • linear하다 보니 연속적으로 채워진 슬롯(primary cluster, 따라서 한번 충돌이 나면 집중적으로 충돌이 발생함)가 생기며 점점 더 커진다.
  • 데이터 검색 시간이 클러스터 길이에 비례 -> 효율성 저하

1-2) 이차식 프로빙

: 선형 프로빙에 비해 충돌이 적지만 secondary clustering(처음 충돌한 위치가 같다면 다음 충돌할 위치도 반복적으로 계속 충돌이 나게 됨.)이 발생함.

1-3) 이중 해시

: 충돌이 없을 때는 h1으로 위치를 탐색하고, 충돌이 있으면 h2 mod m만큼 이동하면서 탐색.

2) 체이닝

충돌 시 연결 리스트에 추가하는 방식

: 중복된 해시 값이 있는 경우, 해당 슬롯을 연결 리스트로 저장함. 연결리스트이기 때문에 최악의 경우 수행 시간이 O(n)임. 이런 문제는 트리로 구성하면 완화시킬 수 있음. 장점은 삽입, 삭제가 간단함.

---

+) 언어별 해시 충돌 해결법

• 자바 : 체이닝
• c++ : 체이닝
• python : Open Addressing