자료구조 - Hash Table

해시 테이블 (Hash Table)

Hash Table은 효율적인 탐색(빠른 탐색)을 위한 자료구조 입니다.

key-value 쌍의 데이터를 입력 받고

hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치를 지정하여

key-value 데이터 쌍을 저장합니다. 

저장, 삭제, 검색의 시간 복잡도는 모두 O(1) 입니다.

Direct-address Table(직접 주소화 테이블)

Direct-address Table은 key 값이 k인 데이터를 index k 위치에 저 장하는 방식입니다 .

student[3] = "김사과"
student[5] = "반하나"
student[6] = "김체리"
student[7] = "두리안"

index	value
0	/
1	/
2	/
3	김사과
4	/
5	반하나
6	김체리
7	두리안
8	/

 

하지만 직접 주소화 방법을 통해 key-value 쌍의 데이터를 저장하고자 하면 많은 문제가 발생합니다.

• 문제점 1) 불필요한 공간 낭비
• 문제점 2) Key값으로 문자열이 올 수 없음

따라서 Direct-address Table(직접 주소화 테이블)의 대안으로 Hash table을 이용할 것입니다.

Hash table

Hash table은 hash function h를 key-value를 저장합니다.

key k 라고 했을 때 h(k) 함수값에 해당하는 index에 key-value를 저장합니다.

h(k)는 키 k의 해시값이다. 라고 표현합니다.

모든 데이터에 key 값은 무조건 존재해야 하며, 중복되는 key 값이 있어서는 안됩니다.

그리고 key-value 데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 합니다.

Collision

collision이란 서로 다른 key의 해시값이 똑같을 때를 의미합니다.

즉, 중복되는 key는 없지만 해시값은 중복될 수 있는데 이때 collision이 발생했다고 합니다.

따라서 collision 이 최대한 적게 나도록 hash function 을 잘 설계해야합니다.

어쩔 수 없이 collision 이 발생하는 경우 seperate chaining 또는 open addressing 등의 방법을 사용하여 해결합니다.

시간 복잡도와 공간 효율성

시간 복잡도는 저장, 삭제, 검색 모두 기본적으로  O(1) 입니다.

다만 collision 으로 인하여 worst case O(n) 이될 수 있습니다.

 

공간 효율성은 떨어집니다 .

데이터가 저장되기 전에 미리 저장공간 (slot, bucket) 을 확보해야 하기 때문입니다.

따라서 저장공간이 부족하거나 채워지지 않은 부분이 많은 경우가 생길 수 있습니다.

	Hash table	Linked list	Array
access	O(1)	O(n)	O(1)
insert	O(1)	O(1)	O(n)
append		O(1)	O(1)
delete	O(1)	O(1)	O(n)

해시테이블 사용법 - dictionary

파이썬의 딕셔너리는 hash table로 구현되어 있습니다.

 hashtable = {}

 

파이썬에선 key를 리스트의 index처럼 생각하면 편합니다.

아래는 리스트 코드인데 리스트에선 value를 access하거나 update 할 때, index를 사용했습니다.

a = [1, 3, 5, 7]
a[3] 	# 5
a[3] = 0

 

dictionary도 아래와 같이 key-value가 있을 때, key를 index처럼 생각하면 됩니다.

student_info = {}
student_info[2022390] = "김사과"
student_info[2022392] = "반하나"
student_info[2022393] = "김체리"
student_info[2022401] = "두리안"

 

in 연산자

• dictionary는 in 연산자와 결합했을 때 강력한 힘을 발휘합니다.
• in은 dictionary에서 key가 존재하는지 확인해줍니다.
• key가 존재하면 True를 반환하고 존재하지 않으면 False를 반환합니다.
• in 연산자의 시간복잡도는 O(1)으로 매우 효율적입니다.

if 2022390 in student_info:
    print("학생이 존재합니다")
else:
    print("학생이 존재하지 않습니다")

 

list도 in 연산자를 사용하여 value가 있는지 확인할 수 있지만 O(n)의 시간 복잡도를 가집니다.

 

Dictionary에 관한 함수

1. dictionary.items()

key와 value 모두 접근할 때 사용합니다.

for student_id, name in student_info.items():
    print(student_id, name)

 

 

결과

2022390 김사과 2022392 반하나 2022393 김체리 2022401 두리안

2. dictionary.keys()

for student_id in student_info.keys():
    print(student_id)

 

결과

2022390 2022392 2022393 2022401

3. dictionary.values()

for name in student_info.value():
    print(name)

 

결과

김사과 반하나 김체리 두리안

4. dictionary.get()

print(student_info.get(2022390))

 

결과

김사과

 

없는 값을 가져오면 None으로 출력됩니다.

 print(student_info.get(1111))

 

결과

None

 

하지만 없는 값을 가져올 때  default를 지정할 수도 있습니다.

 print(student_info.get(1111, "김사과나무"))

 

결과

김사과나무

 

좀 더 응용하면 왼쪽과 같은 코드를 오른쪽 코드처럼 간단하게 표현할 수 있습니다.
if 3 not in a:     a[3] = 1 else:     a[3] += 1	a[3] = 1 + a.get(3, 0)

그렇다면 List 대신에 무조건 Dictionary를 쓰는게 좋을까요?

Dictionary는 List와 다르게 정렬할 수 없으므로 데이터의 순서가 중요할 때는 list를 사용하는 것이 좋습니다.

sorted_dict = sorted(my_dict.items())

 

 혹여나 Dictionary를 위 코드처럼  정렬했다 하더라도 결국에는 list로 반환됩니다.