해시, Hash

다양한 책과 영상을 통해 해시, 해시 함수, 해시 테이블 등에 대해서 조금씩 배우기는 했는데 자료마다 해시를 소개하는 시점도 다르고 방법도 제각각이라 이번에는 공부를 하면서도 명확한 정의를 내리기가 어려웠다. 그래도 일단 내 나름대로 공부한 내용들을 모아서 정리를 해보았다.

해시 (Hash)

해시란 데이터를 다루는 기법의 하나로 검색과 저장을 효율화 시킨 자료구조다. 해시는 데이터를 ‘인덱스와 값’ 혹은 ‘키와 밸류’로 짝을 지어서 저장하는데, 파이썬의 딕셔너리나 자바의 맵 자료형과 매우 유사하다. (해시가 개념이라면 딕셔너리와 맵은 실질적으로 구현된 자료형이라고 이해하면 될까?)

해시의 구현과정

해시는 데이터의 검색을 빠르게 하기위해 데이터를 인덱스와 값으로 나누어 저장을 한다고 했다. 여기에서 인덱스의 생성을 위해 임의로 전달된 데이터의 값을 특정 기준 혹은 알고리즘으로 재정의하여 고정된 길이의 값으로 반환하는데, 그 알고리즘을 해시 함수(hash function)라고 부르고 그렇게 재정의 된 데이터의 값을 해시 값(hash value)이라고 한다.

그 다음엔 해시 값을 기준으로 짝을 지어서 데이터를 저장하게 되는데, 저장된 데이터들의 구조를 해시 테이블(hash table)이라고 부른다. 여기에서 해시 값이 해시 테이블의 인덱스 혹은 키가 되는 것이고, 원래의 데이터가 인덱스와 짝 지어진 밸류가 된다. 그리고 개별 인덱스와 밸류는 버켓(bucket)과 엔트리(entry)라고 지칭한다.

그리고 이렇게 데이터를 해시 자료구조로 변환하는 과정 전체를 해싱(hashing)이라고 한다.

해싱 예)

1. 정렬된 배열 A가 있을 때, A의 값들을 배열의 크기로 나눈 나머지를 구한다. 나눈 나머지 값이 해시값으로 이후 데이터에 접근하는 기준이 된다.

   A = [5, 6, 14, 20, 29, 34, 37, 51, 68, 75]

   Hash Value = [5, 6, 4, 0, 9, 4, 7, 1, 8, 5] (A를 len(A)인 10으로 나눈 나머지 값들)

2. 해시값을 인덱스로 생각하고 다시 배열을 만든다.

   A2 = [20, 51, None, None, [14, 34], [5, 75], 6, 37, 68, 29 ]

3. 추가할 숫자를 마찬가지로 배열의 크기로 나눠준 후 나머지 값을 인덱스로 하여 삽입한다. 예를들어 12를 추가할 경우, 12 % 10 은 2가 되므로 A2[2] 에 넣어준다.

   A2 = [20, 51, 12, None, [14,34], [5,75], 6, 37, 68, 29]

---

만약 해싱을 하지 않고 12를 추가할 경우 14부터 그 뒤의 값들의 위치를 모두 한칸씩 움직여야 했을 것이다. 하지만 이렇게 해싱을 이용하면 배열에 값을 추가하기 위해 다른 원소들의 위치를 모두 한칸씩 움직이지 않아도 된다.

이 과정에서 원소를 새로 저장한 배열 A2가 해시 테이블이고 키를 해시값으로 변환하는 과정이 해시 함수다.

그런데 중간에 보면 [14, 34], [5, 75] 처럼 해시값이 중복되는 경우가 있는데 이를 충돌(Collision)이라고 한다. 해시법에서 충돌이 발생하는 경우 다음 방법으로 대처할 수 있다:

• 체인법 (Chaining): 해시값이 같은 밸류들을 연결 리스트로 관리
• 오픈 주소법 (Open Addressing) 혹은 선형 탐사 (Linear Probing): 빈 버켓을 찾을 때까지 해시를 반복하여 빈 버켓에 밸류를 삽입.
• 리사이징 (Resizing): 해시 테이블에 빈 버켓이 없어서 더이상 오픈 주소법을 사용할 수 없는 경우 테이블의 크기를 늘리고 다시 해싱을 하여 추가 공간을 생성.

딕셔너리를 통한 해시 구현

해시 함수를 사용해서 해시 테이블에 값을 삽입할 수도 있지만, 파이썬에서 딕셔너리를 사용하여 직접 해시를 구현할 수도 있다. 아래는 딕셔너리를 통해 해시를 구현하는 방법이다.

# 딕셔너리 선언 
hash = dict()

# 딕셔너리 삽입/수정
hash[1] = 'apple'
hash['banana'] = 3
hash[(4,5)] = [1,2,3]
hash[10] = dict({1:'a', 2:'b'})
hash[1] = 'melon'  # 키 1에 대한 값이 'apple'에서 'melon'으로 변경됨

# 딕셔너리 값 추출
hash.pop(1)  # {1:'melon} 추출
hash.pop('banana')  # {'banana':3} 추출

# 딕셔너리 삭제
del hash[(4,5)]
del hash[10]

• 배열과 집합은 딕셔너리의 키값으로 사용할 수 없음 (인덱스 변환 불가)
• del 함수사용은 결과를 돌려주지 않고 바로 삭제가 이루어지지만 성능에 큰 영향을 미칠정도로 .pop()과 속도가 크게 차이나지는 않음

딕셔너리 루프

dict 클래스 함수를 통해 무엇을 기준으로 루프를 돌릴 것인지 선택 가능

hash = dict() 클래스 선언을 했을 때,

• hash.keys() : 딕셔너리의 모든 키값을 리스트로 반환
• hash.values() : 딕셔너리의 모든 밸류값을 리스트로 반환
• hash.items() : 딕셔너리의 모든 키와 밸류값을 튜플로 반환

딕셔너리 정렬

sorted() 함수 사용 ⇒ 언제나 리스트로 반환

# sorted 함수 정의
sorted(정렬할 데이터, [key 파라미터], [reverse 파라미터])

# 오름차순 정렬
sorted(hash.keys(), key = lambda x : x)  # 키 정렬
sorted(hash.values(), key = lambda x : x)  # 밸류 정렬
sorted(hash.items(), key = lambda x : x)  # (키, 밸류) 튜플들을 키를 기준으로 오름차순 정렬

# 내림차순 정렬
sorted(hash.keys(), key = lambda x : -x)  # 키 정렬
sorted(hash.values(), key = lambda x : -x)  # 밸류 정렬
#sorted(hash.items(), key = lambda x : -x)  # 튜플에 -를 적용할 수 없기 때문에 에러발생
sorted(hash.items(), key = lambda x : -x[1])  # (키, 밸류) 튜플들을 밸류를 기준으로 내림차순정렬
sorted(hash.items(), key = lambda x : x[1], reverse=True)

• sorted 함수의 key 옵션은 어떤 것을 기준으로 정렬할 것인가 정의
• sorted 함수의 reverse 옵션은 내림차순으로 정렬할 것인지 선택. 없을 경우 오름차순이 디폴트이며 reverse=True 로 입력하면 내림차순으로 정렬하여 반환
• key를 음수로 정하면 reverse 선택을 안해도 내림차순으로 정렬
• .sort()와 sorted()의 차이는 .sort()는 본체 리스트를 정렬해서 변환하고 sorted()는 본체는 그대로 둔 상태로 정렬한 새 리스트를 반환한다.