[자료구조 with Python] 5. 선형 자료 구조 - 배열(4), Hash검색

 

 

 

 

지난 포스팅에서, 배열의 기본 검색 방법인 선형 검색과, 오름차순 또는 내림차순으로 정렬된 자료를 가지는 배열에서 효율적인 검색이 가능한 이진 검색에 대해 알아보았다. 이번 포스팅에서는 지난 포스팅의 내용에 이어, 배열 내의 값을 검색하는 세 번째 방법인 Hash 검색에 대해 알아보려 한다.

 

Hash 검색을 이해하기 위해서는, Hash와 관련된 내용에 대해 먼저 알고 들어갈 필요가 있다. 먼저 Hash 함수, Hash 값에 대해 알아보는 것부터 시작해보자.

 

 

1. Hash 란?

 

SNS때문에 Hash라는 단어가 무언가를 설명하는 기호(#)로 일반인에게는 많이 알려져 있지만, 컴퓨터와 관련된 업무를 하는 사람들 사이에서 Hash는 "임의의 값을 특정 길이의 값으로 변환"하는 작업을 의미한다. 특정 값의 Hash 작업은 'Hash() 함수(Hash 알고리즘이라고도 한다)'에 의해 진행되며, Hash() 함수에 의해 도출되는 결과값을 'Hash값(Hash코드)'이라고 한다.

 

 

조금 더 쉽게 풀어 설명하자면, "안녕하세요"와 "Mr. Python"이라는 문자열을 Hash 작업을 통해 변환하면 고정된 길이(예를 들어 5글자)로만 나타나게 된다.

 

"안녕하세요"  :   Hash함수1("안녕하세요")  ->   FC0A3

"Good Morning Mr.Python"  :   Hash함수("Good Morning Mr.Python") -> 34A9D

 

 

Linux에서 이 Hash가 적용된 곳을 발견할 수 있는데, 바로 각 계정의 암호를 저장하는 shadow 파일이다. 이 파일에는 각 사용자의 암호가 hash 함수를 통해 고정된 길이의 변형된 값으로 저장된다. 

 

잘 알려진 Hash 함수로는 MD(Message Digest)와 SHA(Secure Hash Algorithm)이 있다. MD 알고리즘은 128자리의 값으로 변환된 값을 제공하는데, 2013년에 이미 Hash값을 통해 기존의 값을 90% 이상 해독할 수 있음이 밝혀져 안전성 문제로 인해 잘 사용하지 않는다. 따라서 현재 대부분의 컴퓨터에서는 SHA 계열의 Hash 알고리즘을 사용한다. 위에서 예시로 든 Linux도 SHA를 사용한다.

 

Python에서 특정 변수의 값으로부터 Hash 값을 추출하는 것은 기본 Python 라이브러리에 포함된 hashlib 패키지를 Import 하면 된다. hashlib 패키지 안에는 MD, SHA 알고리즘을 통해 Hash 값을 추출하도록 하는 함수도 존재한다.

 

hashlib 패키지 안에 존재하는 sha512 함수를 예로 사용해보자. sha512 함수는 인자로 문자열이나 숫자 등을 사용한다. 아래와 같이 sha512 함수 인자로 "Hello"라는 문자열을 넣어 코드를 실행하면, Hash 함수의 결과가 Sha512 Hash객체로 반환된다.

 

 

객체로 반환된 값을 문자로 표시하기 위해서는 Hash 값(digest)을 표현하기 위한 메서드 함수를 추가해주어야 한다. 이 메서드 함수는 digest()와 hexdigest() 두 종류가 존재하는데, digest는 \x로 시작하는 - 아직은 필자가 알 수 없는 포맷의 - 문자열로 표시되며, hexdigest는 16진법으로 표시된다. 

 

 

'sha1'을 제외한 나머지 sha 알고리즘의 뒤에 붙어있는 숫자는, Hash값의 길이를 의미한다. 예를 들어, sha-512의 경우, Hash 값이 512bit(128자, 1자(char)는 4bit를 차지한다)로 고정된 길이를 가진다. sha-1은 160비트, 40자 길이의 값으로 반환된다.

 

SHA512의 결과값 길이: 128자

 

 

SHA256의 결과값 길이: 64자

 

 

 

2. Hash 검색 알고리즘에서 Hash값의 사용법과 Hash 검색 사용을 위한 자료구조.

 

배열안의 특정 위치에 저장된 값을 Hash 알고리즘을 통해 Hash값을 추출했다고 가정해보자. 그럼, Hash 검색에서 이 추출한 Hash 값이 어떤 역할을 하게 되는 것일까? 

 

위의 예시에서 봤듯이, Hash 함수에 들어가는 값이 동일하면, Hash 값도 동일하다. 배열에 값을 넣기 전에, 이 각기 다른 Hash 값을 이용하여 값이 저장될 배열의 index를 구할 수 있다면, 서로 다른 값들을 별도의 index에 저장할 수 있을 것이다.

 

문제는, 우리가 위에서 본 Hash 값의 반환 형태가 문자열이기 때문에, index에 넣을 수 있는 int나 long(정수) 자료형으로 변환해야 한다는 것이다. 다행히도, hexdigest로 얻어낸 값이 16진수로 표현된 문자열이기 때문에, 이 값을 10진법으로 변환하는 것이 가능하다.

 

hash 값 앞에 0x를 추가하여, 16진수로 표현된 문자열을 10진법으로 변환한 결과.

 

그런데, 10진법으로 변환한 값은 index로 쓰기에 너무 크다는 것이 문제다. 사람의 인지능력으로는 셀 수 있는 범위를 넘어서는 숫자라, 컴퓨터가 배열을 생성할 수 없고, 설령 컴퓨터가 저 크기만큼의 배열을 생성할만한 능력이 있다고 해도, 메모리의 낭비가 너무 심해진다. 감이 안오시는 분들은 아래의 코드를 한 번 보자. 뭔가 아득해지지 않는가?

 

print(list[2832704043344549871570708225316172805838044371438910560478926526156969430227809249581562345088470888157080353509043112646602814782792647180723640865125141])

 

따라서, 추출한 Hash값을 적당한 크기의 배열에 맞게 index를 변환하는 과정을 다시 한 번 거쳐야 한다. 이는 프로그래머마다 고유의 방법으로 진행하는데, 가장 간단한 방법 중의 하나는 추출된 Hash값을 생성할 배열의 크기만큼 나눈 나머지를 index로 사용하는 것이다. 만약 필자가 길이 10만큼의 배열을 사용한다고 가정하면, 위의 값은 10을 나눈 나머지 1을 index로 지정하여 list[1]의 위치에 "Hello"가 저장하게 하는 것이다.

 

 

다른 값도 한 번 저장해보자. 이번에는 value 변수를 "Python"으로 지정하고 동일한 과정을 거쳐 list 가 어떻게 변하는지 확인해보자.

 

 

list[8]에 "Python" 문자열이 저장된 것이 보인다. 

 

지금은 예시를 위해 저장되는 값으로부터 추출한 Hash 값을 이용해 index를 지정했지만, 실제 Hash 검색 알고리즘은, 직접 '저장되는 값'을 이용해 index를 구하는 것이 아니라 저장되는 값을 구분할 수 있는 키 값을 인자로 사용한다.. 일상에서 hash 검색을 손쉽게 확인할 수 있는 것이 핸드폰의 전화번호 검색 기능인데, 전화번호 검색 시 저장해놓은 사람의 이름만 입력하면 그 사람의 전화번호가 뜨는 것이 바로 이 hash 검색과 매우 유사하다. 한 번 확인해 보자. 

 

 

우리가 만든 이 list에서 이름만으로 index 값을 변환해 검색할 수 있도록 함수를 별도로 만들어 낸다면, 선형 검색처럼 배열의 첫 부분부터 훑어보는 과정없이 우리가 찾고자 하는 값(여기서는 전화번호)을 더 효율적으로 찾아낼 수 있게 된다. 

 

 

지금까지 알아본 hash 검색 알고리즘을 가능하게 할 자료 구조를 Python 코드로 작성하면 아래와 같이 나타나게 된다.

 

 

참고로, key 값이 정수형일 경우, sha512로 Hash값을 추출하는 것이 불가능하다.

 

 

따라서, key 값이 정수형인 경우(instance(self.key, int)) key 값을 바로 배열 크기로 나눈 나머지 값을 index로 사용하도록 설정한다. 추가로, key 값이 문자열인 경우, window의 커맨드 창에 Hash 값을 제대로 출력하려면, 유니코드로 지정된 key 값을 encode() 메서드로 한 번 인코딩을 진행해 주어야 한다.

 

 

위의 코드 내용을 바탕으로 정보의 추가 및 검색 코드를 작성하고 실행하면 아래와 같은 결과가 나온다.

 

hash 검색을 사용하는 자료구조를 통한 값의 저장과 검색 코드

 

hash 검색 자료구조 코드의 테스트 결과

 

 

사실, Python에서도 Hash 검색과 유사한 가능한 자료구조를 가지고 있는데, Python의 기본서에도 나오는 Dictionary 자료형이 바로 Hash 검색이 그것이다. Dictionary 자료형 역시, 특정 키 값을 통해 저장된 값을 저장하고 찾을 수 있다는 점에서 Hash 검색에 사용되는 자료형과 매우 유사하다.

 

 

 

 

 

3. Hash 검색 알고리즘의 문제점.

 

필자가 아주 극단적으로, 전화번호를 저장할 수 있는 배열의 크기를 2로 정했다고 가정해보자. 검색에 사용되는 이름으로부터 계산되는 index 값은 "김철수"와 "박희동" 모두 0이 된다. 즉, 배열 0번에 두 값이 중복되어 들어가게 된다. 

 

 

이렇게 될 경우, 먼저 저장한 값이 뒤에 저장된 값에 의해 검색이 불가능해지는 현상이 발생한다.

 

 

위와 같이 공동의 Hash 값을 가지게 되는 경우가 발생하게 되는 것을 Hash 충돌이라고 한다. Hash 충돌이 발생하면, 충돌이 발생하기 전에 저장되어 있던 값은 신규 등록된 값으로 대체되며, 이전의 값은 사라지게 된다. 이렇게 될 경우, 유사한 정보의 저장이라는 배열 본연의 기능을 진행하지 못하기 때문에, Hash 충돌을 해결할 방안이 마련되어야 한다.

 

이 Hash 충돌의 해결 방법은 두 가지가 있는데, 충돌되는 값을 연결 리스트(Linked List)로 연결하거나(체이닝, Chaining), 다른 비어있는 배열에 값을 저장하는(개방 주소법, Open Addressing) 방법이 있다. Hash 충돌의 해결 알고리즘과 코드는 다음 포스팅에서 알아보려 한다.

 

 

 

Fin.