[자료구조] 해시 (Hash)

데이터를 일정한 규칙에 따라 고정된 크기 값으로 매핑하는 방법을 해시라고 한다.

 

 

 

출처 : https://s1m0hya.tistory.com/27

 

 

해시를 활용한 자료구조로는 대표적으로 해시테이블, 해시 맵이 있다.

 

 

해시테이블 

 

키를 해시 함수로 처리하여 배열 인덱스를 계산하고, 해당 위치에 데이터를 저장하는 자료구조

아주 빠른 검색 속도를 제공한다. 해시함수를 통하여 해시 주소를 테이블의 인덱스로 사용한다.

* 해시함수 : 키값을 해시 테이블의 주소로 변환하는 함수

 

해시 테이블은 키를 해시 함수로 변환하여 배열의 인덱스를 계산한다.

배열에서 인덱스 접근은 O(1)의 시간복잡도를 가지기 때문에 빠르다.

 

해시 함수는 같은 키에 대해 항상 같은 인덱스를 반환하므로 탐색과정이 필요가 없어서 빠르다.

가장 중요한건 해시 테이블은 충돌이 적게 발생하고, 좋은 해시 함수를 쓸 때 빠릅니다.

 

여기서 충돌이란 서로 다른 키가 같은 해시값(인덱스)를 가지는 현상이다.

이런 경우에는 한 인덱스에 여러 데이터가 몰리면 해당 위치에서 선형 탐색을 해야 한다.

 

* 선형 탐색 : 배열이나 리스트에서 원하는 값을 찾기 위해 처음부터 끝까지 순차적으로 모든 요소를 하나씩 비교하는 가장 기본적인 탐색 알고리즘

 

또한 여기서 좋은 해시 함수란 

✅ 균등한 분포 : 배열(버킷) 안에서 해시값들이 서로 다른 칸에 많이 분포되어 있어야 한다.

 

✅ 입력한 값이 조금만 변해도 큰 변화가 있어야 충돌을 방지 가능

 

✅ 빠르고 효율적인 계산을 활용한 함수 (데이터 처리마다 해당 함수가 사용되므로)

 

해시 맵도 비슷한 원리로 동작된다.

 

해시맵은 Key 마다 Value가 연결되는 자료구조이다.

 

충돌이 생기면 , 즉 같은 인덱스에 데이터가 생기면 그 인덱스 안에 데이터들은

배열로 저장하지 않고 연결리스트 형태로 저장하게 된다.

같은 인덱스가 생길때마다 노드가 추가된다. 이것을 체이닝 방식이라고 한다.

(연결리스트 안에서는 선형순회)

 

또 다른 방법으로는 충돌 발생시 다른 버킷(칸)에 데이터를 저장하는 방식이다.

충돌시 인덱스 +1, +2 등 이렇게 해서 빈 칸을 찾아서 저장한다.

탐색 시에는 해시값으로 첫 위치를 찾고, 원하는 키가 있으면 바로 반환

없다면 다음 위치로 탐색하며 반복한다.

만약 끝까지 없다면 빈 배열칸을 만날때 종료된다.

이것을 개방 주소법이라고 한다.