인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

자바 HashMap은 조회나 삽입 삭제 시 시간복잡도 O(1)로 알고 있어서요

...

자바 HashMap은 내부적으로 해시테이블로 구현되어있어서 그렇지만 일반적으로는 O(log N)이라고 말해야 하나요?

-> 이건 맵이 아니라 해시테이블로 봐야 하며 최악의 경우 O(n), 보통 O(1)로 보는게 맞습니다.

이 해시테이블은 배열과 연결리스트로 구현이 되며 여기서 충돌이 많이 날 경우 연결리스트의 시간복잡도상 O(N)이 걸리는 것이죠.

하지만 자바8부터는 버킷내 연결 리스트의 요소 갯수가 8개 이상이면 Red-Black Tree (레드-블랙 트리) 로 변환됩니다. 이 자료구조는 O(logN)의 시간복잡도를 갖는데요.

즉, 자바의 hashmap의 경우

자바 8미만의 경우

• 최악의 경우 O(N), 보통 O(1)

자바8이상부터

• 연결 리스트의 요소 갯수가 8개 이상일 때 최악의 경우 O(logN), 보통 O(1)

• 연결 리스트의 요소 갯수가 6개 이하일 때 최악의 경우 O(N), 보통 O(1)

이라고 보시면 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 3831568님.

맵(Map) 자료구조의 시간 복잡도에 대한 궁금증이 있으시군요. 맵의 시간 복잡도를 이해하기 위해서 다양한 맵 구현 방법을 알아두는 것이 좋습니다.

1. 일반적인 맵(Map)의 시간 복잡도:

   • 맵은 보통 트리 기반으로 구현되며 이 경우 각각의 연산(삽입, 삭제, 조회)에서 O(log N)의 시간 복잡도를 가지게 됩니다. 이는 맵이 일반적으로 이진 검색 트리(BST)나 자가 균형 이진 검색 트리(예: 레드-블랙 트리)로 구현되기 때문입니다.
     

2. 자바 HashMap의 시간 복잡도:

   • 자바의 HashMap은 해시 테이블로 구현되어 있어, 이상적으로 조회, 삽입, 삭제가 O(1)의 시간 복잡도를 가집니다. 하지만 해시 충돌이 발생하면, 내부적으로 연결 리스트나 트리(자바 8 이상에서는 충돌이 심한 경우 트리로 전환)로 관리되는데, 이로 인해 최악의 경우 O(N)이 될 수 있습니다.
     

3. 왜 O(log N)이라는 설명이 나오는가?

   • 질문에서 언급한 O(log N)은 주로 트리 기반의 맵, 예를 들어 TreeMap을 설명할 때 사용됩니다. TreeMap은 이진 검색 트리로 구현되어 있어 전형적인 O(log N)의 시간 복잡도를 보입니다.
     

따라서 HashMap의 경우 일반적으로 O(1)이지만, 이는 충돌이 적절히 관리되는 이상적인 상황을 가정한 것이며, 구현방식과 사용상황에 따라서는 O(N)이 될 수도 있음을 알고 있는 것이 중요합니다. 특정 맵 구현에 따라 시간 복잡도가 달라질 수 있기 때문에 어떤 상황에서든지적합한 맵을 선택하는 것이 중요합니다.

이와 관련된 구체적인 질문 및 더 자세한 설명이 필요하시다면 다음 링크의 질문과 답변들을 참고해 보세요:

• “map 자료구조의 시간복잡도”
  
• “힙의 참조 시간복잡도가 이해되지 않습니다..”
  

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.