자료구조/알고리즘 - 해시(Hash)

패스트캠퍼스 - 컴공전공 - 소프트웨어 베이직 - 자료구조/알고리즘 - 해시

 

 

 

해시 ( Hash )

 

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

메모리 공간 소모가 크지만, 매우 빠른 속도로 데이터 처리

데이터베이스 등의 소프트웨어에서 활용

 

패스트캠퍼스 강의자료

 

 

입력받은 값 n에 대해 10으로 나눈 나머지 값 -> key

 

 

특정한 값(value)을 찾고싶을 때 그 값의 key로 접근 가능하다.

일반적으로 해시 함수는 모듈로(Modulo) 연산 등의 수학적 연산으로 이루어져 있으므로,

O(1)의 시간 복잡도를 갖는다.

 

 

 

- 해시의 충돌

 

 

 

어떤 값이든 입력값으로 받을 수 있지만,

해시 함수를 거쳐 생성되는 key의 수는 한정적이므로 key 중복이 발생할 수 있다.

hash table에서 key가 중복되는 경우,

충돌(collision)이 발생했다고 표현한다.

 

 

 

 

 

 

- 해싱 (Hashing) 알고리즘

 

 

나눗셈 법(division method)이 가장 많이 활용됨

( 입력값 / 테이블의 크기의 나머지 = key )

테이블의 크기는 소수(prime number)로 설정하는 것이 효율성이 높다.

( 소수로 나누었을 때 key가 겹칠 확률이 적기 때문 )

 

 

 

- 충돌 처리방법

 

1. 충돌을 발생시키는 항목을 hash table의 다른 위치에 저장 

-> 선형 조사법, 이차 조사법 등

 

2. hash table의 하나의 bucket에 여러 개의 항목을 저장 

-> chaining 등

 

 

 

 

 

 

* 선형 조사법

 

 

 

중복이 발생할 경우,

해당 key값의 비어있는 다음 위치에 값을 넣는다.

비어있는 자리를 선형적으로(차례대로) 탐색해나가기 때문에 선형 조사법이라 한다.

 

 

 

** 선형 조사법 구현해보기

 

 

 

 

 

 

 

 

강의에서 사용한 코드를 동일하게 작성해보았고, 

결과값이 정상적으로 출력되었다.

 

이번 예제에서는 time 라이브러리를 이용한 게 조금 특이했는데,

예전에 로또번호를 랜덤으로 추출하는 코드를 작성할 때 사용했던 라이브러리여서

자세한 설명 없이도 금방 이해할 수 있었다.

 

 

 

 

** 선형 조사법의 단점

 

 

충돌이 발생하기 시작하면,

유사한 값을 가지는 데이터끼리 밀집되는 '집중 결합' 문제가 존재한다.

 

해시 테이블의 크기가 크다면 (메모리를 많이 소모한다면)

충돌이 적게 발생하므로 매우 빠른 데이터 접근속도를 가질 수 있다.

 

일반적인 경우, hash table 크기가 한정적이므로 충돌이 최대한 적게 발생하도록 해야 한다.

 

 

 

 

 

* 이차 조사법

 

 

선형 조사법을 변형한 형태 

-> 키 값을 선택할 때 '완전 제곱수'를 더해나간다.

 

 

패스트캠퍼스 강의자료

 

 

위의 예제를 살펴보면,

중복이 발생했을 때

해당 키값으로부터 차례대로 1², 2²,... 만큼 떨어져있는 위치에 값을 넣는 것을 확인할 수 있다.

 

=> 선형 조사법에서 발생했던 데이터가 밀집되는 문제를 줄일 수 있다.

따라서 해시 충돌이 보다 적게 발생한다.

 

 

 

 

 

** 조사법의 테이블 크기 재설정

 

선형 조사법, 이차 조사법 모두 테이블이 가득 차는 경우,

테이블의 크기를 확장해서 해시 테이블을 계속해서 유지할 수 있다.

 

 

 

 

 

 

* 체이닝 기법 (chaining)

 

 

연결 리스트를 활용, 특정 키를 갖는 항목들을 연결해 저장

-> 삽입/삭제가 용이, 테이블크기 재설정 문제는 '동적 할당'을 통해 해결

(동적 할당을 위한 메모리공간이 추가적으로 필요하다.)

 

 

 

체이닝 기법을 이용하면,

충돌이 발생했을 때 해당 키값에 그냥 데이터들을 연결리스트로 모두 삽입한다.

 

 

 

 

 

 

** 체이닝 기법 구현해보기

 

 

 

 

 

강의에서 사용한 예제이고,

정상적으로 출력되는 것을 확인할 수 있었으며

동일한 키 값에 여러 개의 데이터가 저장되기도 한 것을 확인해볼 수 있었다.

 

 

 

 

 

 

 

 

 

정리

 

 

•Hash는 이론적으로 데이터의 삽입/삭제에 O(1)의 시간복잡도를 갖는다.

•데이터베이스 인덱싱 및 정보보안 관련 모듈 등에서 다양하게 사용된다.