[자료구조] 해시 - (1) 개념

해시 - (1) 개념

해시란 무엇인가?

• 데이터를 관리하고 유지하는 자료구조
• 리소스 < 속도 (리소스를 포기하고 속도를 취한 자료구조)
• 키(key)는 해시 함수(Hash function)을 통해 해시(hash) = 배열의 인덱스 로 변경이 되고, 해시 = 배열의 인덱스는 값(value)와 매칭되어 저장소(storage)에 저장이 된다

Hash Table의 요소

• 키(key) : 고유한 값, 해시의 input
• 해시 함수(Hash function) : 키를 해시로 바꿔주는 역할
• 해시(Hash) : 해시 함수의 결과물, 저장소에서 값과 매칭되어 저장된다 = 배열의 인덱스
• 값(value) : 저장소에 최종 저장되는 값

 

해시 Big O Notation

각 조회의 평균 시간은 테이블에 저장된 요소 수와 관련이 없다.

• 삽입: O(1)
• 삭제: O(1)
• 검색 : O(1)

해시의 주요 용도

1. 검색이 많이 필요한 경우
2. 저장, 삭제, 읽기가 빈번한 경우
3. 캐쉬 구현시 (중복 확인이 쉽기 때문)

해시의 장점

• 해시는 자원(리소스)을 이용하여 속도를 높인다
• 어떤 값을 찾으려고 할 때 전체 원소에 대해 루프문을 실행시키지 않고 어떤 키에 해당하는 값의 주소를 테이블에서 찾아주는 함수이므로  조회 속도가 매우 빠르고 간단

해시의 단점

• 충돌이 발생할 수 있다.
  • 123이 이미 인덱스 1에 들어가 있는 상황
  • 192도 나누기 100을 거치면 인덱스가 1인 값 자리에 들어가야 하는데 이미 123이 들어가 있음 → 충돌

충돌에 대처하는 두가지 방법

• 체이닝(Chaining) 또는 separate Chaining

• 해당 인덱스에 이미 값이 있으면 그 뒤에 체인으로 연결
• 리스트 같은 자료구조를 이용

• 선형 탐사(Linear Probing)

• 체이닝을 하면 너무 자원을 많이 차지함(테이블을 쓰라고 할당해놨는데 테이블은 안쓰고 계속 잇기만 하고 있음)
• 선형 탐사 방법은 "이미 만들어 놓은 버켓을 먼저 소모하자"
• 맨 마지막 데이터인 100이 해시함수를 거치면 인덱스 1인 자리에 값으로 들어가야하는데 이미 123이 자리를 차지하고 있으므로 다음 인덱스인 2의 값으로 넣어준다
• 만약 이렇게 테이블이 또 꽉차면 데이터가 더 들어오려고 할 때 자리가 없어진다 그러면 테이블 리사이징을 한다
• 테이블의 크기를 늘린다음 기존의 데이터를 해시함수로 보내버리고 다시 테이블을 재정렬한다