잔재미코딩
블로그 자료모음 기업교육

이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
잔재미코딩 소식 공유
좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 사이트와, 다음 두 채널도 오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
●  잔재미코딩 뉴스레터 오픈 [구독해보기]
●  잔재미코딩 유투브 오픈 [구독해보기]

6. 대표적인 데이터 구조5: 해쉬 테이블 (Hash Table)

  • Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조
    • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
    • 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
    • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
    • 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨

알아둘 용어

  • 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
  • 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터(Value) 위치를 찾을 수 있는 함수
  • Key를 해싱 함수로 연산해서, 해쉬 주소를 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 알 수 있음

간단한 해쉬 예

1) key 와 데이터를 국제전화코드를 예로 만들어 봅니다.

In [141]:
dial_code = dict()
dial_code[86] = 'China'
dial_code[91] = 'India'

2) 이번엔 초간단 해쉬 함수를 만들어봅니다.

In [142]:
# 해쉬 함수로 키를 넣으면 해쉬값을 리턴해줌 (해쉬값이 주소가 될 수 있음)
def hash_func(data):
    return data % 10

3) 해쉬 테이블에 저장해 봅니다.

In [143]:
hash_table = list([0 for i in range(10)])
def storage_data(hash_address, data):
    hash_table[hash_address] = data

4) 해쉬 테이블에서 특정 주소의 데이터를 가져오는 함수도 만들어 봅니다.

In [144]:
def get_data(key):
    return hash_table[hash_func(key)]

5) 실제 데이터를 저장하고, 읽어 봅니다.

In [145]:
address = hash_func(86)
storage_data(address, dial_code[86])
print (get_data(86))

China

파이썬 딕셔너리(Dictionary)

  • 내부적으로는 결국 hash로 구현
  • 예: 스마트폰에 전화번호 저장하기
    • 전화번호 저장시 이름을 저장하기
      • 이름: 여친, 전화번호: 000-2222-3333
    • 이름으로 전화번호 찾기

1) 해쉬 테이블을 위한 데이터 저장공간 만들기

In [146]:
data = list([0 for i in range(8)])
print (data)

[0, 0, 0, 0, 0, 0, 0, 0]

참고 (numpy 라이브러리 활용해서 데이터 저장공간 만들기)

In [29]:
import numpy as np
# np.empty(공간사이즈, dtype=object) 문자열(객체)를 넣을 수 있는 데이터 공간을 공간 사이즈만큼 배열로 만들기
data = np.empty(8, dtype=object)
print (data)

[None None None None None None None None]

2) 내장함수 hash() 로 해쉬키 만들기

In [148]:
hash('Dave')
Out[148]:
-1516350869034491289
In [150]:
hash('David')
Out[150]:
1599571219686153533
In [151]:
hash('Dave') % 8
Out[151]:
7
In [152]:
hash('David') % 8
Out[152]:
5

3) 해쉬 함수 만들기

In [153]:
# 임의로 8개의 해싱함수 만들어보기
def hash_function(string):
    return hash(string) % 8

4) Key를 해싱함수를 사용해서 데이터(Value) 저장하기

In [154]:
data[hash_function('Dave')] = '000-1111-2222'
data[hash_function('David')] = '000-2222-3333'

5) Key를 해싱함수를 사용해서 데이터(Value) 읽어오기

In [155]:
data[hash_function('Dave')]
Out[155]:
'000-1111-2222'
In [156]:
data[hash_function('David')]
Out[156]:
'000-2222-3333'

딕셔너리(Dictionary)를 사용하지 않고 hash 함수 만들어보기

  • 나머지를 기준으로 Hash Function 만들어보기
In [5]:
tel_dict['Dave']
Out[5]:
'000-1111-2222'
In [3]:
tel_dict = dict()
In [157]:
def hash_function(string):
    return hash(string) % 8
In [161]:
class HashMap:
    def __init__(self):
        self.items = list([0 for i in range(8)])
    
    def save(self, key, data):
        self.items[hash_function(key)] = data
    
    def get(self, key):
        return self.items[hash_function(key)]

hash_list = HashMap()
hash_list.save('Dave', '000-1111-2222')
hash_list.get('Dave')
Out[161]:
'000-1111-2222'
프로그래밍 연습
다음 메서드로
save: data 를 인자로 data 저장하고(내부 hash_function 함수 적용) 해쉬키를 리턴해주는 메서드
get: key를 인자로 해쉬키를 넣으면 저장된 데이터를 리턴해주는 메서드
def hash_function(string):
    return hash(string) % 8
