해싱은 데이터를 아주 빠르게 삽입하거나 가져올 때 사용하는 자료구조 기법이다.

해시 구조

해쉬테이블 : Key에 Value를 저장하는 데이터 구조
해싱 함수 : key에 대해 산술 연산을 이용해 데이터의 위치를 찾을 수 있는 함수

해싱의 핵심은 넓은 공간을 사용해, 데이터의 저장과 검색 시 발생되는 시간을 줄이는 것이다.

예를 들어 저장의 경우 key를 넣으면 해싱함수가 고유숫자를 리턴하는데 이 값을 주소로 하는 저장공간에 value를 저장한다.

반대로 검색의 경우 마찬가지로 해싱함수에 key를 넣어 찾고하자 하는 것의 주소를 리턴받아 그 저장공간을 찾아 읽으면 된다.

파이썬 Hash

파이썬에서 매우 매우 매우 유용하게 사용하는 Dictionary는 이 해시 테이블로 구현된다.

해시는 key-value 쌍으로 이루어져 있으며 파이썬의 dictionary는 Json 형식으로 사용하면 된다.

hash = {
    'color' = 'green'
    'age' = 24
}

딕셔너리가 저장되면 value값은 dictionary_name['key_name'] 으로 가져올 수 있다.

유용한 함수

• {dictionary}.keys()
  모든 키를 반환한다. 리스트로 변환해주면 활용도가 높아진다.

• dictionary[key] = [리스트] or diction[key].append([리스트])
  key값이 없는 상태면 새로운 키에 대한 value로 리스트를 만들어주고 이미 있는 상태면 key의 value인 리스트에 값을 추가해준다.
  

언제 사용할까?

해시를 사용해야 하는 경우들은 다음과 같다.

1. 리스트를 쓸 수 없을 때

리스트의 경우 값을 뽑을 때 인덱스는 무조건 정수이다. 만약 정수가 아닌 문자열이나 튜플을 인덱스로 사용할 때 해시를 사용한다.

2. 빠른 접근, 탐색

딕셔너리의 시간복잡도는 대부분 O(1)이므로 매우 빠른 자료구조이다.

3. 집계가 필요할 때

원소의 개수를 셀 때 from collection import counter을 사용하면 다음과 같이 빠른 집계를 사용할 수 있다.

string_ex = 'aaaaabbbbbbccccccaaaaddddd'
c1 = Counter(string_ex)
c1 # Counter({'a': 9, 'b': 6, 'c': 6, 'd': 5})