[자료구조] 05. Hash Table

안녕하세요? 주니하랑 입니다.

오늘은 자료구조에서 Hash Table에 대해서 공부 해 보도록 할 것이에요!

제가 작성한 코드가 궁금하시다면? 주니하랑의 깃 허브에 관심을 주세요!

해시 함수에 대한 개념을 잘 모르신다면 [정보보안] 해시함수 개념에 관심을 주세요!

바로 시작 해 보겠습니다!

 

 

---

 

 

 

📌 Hash Table

---

 

    📍 Hash 구조

Hash Table은 Key와 Data를 저장하는 Data 구조인 것이에요.

JAVA로 보면 Hash Map이 될 것이고, Python에서는 Dictionary 구조가 될 것이에요!

• Key를 통해 바로 Data를 받아올 수 있으므로, 속도가 획기적으로 빠르다
• Python Dictionary(사전) Type Hash Table Exam : Key를 가지고 바로 Value를 꺼낸다.
• 보통 배열로 미리 Hash Table 크기 만큼 생성 뒤에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
• 단, Python이나, JAVA 등 Hash를 별도 구현할 이유가 없다. (Dictionary, Hash Map 사용)

 

    📍 주요 용어

• Hash : 임의 값을 고정 길이로 변환 (입력 값이 아무리 크더라도 고정된 값으로 Out을 한다. SHA -256의 경우 Out 크기가 256)
  입력 값을 Block이라 부른다.
• Hash Table : Key Value의 연산에 의해 직접 접근이 가능한 Data 구조
• Hashing Function(해싱 함수) : Key를 Hashing Function으로 연산하여 Hash Value를 알아내고, 이를 기반으로 Hash Table에서 해당 Key에 대한 Data 위치를 일관성 있게 찾을 수 있다.
• Slot : 한 개의 Data를 저장할 수 있는 공간
• 저장할 Data에 대해 Key를 추출할 수 있는 별도 Function(함수)도 존재할 수 있다.

 

 

 

 

 

 

    📍 자료 구조 Hash Table 장, 단점 및 주요 용도

          👉 장점

• Data 저장 / 읽기 속도가 빠르다. ( 검색 속도가 허벌나게 빠르다.)
• Hash는 Key에 대한 Data가 있는지 (중복) 확인이 쉽다.

       

          👉 단점

• 일반적으로 저장공간이 좀 더 많이 필요
• 여러 Key에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조 필요

 

          👉 주요 용도

• 검색이 많이 필요한 경우 사용
• 저장, 삭제, 읽기가 빈번한 경우 사용
• Cache 구현 시 사용 (중복 확인이 쉽기에 사용)

 

 

 

 

 

먼저 Hash를 이용해서 Data를 찾을 때, data에 해당('Andy', 'Dave', 'Trump')하는 것을 먼저 찾으면 그와 Matching 되는 Key를 찾게 되고, 그 Key를 먼저 ord()를 이용하여 문자열을 ASCII Code (정수)를 구한 다음 Hash 함수에 넣으면 Division 방식으로 나누기 5를 하고, 나머지 값을 찾는 것이에요. 그러고 난 뒤 그것을 Hash Address로 사용하여 Hash Table에 있는 번호와 Matching 시켜 값을 찾을 수 있답니다!

 

 

위와 같이 Hash Table이 아닌 배열을 사용했다면 Key(ASCII)와 Value가 들어갈 두 개의 배열이 필요하게 될 것이고, 만약 Trump를 찾으려면 16번에 검색이 이뤄어 져야 하는 단점이 있는 것이에요.

 

하지만, Hash를 이용하면 해당 data를 통해 Matching되는 값을 내부 연산으로 바로 찾을 수 있는 장점이 있답니다!

 

우리는 위에 Hash Function에서 Division 방식을 위해 5를 나눈 것을 알고 있습니다.

그리고, Hash Table은 총 5개의 길이를 가지고 있지요.

내가 입력할 Data보다 일반적으로 조금 크게 Hash Table을 만들어야 하는데, 여기서 Hash Table의 단점을 알 수가 있는 것이에요.

