C 언어 HashTable #01

#Hash

이게 우리가 하고자하는 해시랑 무슨 관련이 있을까요?.

고기 요리를 잘게 썰면 새로운 요리가 탄생하게 됩니다. 바로 이것이 해시의 본 뜻인것 같네요!.

쉽게 말해 해시란 어떤 값을 전혀 다른 새로운 값으로 바꿀 수 있다는 것을 의미합니다.

" 그렇다면 그 데이터로 어떤 일에 쓰이나요?. "

 - 해시 테이블

 - 암호화

 - 데이터 축약

크게 이 세가지 용도로 쓰이게 됩니다. 고기요리로 비유를 들어 아시겠지만, 고기요리 (데이터) 를 잘게썰어 만든 고기요리(변형된 데이터)

즉 어떤 데이터를 전혀 새로운 모습의 데이터를 만들어 내서 암호화에 널리 쓰이고 있으며, 또한 이 변환된 데이터는 데이터가 아무리 길더라도 일정한 길이의 출력 

데이터를 만들어 내기에 데이터가 원본에 비해 어마어마하게 축약되어 엄청난 효율을 지닐 수 있는 것이지요. 또한 배열의 주소값을 이용해 접근하는 방식이라 다른 

데이터를 거치지 않고 바로 접근 할 수있는 장점 때문에 속도도 어마무시하게 빠르지요.

#HashTable

그래서 우리가 알아볼 해시 테이블 (HashTable) 에 대하여 하나씩 차근차근 알아보도록 하지요.

자 위에 있는 배열은 길이가 139 인 배열이라고 하겠습니다. 배열의 이름은 arr[139] 라고 하지요.

arr[0] = 12

arr[1] = 8

      .

  .

arr[??] = 18290

  .

  .

arr[138] = 89

각 요소에 접근하고 싶으면 [] 키워드를 통해 어떤 곳이든 접근 하여 값을 알아 낼 수 있습니다. 

12에 접근하고 싶으면 0번 인덱스를,

8에 접근하고 싶으면 1번 인덱스를,

89에 접근하고 싶으면 138번 인덱스를,

그럼 18290 에 접근하고 싶으면 어떤 인덱스로 접근해야 하나요?......

우리는 알고 있는 여러가지 알고리즘으로 이 18290 이라는 값을 찾아 나갈 수 있습니다. 하지만 우리는 해시에 대해서 배우고 있습니다!.

해시의 장점을 다시한번 상기시켜 봅시다!.

인덱스, 즉 주소값으로 접근하는 방식으로 아주아주 빠르다. 라는 장점을 이용해야 하는 것이지요!.

해시테이블은 아주아주 간단한 개념을 도입해서 이 문제를 해결했습니다. 바로 데이터를 테이블 내의 주소값으로 바꾸는 생각의 전환을 이용한 것 이었지요!.

값 ---> hash function ---> 주소

바로 값을 어떤 해시의 방법론으로 주소값으로 변환시키는 것이지요.

 

#나눗셈법

주소 = 값 % 테이블의 크기

이것이 해시 함수 중에서도 가장 간단한 알고리즘 입니다. 말그대로나누어서 그 나머지를 테이블의 주소로 사용하는 방식이지요.

tip ) '%' : 나머지를 구하는 연산

아주 아주 간단하게 코드로 구현해 보겠습니다. 아주 단순한 방법론이지요.

이 코드에 따르면 테이블의 길이가 '193' 값이 9인 경우 9를 반환하게 돕니다.

값이 '418' 일때는 32,

값이 '1031' 일때는 66,

값이 '27' 일때는 27을 반환하게 됩니다.

여기서 테이블의 길이를 193 으로 지정 한 이유는 나눗셈법으로 구현된 해시 함수가 테이블 내의 공간을 효율적으로 사용하기위해서는 테이블의 크기 n 을 소수로 

정하는 것이 좋다고 알려져 있습니다.

2의 제곱수와 거리가 먼 소수를 길이로 만든 해시 함수가 좋은성능을 낸다고 합니다!.

그렇다면 이제 나눗셈법을 이용한 해시테이블을 구현한 예제 프로그램을 구현해보도록 하지요!.

#예제 프로그램

자 우리는 .h 문서를 만들어 저장하겠습니다!.

맥 에선 c 를 사용할 수 있는방법이 Xcode 툴을 이용하는 것 밖에 몰라서 Xcode 를 사용하였습니다. 윈도우를 이용하시는 분들은 visual studio를 사용하시면...

됩니다!.

1. 주소 반환 함수 ( 나눗셈법 ) 

자 먼저 주소 반환 함수를 작성했습니다!. 따로 크게 설명할 건 없지만... 이해가 잘안되시는 분들을 위해 다시한번 설명을 해보겠습니다. 

주소 = 값 % 테이블의 크기

우리는 나눗셈법을 알고 있습니다!. 테이블의 크기(길이) 와 값을 이용한 주소(인덱스) 를 반환 하는 함수입니다!. 잘 이해가 안가신다면 스크롤을 조금만 올려 다시한

번 읽고 오시는것을 추천합니다!.

2. 노드와 해시테이블 정의

해시 테이블이 가지고 다닐 노드와 해시테이블을 구현했습니다!.

우리는 value 와 해시 테이블이 가지고 있는 hashSize 를 이용하여 address 로 사용할 것입니다!

address = value % hashSize

주소 = 값 % 테이블의 크기

이렇게 보니 똑같죠?

3. 해시 테이블 만들기

해시테이블을 정의를 했으면 해시테이블을 만들어주어야겠지요. malloc 함수를 이용하여 공간을 만들어 주었습니다.

해시테이블을 만들어 준 후, 포인터를 반환하게 되지요.

ex) malloc(size) : 말록 함수는 메모리에 size 만큼 공간을 할당하여 만들어주는 일을 합니다.

4. 값 넣기 값 가져오기

해시 테이블을 만들었다면 각 값이 해시 값으로 변환된 인덱스에 값이 잘 set 되고 get 되어야겠지요.

5. malloc 으로 할당한 메모리 해제시키기

할당된 메모리를 해제 시켜주는 함수도 있어야겠지요!...

#예제 프로그램 테스트

메인

콘솔결과.

다음 내용은 다른 방법론으로 구현한 해시를 알아보도록 할게요!.

처음 작성한 글이라 설명이 미숙하기만 하네요!... 

혹시나 이해가 안되시거나 하시면 메일을 주셔도 좋고 댓글을 달아주셔도 좋습니다!.

imgenius0136@gmail.com