자료구조 - Hash

해시

다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값

 

*매핑 : 하나의 값을 다른 값으로 대응시키는 것

탐색

하나 이상의 필드로 구성된 레코드의 집합에서 원하는 레코드를 찾는 것

 

*탐색을 위하여 사용되는 자료 구조 : 배열, 연결 리스트, 트리, 그래프

 

또한 레코드들의 집합을 테이블(Table)이라고 부른다.

 

테이블에서 레코드들을 어떻게 구분할까?

레코드마다 서로 구별되는 키를 가지고 있는데 이것을 탐색키라고 부른다.

---

의미 있는 단위를 이끌어 내기 위해서 하나의 필드를 가진 레코드만으로는 부족하다.

 

따라서 맵이라는 개념을 끌어온다.

맵

탐색키 그리고 탐색키와 관련된 값의 쌍을 말한다.

즉, 두 가지 필드를 가진 키를 가진 레코드 또는 엔트리로 이루어진다.

 

이 두 가지 값은 key, value가 된다.

 

이렇게 맵을 만들었다면 가장 기본적인 연산이 가능해야 한다.

바로 삽입, 삭제, 탐색 연산이다.

 

그렇다면 맵을 구성하는 데에 있어서 어떠한 자료구조를 사용할 수 있을까?

 

먼저 배열이 있다. 배열로 맵을 구성할 경우 배열이 정렬되어 있나를 기준으로 방법이 달라지지만,

여기서는 배열이 정렬되어있고 정렬된 배열에서의 탐색 중 하나인 해싱(hashing)을 알아보겠다.

 

해싱

키 값을 해시 함수(hash function)이라는 수식에 대입시켜 계산한 후 나온 결과를 주소로 사용하여 바로 값에 접근하게 할 수 있는 방법이다.

해시 함수

해시 함수 또는 해시 알고리즘 또는 해시함수 알고리즘 은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

 

이렇게 해시 함수에 의해 계산된 위치에 레코드를 저장한 표를 해시 테이블이라고 한다.

해시 함수는 탐색키를 입력받아 해시 주소를 계산한다.

 

다시 되새겨보자.

 

해시는 해시 함수에 의해 고정된 길이의 주소를 가지는 데이터로 매핑한 값.

탐색은 특정 레코드를 찾는 것.

맵은 탐색키 그리고 탐색키와 관련된 값의 쌍(key, value).

해시 함수는 임의의 길이의 주소를 가지는 데이터를 고정된 길이의 주소를 가지는 데이터로 매핑해주는 함수.

 

해시 테이블의 구조는 버킷과 슬롯으로 되어있다.

버킷의 수가 고정되어 있어서(고정된 길이!) 서로 다른 키를 가지고 있지만 해시 함수에 의해 같은 장소를 가지게 될 수도 있다.

그럴 때 다른 슬롯에 넣어줄 수도 있지만 슬롯도 꽉 차있는 상황에서의 충돌이라면?

 

이러한 상황을 오버플로우라고 한다.

 

출처

https://luv-n-interest.tistory.com/187?category=873976 

[C언어] 자료구조 - Hash 해시 ,해싱-1