위의 그림에서 Hash Tabledp 1, 2번 Data가 비어있음에도 만들어 준 것은 만약 내가 넣을 Data 개수 만큼 길이를 잡거나 그 보다 적게 잡게 되면 '충돌'을 해결하기 위해 별도 자료 구조가 필요해 지는 것이에요. 만약 Andy라는 값의 Key와 추가로 넣은 Harang이라는 Data의 Key가 동일하다면 이것을 구분하기 위해 Hash Table의 길이가 작으면 작을수록 이러한 확률이 올라간다는 단점이 있답니다!

 

 

 

 

📌 충돌(Collision)

---

해쉬 테이블의 가장 큰 문제는 충돌인 것이에요. 이 문제를 충돌 또는 해쉬 충돌(Hash Collision)이라 한답니다!

 

    📍 충돌 해결 알고리즘

          👉 Chaning 기법

개방 해싱 혹은 Open Hashaing 기법이라고 불리는 것이에요. 이것은 해쉬 테이블 저장 공간 외 추가로 공간을 활용하는 기법인 것이에요.

충돌이 일어나면, 링크드 리스트라는 자료 구조를 활요하여 링크드 리스트로 데이터를 추라고 뒤에 연결 시켜서 저장하는 기법인 것이랍니다.

 

CollisionChainning.py

 

# HashTable 충돌 해결 학습

print("연습 문제: 연습 문제 1번(hashTable.py)의 Hash Table Code에 Chaining 기법으로 충돌해결 Code 작성")
print('-' * 100)
print("Hash Function : key % 8 \n Hash Key : hash(data)")
print('-' * 100 + '\n')

hash_table = list([0 for i in range(10)])


def hash_function(key_1):
    return key_1 % 10


def hash_key_maker(data1):
    return hash(data1)


def save_data(data1, value):
    # Hash Table의 충돌로 인하여 링크드 리스트를 통하여 chainning기법을 통해 해결을 하고자 할 때, 해당 값을 판별하기 위하여 key를 따로 저장
    index_key = hash_key_maker(data1)

    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):

            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return

        hash_table[hash_address].append(index_key, value)

    else:
        hash_table[hash_address] = [[index_key, value]]


def output_data(data1):
    index_key = hash_key_maker(data1)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
            return None
        else:
            return None

    return hash_table[hash_address]


# hash 충돌을 발생 시키기 위해 Test
print(hash('Juny') % 10)
print(hash('Harang') % 10)
print(hash('Dev') % 10)
print('-' * 100 + '\n')

save_data('Juny', '12345678')
save_data('Dev', '22293848')

print(output_data('Juny'))
print('-' * 100 + '\n')

print(hash_table)
print('=' * 100 + '\n')

 

 

          👉 Linear Probing 기법

폐쇄 해슁 또는 Close Hashing 기법 중 하나로 해쉬 테이블 저장 공간 안에서 충돌 문제를 해결하는 기법인 것이에요.

충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 Data를 저장하는 기법이랍니다!
저장 공간 활용도를 높이기 위해서 사용한다고 해요!

 

 

CollisionLinearProbing.py

# HashTable 충돌 해결 학습

print("연습 문제: 연습 문제 1번(hashTable.py) Hash Table Code에 Linear Probing 기법으로 충돌 해결")
print('-' * 100)
print("Hash Function : key % 8 \n Hash Key : hash(data)")
print('-' * 100 + '\n')

hash_table = list([0 for i in range(10)])


def hash_function(key_1):
    return key_1 % 10


def hash_key_maker(data1):
    return hash(data1)


def save_data(data1, value):
    index_key = hash_key_maker(data1)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):

            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return

            elif hash_table[index][0] == index_key:  # 값이 다르지만, index Key가 동일하다면?
                hash_table[index][1] = value  # 그 다음 위치에 값을 저장한다.
                return

    else:
        hash_table[hash_address] = [index_key, value]


def output_data(data1):
    index_key = hash_key_maker(data1)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:

        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None

            elif hash_table[index][0] == index_key:
                return hash_table[index][1]

    else:
        return None


print(hash('dk') % 10)
print(hash('da') % 10)

print('-' * 100 + '\n')


save_data('dk', '010393838')
save_data('da', '020393838')

print(output_data('dk'))
print(output_data('da'))
print('-' * 100 + '\n')

 

 

          👉 빈번한 충돌을 개선하는 기법

해쉬 함수를 재정의 하거나, 해쉬 테이블 저장 공간을 확대한다면 충돌의 가능성을 낮출 수 있는 것이에요.

