‘ArrayList - contains()' vs. ‘HashMap - containsKey()'

‘ArrayList - contains()' 의 시간 복잡도

• [ ] contains(Object o)의 동작 방식과 그에 따른 시작 복잡도를 알아보자 !

동작 방식

1. 주어진 객체가 ArrayList에 존재하는지 확인한다.
2. 해당 메서드는 내부적으로 리스트의 처음부터 끝까지 모든 요소를 순차적으로 검사하여, 주어진 객체가 리스트에 있는지 확인한다 ! → O(n) - Worst case (리스트의 길이가 n일 때)

‘HashMap - containsKey()' 의 시간 복잡도

• [ ] containsKey(Object key)의 동작 방식과 그에 따른 시작 복잡도를 알아보자 !

동작 방식

1. 파라미터값으로 받은 키에 대해 hashCode() 메서드를 호출하여 해당 키의 해시 값을 계산한다.
2. 해시 값으로 key-value 쌍이 저장될 버킷(메모리 슬롯)을 결정하고 해당 버킷에 접근한다. ⚠️ 단, 해시 충돌로 인해 동일한 해시 값을 가진 여러 키가 같은 버킷에 저장되어 있을 수 있다
3. 충돌이 없다면, 바로 해당 버킷에서 저장된 요소를 꺼내면 된다. → O(1) - Average case
4. 충돌이 있다면, 해시 값이 동일한 여러 키들 중에서 일치하는 키를 찾기 위해 해당 버킷의 여러 요소들을 equals() 메서드로 비교해야 한다. → O(log n) - Worst case (Java 8 이후)

<aside> 💡

충돌을 해결하기 위해 이전에 사용하던 Seperate Chaining 기법 !

• 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로써 모든 자료를 해시테이블에 담는 것이다. → 해당 버킷에 데이터가 있다 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식(연결 리스트; Linked-List)으로 구현하는 것이라, **최악의 경우(worst case)**에 시간 복잡도가 O(n)이 소요되는 것이다 ! </aside>

<aside> 💡

Java 8 이후부터 해시 충돌이 많은 최악의 경우에도 시간 복잡도가 O(log n)인 이유 ?

• Java 8부터 충돌이 많은 경우 연결 리스트(Linked-List)가 아닌 트리 구조(Red-Black Tree)를 사용하여 충돌을 해결하기 때문이다 ! </aside>

참고 자료 - Red-Black Tree

이진 트리(Binary Tree)의 성능을 향상시킨 레드-블랙 트리(Red-Black Tree)