다음과 같은 코드가 실행될 수 있도록 해보기 
hash_list = HashMap()
key1 = hash_list.save('Dave')
hash_list.get(key1)
In [112]:
class HashMap:
    def __init__(self):
        self.items = list([0 for i in range(8)])

    def __hash_func(self, data):
        return hash(data) % 8
    
    def __add(self, key, data):
        self.items[key] = data

    def save(self, data):
        key = self.__hash_func(data)
        self.__add(key, data)
        return key

    def get(self, key):
        return self.items[key]
프로그래밍 연습
위 코드에서 해쉬키가 동일할 경우에는 기존 데이터를 덮어씌우지 않고, 추가할 수 있도록 리스트 변수를 사용해서 만들어보세요 get 메서드에는 해쉬키가 동일한 데이터를 리스트 변수에 담아 리턴하도록 변경하기 
def hash_function(string):
    return hash(string) % 8
다음과 같은 코드가 실행될 수 있도록 해보기 
hash_list = HashMap()
key1 = hash_list.save('Dave')
hash_list.get(key1)

동일 해쉬 주소에 여러 데이터가 있을 때 (심화)

In [102]:
class LinearMap:
    def __init__(self):
        self.items = list()

    def add(self, k, v):
        self.items.append((k, v))

    def get(self, k):
        data = list()
        for key, val in self.items:
            if key == k:
                data.append(val)
        return data
In [103]:
linear_map = LinearMap()
linear_map.add(1, 2)
linear_map.add(1, 3)
linear_map.get(1)
Out[103]:
[2, 3]
In [104]:
class BetterMap:
    def __init__(self, n=100):
        self.maps = []
        for i in range(n):
            self.maps.append(LinearMap())

    def find_map(self, k):
        index = hash(k) % len(self.maps)
        return self.maps[index]

    def add(self, k, v):
        m = self.find_map(k)
        m.add(k, v)

    def get(self, k):
        m = self.find_map(k)
        return m.get(k)
In [105]:
better_map = BetterMap()
better_map.add(1, 2)
better_map.add(1, 3)
better_map.get(1)
Out[105]:
[2, 3]
In [106]:
class HashMap:
    def __init__(self):
        self.maps = BetterMap(2)
        self.num = 0

    def get(self, k):
        return self.maps.get(k)

    def add(self, k, v):
        if self.num == len(self.maps.maps):
            self.resize()
        self.maps.add(k, v)
        self.num += 1

    def resize(self):
        new_maps = BetterMap(self.num * 2)
        for m in self.maps.maps:
            for k, v in m.items:
                new_maps.add(k, v)
        self.maps = new_maps
In [107]:
hash_map = HashMap()
hash_map.add(1, 2)
hash_map.add(1, 3)
hash_map.get(1)
Out[107]:
[2, 3]

hash 장단점

  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
    • 캐쉬로 활용 시에도 유용함
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
    • 예: 알파벳을 키로 하는 해쉬테이블 공간을 10개로 놓았을 경우,
      • 몇몇은 공간이 충돌됨

좋은 해쉬 함수 사용하기

  • 충돌이 많은 해쉬 함수는 성능을 떨어뜨림
  • 주소에 키에 대한 데이터를 고루 분표시키는 함수
    • 근래 SHA(Secure Hash Algorithm) 함수등이 많이 사용됨

적합한 해쉬 테이블 사이즈

  • 해쉬 테이블 사용률: 해쉬 테이블에 있는 항목의 수 / 해쉬 테이블에 있는 공간의 수
  • 보통 해쉬 테이블 사용률이 0.7 이상이면 해쉬 테이블 사이즈를 2배로 늘림

실제 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)

SHA-1

In [76]:
import hashlib
hash_object = hashlib.sha1()                      # 어떤 해쉬 알고리즘 쓸래?
hash_object.update(b'Hello World')                # 어떤 값을 해슁할 것인가?
hex_dig = hash_object.hexdigest()                 # 16진수로 해쉬값을 리턴해줌
print(hex_dig)

0a4d55a8d778e5022fab701977c5d840bbc486d0

SHA-256

In [77]:
import hashlib
hash_object = hashlib.sha256()                    # 어떤 해쉬 알고리즘 쓸래?
hash_object.update(b'Hello World')                # 어떤 값을 해슁할 것인가?
hex_dig = hash_object.hexdigest()                 # 16진수로 해쉬값을 리턴해줌
print(hex_dig)

a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
합리적인 분들과 확연히 다른 좋은 IT 강의를 만들 수 있는 선순환 시스템을 지향합니다
컨택: dream@fun-coding.org
Copyright 2023 © (주)노이먼스 All rights reserved.