공부방 (3) 썸네일형 리스트형 [자료구조] HashMap 내부 동작 - 2 일반적으로 get() 및 put() 연산은 평균적으로 O(1)의 시간 복잡도를 갖는다.(Key 값을 알고 있으면 바로 인덱스로 접근 가능) 하지만 최악의 경우(모든 키가 같은 버킷 인덱스로 매핑되는 경우), 연결 리스트나 균형 이진 트리에서 선형 탐색이 필요하므로 O(n)까지 증가할 수 있다.충돌 관리는 어떻게 할까?1. HashMap의 전체 크기(size)가 threshold (capacity * load factor, 기본적으로 초기 용량 16에 로드 팩터 0.75를 곱한 값인 12) 값을 초과할 경우, HashMap은 배열 크기를 두 배로 확장하고 모든 엔트리들을 새 배열에 재배치하는 재해싱 과정을 거친다. 기존 배열 크기 16에서 32가 되고, threshold도 2배인 24가 된다.static .. [자료구조] HashMap 내부 동작 - 1 개발자라면 한 번쯤은 HashMap을 써봤을 것이다. (필자는 현업에서 비즈니스 로직 구현 시 종종 활용하고 있다.) HashMap의 용도Java에서 HashMap은 매우 중요한 데이터 구조로, 키-값 쌍을 내부적으로 해싱이라는 기법을 사용하여 저장하고 검색한다.해싱은 특정 객체를 고유한 숫자 값인 해시 코드로 변환하는 과정이다. HashMap에서 이 해시 코드는 해당 객체가 저장되어 있는 버킷이라고 하는 위치를 결정한다.데이터 검색 속도: HashMap은 키-값 쌍을 저장하고 검색할 때 일반적으로 상수 시간 복잡도 (O(1))이다. 즉, 맵의 크기에 관계없이 거의 일정한 시간 안에 데이터를 검색할 수 있다.중복 키 방지: HashMap에서 각 키는 유일해야 한다. 동일한 키로 값을 저장하려고 하면 기존.. [자료구조] 우선순위큐(PriorityQueue)에 대한 고찰 우선순위 큐(Priority Queue)는 각 요소에 우선순위(priority)를 부여하여, 우선순위가 가장 높은 요소가 먼저 처리되는 자료구조이다. 일반적인 큐와 다른 점은, 큐에서는 FIFO(First In, First Out) 원칙에 따라 요소가 처리되지만, 우선순위 큐에서는 우선순위에 따라 요소가 처리된다. 우선순위: 각 요소는 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 큐에서 제거된다.동적 크기: 우선순위 큐는 동적으로 크기가 변할 수 있으며, 요소를 추가하거나 제거할 수 있다.구현 방식: 우선순위 큐는 보통 힙(Heap) 자료구조를 사용하여 구현된다. 최소 힙(Min-Heap)이나 최대 힙(Max-Heap)을 사용하여 우선순위를 관리한다.우선순위 큐는 동적으로 크기가 변할 수 있다.. 이전 1 다음
