[자료구조] - 해시(Hash)

해시

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

• 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생 'collision' 현상

그래도 쓰는 이유?

적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능

• 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능
• 해시테이블의 시간복잡도 O(1) - (이진탐색트리는 O(logN))

충돌 문제 해결

1. 체이닝
   연결 리스트로 노드를 계속 추가해 나가는 방식
2. Open Addressing
   해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용
3. 선형 탐사
   정해진 고정 폭으로 옮겨 해시값의 중복을 피함
4. 제곱 탐사
   정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함