Java 의 주요 자료구조 - ArrayList & Hash Map

ArrayList의 동작 방식

ArrayList는 내부적으로 배열을 사용하여 데이터를 저장하며, 그 작동 원리는 다음과 같다.

1. 내부 배열 관리
   • 데이터를 순차적으로 저장하는 배열을 사용한다.
   • 배열은 일정한 용량(Capacity)을 가지며, 초기 용량은 지정할 수 있다.
2. 용량 확장 방식
   • add 연산 시 남은 공간이 없으면, 현재 용량의 50%를 추가하여 새로운 배열을 생성한다.
   • 이 과정에서 기존 배열의 내용을 arraycopy 메서드를 사용하여 새로운 배열로 복사한다.
   • 용량 확장 시 복사로 인한 성능 오버헤드가 발생하지만, 대부분의 삽입 연산은 평균적으로 O(1)의 시간 복잡도를 유지한다.
   • 참고로, C++의 vector는 용량을 두 배로 늘리는 방식으로 확장하는 점에서 차이가 있다.

---

해시테이블의 작동 원리 및 충돌 해결 방법

해시테이블은 키-값 쌍을 효율적으로 저장하고 검색하기 위한 자료구조로, 기본 개념과 충돌 해결 방식은 아래와 같다.

기본 개념

• 해시 함수
  • 키를 해시 함수에 전달하여, 해당 키가 저장될 버킷(bucket)의 인덱스를 결정한다. O(1)의 시간복잡도를 가진다.
• 버킷
  • 하나 이상의 키-값 쌍을 저장할 수 있는 자료구조이다.
  • 해시 함수에 의해 동일한 버킷으로 할당되는 경우, 여러 항목이 한 버킷에 저장될 수 있다.

충돌 해결 방법

해시 함수가 서로 다른 키에 대해 동일한 버킷을 반환하는 충돌 상황에 대비해 두 가지 주요 방식이 사용된다.

체이닝(Chaining)

• 특징
  • 자바의 해시테이블은 기본적으로 체이닝 방식을 채택한다.
  • 각 버킷은 링크드 리스트와 같이 여러 키-값 쌍을 저장할 수 있도록 구성된다.
  • Java 8 이후부터 버킷에 저장된 항목 수가 일정 임계치(보통 8)를 초과하면, 연결 리스트를 레드 블랙 트리로 변환하여 검색 속도를 향상시킨다.
• 장점
  • 로드 팩터(load factor)가 1을 넘어도 안정적으로 동작할 수 있다.
• 단점
  • 추가적인 포인터 사용으로 인한 메모리 부하가 발생한다.

오픈 어드레싱 (Open Addressing)

• 특징
  • 충돌이 발생하면, 해시 테이블 내에서 순차적으로 다음 인덱스 등을 탐색하여 빈 공간을 찾아 데이터를 저장한다.
  • 선형 탐사, 이차 탐사, 이중 해싱 등의 방식이 있다.
• 장점
  • 메모리 사용 효율이 높으며, 부하율이 낮은 상황에서는 빠른 접근 속도를 제공한다.
• 단점
  • 단순한 충돌 해결 방식으로 인해 삽입이나 삭제 시 복잡성이 증가할 수 있다.
  • 실제 삭제 대신 '삭제 표시'를 사용해야 하므로, 지속적인 사용 시 테이블의 성능이 저하될 위험이 있다.