7 - Hash Table

해시 테이블에 대해서 알아보겠습니다.

 

핸드폰 전화번호부를 만든다고 생각해볼게요.

 

 

이렇게 쭉 데이터를 쌓아보겠습니다.

 

자료구조는 데이터를 효율적으로 정렬하고 찾기 위해서 사용하겠죠?

 

그래서, 한큐에 찾기 위해 Hash Table이라는 애를 만들었습니다.

 

 

Insert와 Delete의 시간복잡도는 O(1)입니다.

 

최악의 경우 O(n)일 수도 있습니다. (충돌이 났을 때)

 

아래와 같은 그림처럼 충돌이 일어나면 어떻게 해야 하는가?

 

 

이럴 때는, 데이터를 옆에 붙여버리거나, 빈 공간에 할당해줄 수 있습니다.

 

 

 

이 것은 Chaining, Open Addressing 이라고 합니다.

 

자, 그러면 hash table을 구현해보겠습니다.

 

 

# Hash table만들기
hash_table = [[] for _ in range(10)]
print (hash_table)
# Output:
# [[], [], [], [], [], [], [], [], [], []]

# 삽입
def insert(hash_table, key, value):
    # Key값
    hash_key = key % len(hash_table)

    # 중복확인을 위한 애
    key_exists = False
    bucket = hash_table[hash_key]

    # bucket안에 여러개가 들어있으면 반복문으로 돌리면서 확인
    for i, kv in enumerate(bucket):
        # kv(Key, value)
        k, v = kv
        if key == k:
            # 중복을 확인했다면 if else중 if로 가기
            key_exists = True
            break
    # 중복되는 것이 있을 때 append하지 않음
    if key_exists:
        bucket[i] = ((key, value))
    # 중복되는 것이 없으면 append
    else:
        bucket.append((key, value))

insert(hash_table, 10000000, '민수')
insert(hash_table, 10000005, '철수')
insert(hash_table, 20000000, '민지')
# output :
# [[(10000000, '민수'), (20000000, '민지')], [], [], [], [], [(10000005, '철수')], [], [], [], []]
insert(hash_table, 20000000, '민지')
# output :
# [[(10000000, '민수'), (20000000, '민지')], [], [], [], [], [(10000005, '철수')], [], [], [], []]
print(hash_table)

 

참조를 좀 많이했네요..ㅎㅎ

 

참조

[1] - https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o

[2] - https://www.youtube.com/watch?v=Vi0hauJemxA

[3] - https://www.fun-coding.org/DS&AL1-6.html

[4] - https://preamtree.tistory.com/20

[5] - https://www.youtube.com/watch?v=zHi5v78W1f0

[6] - http://blog.chapagain.com.np/hash-table-implementation-in-python-data-structures-algorithms/