해시 hash

1. 해시는 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료구조다

2. 해시를 사용하려면 메모리 공간이 많이 소모되지만, 매우 빠른 속도로 데이터를 처리할 수 있다

 

특정한 값을 찾고자 할 때는 그 값의 키로 접근할 수 있다. 일반적으로 해시 함수는 module 연산 등의 수학적 연산으로 이뤄져 있어 찾고자 하는 값에 O(1)만에 값에 접근할 수 있다. 그러나 수학적 연산으로 나온 결과값이 키가 되는데 아무대로 중복이 발생할 수 있다. 이때 해시에서 충돌이 발생했다고 표현한다

 

해싱 알고리즘은 나눗셈 법이 가장 많이 활용된다. 입력 값을 테이블의 크기로 나눈 나머지를 키로 이용하는 방식으로, 테이블의 크기는 소수로 설정하는데 충돌 발생을 줄일 수 있기 때문이다. 충돌을 피하는 것은 불가능한데, 충돌을 처리하는 방법은 다음과 같이 두 가지 유형으로 분류할 수 있다

 

1) 충돌을 발생시키는 항목을 해시 테이블의 다른 위치에 저장하는 선형 조사법, 이차 조사법

2) 해시 테이블의 하나의 버킷에 여러 개의 항목을 저장하는 체이닝 기법

 

1. 선형 조사법

- 충돌이 발생했을 때, 바로 다음 위치를 탐색한다