패스트 캠퍼스 챌린지 14일차 - 자료구조 해쉬테이블 #5

목차

1. 개선된 해쉬 함수
2. Hash Table의 시간 복잡도

• 

1.개선된 해쉬 함수

• 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있음
• 유명한 해쉬 함수들이 있음: SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)
  • 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

• SHA-1

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha1()
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print (int(hex_dig, 16))

• SHA-256

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha256()
hash_object.update(data)
hex_dig = hash_object.hexdigest()
print (int(hex_dig, 16))

---

2.Hash Table의 시간 복잡도

• 일반적인 경우(Collision이 없는 경우)는 O(1)
• 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1) 이라고 말할 수 있음

검색에서 해쉬 테이블의 사용예

• 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)
• 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

https://bit.ly/37BpXiC