예를 들어 5개의 Data를 저장해야 한다면 50%가 넘는 저장 공간인 10개 이상으로 해쉬 테이블 공간을 만드는 것이지요!

 

💡참고 : 해쉬 함수와 키 생성 함수
               - Python의 hash()는 실행할 때마다, Value가 다를 수 있다.
               - 유명한 Hash 함수 종류 : SHA(Secure Hash Alogorithm, 안전한 해시 알고리즘)
                  * 어떤 Data도 유일한 고정 크기의 고정값을 반환해주므로, 해쉬 함수로 유용하게 활용 가능

 

 

          👉 SHA-1

import hashlib

data = 'test'.encode()  # test String을 Byte 형태로 바꿔준다.
hash_obj = hashlib.sha1()
hash_obj.update(b'test')  # test String을 Byte 형태로 바꿔준다.

print('test의 sha1 값은 \'' + str(hash_obj) + '\' 입니다.')
print('-' * 100 + '\n')

hex_dig = hash_obj.hexdigest()  # 16진수로 Byte 형태로 바꾼 값을 hex_dig에 담는다.
print('test의 sha1으로 변환한 값을 다시 16진수로 변환한 값은 \'' + hex_dig + '\' 입니다.')
print('-' * 100 + '\n')

 

 

          👉 SHA-256

import hashlib

data = 'test'.encode()  # test String을 Byte 형태로 바꿔준다.
hash_obj = hashlib.sha256()
hash_obj.update(b'test')  # test String을 Byte 형태로 바꿔준다.

print('test의 sha256 값은 \'' + str(hash_obj) + '\' 입니다.')
print('-' * 100 + '\n')

hex_dig = hash_obj.hexdigest()  # 16진수로 Byte 형태로 바꾼 값을 hex_dig에 담는다.
print('test의 sha256으로 변환한 값을 다시 16진수로 변환한 값은 \'' + hex_dig + '\' 입니다.')
print('-' * 100 + '\n')


# HashTable 충돌 해결 학습

print("연습 문제: 연습 문제 2번(CollistionChainning.py)의 Chaining 기법을 적용한 Hash Table Code에 Key 생성 할수를 SHA-256으로 변경 해 보기")
print('-' * 100)
print("Hash Function : key % 8 \n Hash Key : hash(data)")
print('-' * 100 + '\n')

hash_table = list([0 for i in range(10)])


def hash_function(key_1):
    return key_1 % 10


def hash_key_maker(data1):
    hash_object = hashlib.sha256()
    hash_object.update(data1.encode())
    hex_digest = hash_object.hexdigest()

    return int(hex_digest, 16)  # 문자열인 hex_digest는 16진수를 사용하여 문자열이 되어 있으므로, 이것을 10진수 int로 변환한다.


def save_data(data1, value):
    # Hash Table의 충돌로 인하여 링크드 리스트를 통하여 chainning기법을 통해 해결을 하고자 할 때, 해당 값을 판별하기 위하여 key를 따로 저장
    index_key = hash_key_maker(data1)

    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):

            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return

        hash_table[hash_address].append(index_key, value)

    else:
        hash_table[hash_address] = [[index_key, value]]


def output_data(data1):
    index_key = hash_key_maker(data1)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
            return None
        else:
            return None

    return hash_table[hash_address]


# hash 충돌을 발생 시키기 위해 Test
print(hash_key_maker('dbaa') % 10)
print(hash_key_maker('daaa') % 10)
print(hash_key_maker('dh') % 10)
print('-' * 100 + '\n')

save_data('dbaa', '12345678')
save_data('daaa', '22293848')

print(output_data('dbaa'))
print(output_data('daaa'))
print('-' * 100 + '\n')

print(hash_table)
print('=' * 100 + '\n')

 

 

 

📌 시간 복잡도

---

일반적인 경우 (Collision이 없다고 가정)는 O(Big O)(1)이고, 최악의 경우(Collision이 모두 발생하였을 때를 가정)는 O(n)이 걸립니다!

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1)이라고 말한답니다.

 

          👉 검색에서 Hash Table 사용 예

16개의 배열에 Data를 저장하고, 검색할 때 O(n)인 것이고, 16개의 Data 저장 공간을 가진 위의 Hash Table에 Data를 저장하고, 검색할 땐 O(1)이랍니다!