[Algorithm] 해시를 사용한 집합(set)과 맵(map)
🌵 Hash Function (해시 함수) 또는 Hash Algorithm (해시 알고리즘) 임의의 길이의 데이터(key)를 고정된 길이의 데이터(hash)로 매핑하는 함수 이 과정을 hashing이라 한다. 즉, 해시 함수 : key (Input) -> Hash (Output) 이때의 Hash는 저장 위치가 된다. 🌵 Hash Table (해시 테이블) 또는 Hash Map (해시 맵) 해시값을 주소 또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다. 파이썬의 딕셔너리(dictionary) 자료형은 해시 테이블로 구현되어 있다. 장점 해시 테이블은 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있다..
🦖 Programming/Algorithm
2022. 9. 16. 15:26