Hash Table
-
Hash Table과 array 차이점, 설명영상, 글 요약 2023. 1. 3. 00:01
#1 서론 어떤 사람이 좋아하는 국가들이 배열에 저장되어있다고 가정하자. 그럼 어떤사람이 '한국'을 좋아하는지 찾으려고 한다면 선형검색(Linear Search)을 해서 찾아야 할 것이다. 그럼 시간 복잡도는 O(n)일 것이다. 이것은 그리 효율적이지 않다. 이보다 더 효율적으로 만들 수 있다. 그것을 알아본다. #1-1 시작하기 전 알아야 할 것 Hash Table Key : Value 형태로 이루어진 자료구조 예시 Python - Dictionary JS - Object 보통 시간복잡도는 O(1)이지만, 항상 그런것은 아니다. 이유는 Hash function에서 설명한다. Hash function 아래 그림1과 같이 key를 받아서 일정한 알고리즘을 거친 뒤 인덱스로 변환하여 데이터 배열에 저장한다...