Java Collection

ArrayList

List 인터페이스를 구현, Object 배열을 이용해서 데이터를 순차적으로 저장한다.

크기를 변경할 수 없다.

• 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사하는 작업이 필요하다.

비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

• 배열의 중간에 데이터를 삭제, 추가하려면 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.

Stack을 구현하기 적합하다.

• Stack은 순차적으로 데이터를 추가하고 삭제한다.
  • 1, 2, 3 → 3, 2, 1

LinkedList

불연속적으로 존재하는 데이터를 서로 연결한 자료구조, 각 요소들은 자신과 연결된 다음 요소에 대한 주소값과 데이터로 구성되어 있다.

이전요소에 대한 접근이 어렵다.

• 이동 방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다.
  • 이전 요소에 대한 참조도 가능한 DoubleLinkedList 활용

Queue을 구현하기 적합하다.

• Queue는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, 순차적으로 삭제한다면 데이터를 꺼낼 때마다 빈 공간이 생기고 그것을 채우기 위해 데이터의 복사가 발생하기 때문이다.
  • 1, 2, 3 → 1, 2, 3

결과적으로...

순차적인 추가/삭제: ArrayList > LinkedList
중간 데이터 추가/삭제 : ArrayList < LinkedList

HashSet

Set 인터페이스를 구현한 컬렉션, Set의 특징대로 중복된 요소를 저장하지 않는다.

저장순서를 유지하지 않는다

• 중복을 제거하는 동시에 저장순서도 유지하고자 한다면 LinkedHashSet을 사용해야한다.

HashMap

Key와 Value를 묶어서 하나의 데이터(Entry)로 저장한다.

내부 구조

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
	transient Entry[] table;
    ...
    static class Entry implements Map.Entry {
    	final Object key;
        Object value;
    }
}

• Entry라는 내부 클래스를 정의하고, 다시 Entry타입의 배열을 선언해서 생성한다.
  • Key와 Value를 하나의 배열로 다루는 것이 바람직하기 때문이다.
    • Key와 Value는 Object 타입으로 저장한다.
      

많은 양의 데이터를 검색하는데 뛰어나다.

• Hashing을 사용하기 때문이다.

Hashing

해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법이다.

• 배열과 링크드 리스트의 조합으로 되어 있다.

작동 원리

1️⃣저장할 데이터의 키를 해시함수에 넣어 배열의 한 요소를 얻는다.
2️⃣배열의 한 요소에 연결된 링크드 리스트에 데이터를 저장한다.

• 링크드 리스트는 검색에 불리하기 때문에 크기가 커질수록 속도가 떨어진다.