자료구조 - 해쉬

해쉬

파이썬에서의 Dictionary.key + Value의 조합. Key에 Value를 저장하는 데이터 조합.

studentIds = {
"이다솜" : 123,
"오정철" : 145,
"이주경" : 563 }

# 이름이 Key, 숫자가 value

위의 코드를 보기 좋게 정리하면 아래의 표.

"이다솜"	123
"오정철"	145
"이주경"	563
...	...

이때 해쉬 자료구조에서 가장 중요한 것은 Key는 중복될 수 없다는 것.

 

 

해쉬의 시간복잡도

1. Key를 이용해서 Value 가져올 때 : 대략 O(1)

print(studentIds["이다솜"])    # 크기와 상관없이 키를 입력하면 바로 나오니까

Big-O 시간복잡도 = 대략 O(1)

2. Key가 존재하는지 확인할 때 : 대략 O(1)

if("이다솜" in studentIds):    # "이다솜"이라는 key가 studentIds라는 자료구조에 포함이 되나?
                               # 이다솜은 key값에 있어 -> 코드 실행O

if("김주영" in studentIds):    # "김주영"이라는 key가 studentIds라는 자료구조에 포함이 되나? 
                               # 김주영은 key값에 없어 -> 코드 실행X

# Big-O 시간복잡도 = 대략 O(1)

3. Key, Value 추가할 때 : 대략 O(1) 

# 원래 없던 김주영이라는 key에 938의 원소를 추가하고 싶다면
studentIds["김주영"] = 938

# Big-O 시간복잡도 = 대략 O(1)

4. 해당 Key의 Value를 변경할 때 : 대략 O(1)

# 이다솜 key의 value를 555로 바꾸고 싶을 때
studentIds["이다솜"] = 555

# Big-O 시간복잡도 = 대략 O(1)

지금까지 살펴본 해쉬 자료구조의 모든 동작에 있어서 Big-O 시간복잡도는 O(1)으로 굉장히 효율적이야.

 

 

해쉬의 공간복잡도

해쉬의 크기가 N일 때, 해쉬의 공간복잡도 = O(N). 

해쉬는 자료구조의 크기에 구애받지 않는 시간복잡도에 비해서, 그렇게 효율적이지 못한 공간복잡도를 가짐.

해쉬는 자료구조의 특성상 원래 차지하는 자료구조 자체의 메모리보다 더 많은 여유공간이 있어야 돼. 해쉬는 데이터가 입력되지 않은 여유 공간이 많아야 성능 유지가 되거든. 데이터간의 충돌을 방지해야하기 때문. 충돌이 일어난다면 그 충돌을 피해서 정보를 저장해야할 공간을 따로 마련해야 돼. (이 설명은 여기까지만) 그렇기 때문에 사실상 O(N)보다 더 비효율적인 공간복잡도를 가지게 됨. 

 

 

Set

Value 없이 Key만 있는 딕셔너리. 집합이라고도 불림.

 

studentNames = {"이다솜", "오정철", "이주경"}

해쉬와 마찬가지로 key는 중복 허용이 안됨.