테드의 기술블로그 ⛏

HashMap은 탐색시 어떻게 O(1)의 성능을 낼까?

들어가며 HashMap은 어떻게 값을 저장하고 관리하는지 또 탐색시 O(1)의 성능은 어떻게 내는지 궁금하여 정리하고자 한다. 이를 분석하기 전 해시 라는 개념부터 정리해본다. 해당 포스팅은 Java 8 기준으로 작성됐다. Hash란? 어떠한 값이 있을 때 hasing 함수에 이 값을 입력하면 해시 값으로 추출할 수 있다. 동일한 값으로는 동일한 해시 값을 얻을 수 있다. 추출된 해시 값은 자료구조에서 데이터를 빠르게 탐색할 때 쓰인다. 어떻게 데이터를 빠르게 탐색할 수 있을까? 해시를 이용한 데이터 탐색은 내부적으로 O(1) 탐색이 가능한 배열을 사용하여 진행된다. 다음은 탐색에 사용되는 해시테이블 (2차원배열)의 모습이다. (실제 Java 8 HashMap은 내부적으로 slot을 연결리스트 또는 Tr..