코딩 인터뷰 완전 분석 자료 구조 해시테이블 - 해시테이블은 효율적인 탐색을 위해 Key를 Value에 대응시킴 해시테이블 구현 방법 1. 키와 해시 코드 계산 > 키의 개수: 무한대, 해시 코드: int, long > 서로 다른 키가 같은 해시 코드를 가리킬 수 있음 2. hash(key) % array_length 방식을 이용해 배열의 인덱스를 구함 3. 각 배열의 인덱스는 키와 값으로 이루어진 연결리스트 존재 해당 방법 사용 시, 주어진 키로 해시 코드를 계산하여 인덱스 계산 > 충돌이 자주 발생할 경우, 최악의 수행 시간은 O(N)이 됨 > 일반적으로는 O(1) > 이진 트리로 구현 시, 탐색 시간: O(logN) ArrayList - 특정 언어에서는 크기를 자동으로 조절 가능 (동적) - O(1..