CS
-
Hash TableCS 2023. 3. 16. 01:16
Hash table 이란? key-value 쌍의 데이터를 입력받아 빠른 속도로 탐색이 가능한 자료구조이다. 좋은 hash 함수란 ? hash 값이 고르게 분포되게 하는 것이다. 시간 복잡도 collision이 많을 수록 시간복잡도는 O(1)에서 O(n)에 가까워진다. Collision이란? 서로 다른 key의 hash 값이 같을 때 collision 이 발생한다. Collision 해결 방법 1. seperate chaining linked list를 이용한다. collision 이 발생하면 linked list에 버킷(bucket)을 추가하여 데이터를 저장한다. 시간복잡도 삽입 검색 삭제 O(1) O(1) O(1) worst case 의 시간복잡도 삽입 검색 삭제 O(n) O(n) O(n) 2. op..