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

기본적인 것만 알아보자.

 

우선 해시를 알기 전에 알아야 할게 있다.

탐색(search) 란 것이 무엇인지 알아야 하죠. 국어사전의 뜻과 같이 무엇인가를 찾는 작업이다.

그렇다면 컴퓨터에서는 뭘 찾는 것을 탐색이라고 말할까?

 

–탐색을 위하여 사용되는 자료 구조

•배열, 연결 리스트, 트리, 그래프 등

 

바로 하나 이상의 필드로 구성된 레코드(record)의 집합에서 원하는 레코드를 찾는 것을 말한다.

 

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

 

그렇다면 레코드들의 집합인데 서로 어떻게 구분할까??? 

 

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

 

여기까지 탐색을 알아보았다.

 

---

 

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

 

그래서 맵(map)이라는 개념을 끌어온다.

 

맵이라는 것은 탐색키와 탐색키와 관련된 값

 

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

 

즉 2가지 값은 키(key), 값(value) 이 된다.

 

이제 맵을 만들었으면  가장 기본적인 연산이 가능해야겠지??

 

삽입(insert), 삭제(delete), 탐색 연산이 가능해야한다.

 

그렇다면 어떠한 자료구조를 통해 맵을 구성해야할까?

 

배열이 가장 간단해보인다. 배열로 맵을 구성할 경우 배열이 정렬되어 있나를 기준으로 방법이 달라지지만

 

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

 

해싱은 키 값에 산술적인 연산을 적용하여 항목이 저장될 위치, 즉 인덱스를 계산하는 방식이다.

 

이 때, 키값에서 항목의 위치를 계산하는 함수를 해시 함수(hash function)라고 하고

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

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

 

 

 

해시테이블의 구조는 버킷(bucket)과 슬롯(slot)으로 이루어진다.

 

버킷의 수가 고정되어있어서 서로 다른 키를 가지고 있지만 해시함수에 의해 같은 장소를 가리킬 수 있다.

 

그것을 충돌(collision)이라고 부르고, 그 서로 다른 키지만 그 둘을 동의어(synonym)라고 부른다.

 

그렇다면 충돌이 발생했을 때는 어떻게 할까??

여러개의 슬롯이 있다면 버킷이 같더라도 각각 다른 슬롯에 넣으면 된다.

 

그렇다면 또 슬롯이 꽉차있는데도 충돌이 발생한다면??

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

키값으로 해시함수가 가리킨 주소에 들어갈 수 없는 상황이 되는 것이다.

 

다음 글에서 오버플로우 처리 방법에 대해 알아보자.