
Coding_Algorithm/DS_Algorithm
Hash Table/Algorithm and Collision Resolution
00. Hash Table이란? Hash Table이란, Dictionary 구조를 구현하는 효율적인 자료 구조 중 하나이다. cf. Dictionary: INSERT, SEARCH, 그리고 DELETE 기능이 있는 집합 참고로 Hash Table을 사용하였을 때 SEARCH하는데 걸리는 Time Complexity는 다음과 같다. worst case: Θ(n^2) expected time: O(1) Hash Table에는 여러 가지 종류가 존재한다. 이에 대해서 알아보도록 하자. 01. Direct Address Table 가장 단순한 형태의 Hash Table이다. Key값이 그대로 테이블의 인덱스 값이 되며, 따로 처리할 내용이 없기 때문에 Time Complexity도 항상 O(1)이다. 각 op..