List, Set, Map 의 차이

필자가 실무에서 가장 많이 사용하는 자료구조는 List, Set, Map 인데 이들의 차이점은 무엇일까? 간단하게 정리를 해보고자 한다.

 

 

순서가 있는 목록 List

List 는 순서가 있는 목록을 나타낸다.

List 인터페이스의 가장 큰 차이점은 배열처럼 순서가 있다는 것이다. ArrayList 와 Vector 클래스의 사용법은 거의 동일하고 기능도 거의 비슷한 "확장 가능한 배열"이다.

하지만 ArrayList 는 thread safe 하지 않고, Vector 는 thread safe 하다. 

ArrayList 는 객체를 선언할 때 매개 변수를 넣지 않으면 초기 크기는 10이다. 따라서 10개 이상의 데이터가 들어가면 크기를 늘이는 작업이 ArrayList 내부에서 자동으로 수행된다. 참고로 자바의 모든 객체가 생성되면 그 객체가 위치하는 주소가 내부적으로 할당된다.

 

 

순서가 중요하지 않은 Set
순서에 상관 없이, 어떤 데이터가 존재하는지를 확인하기 위한 용도로 많이 사용된다. 

다시 말해서 중복되는 것을 방지하고, 원하는 값이 포함되어 있는지를 확인하는 것이 주 용도이다. 

HashSet	순서가 전혀 필요 없는 데이터를 저장한다.  Set 중에 가장 성능이 좋다.
TreeSet	저장된 데이터의 값에 따라서 정렬되는 셋이다.  red-black 이라는 트리 타입으로 값이 저장되며, HashSet 보다 약간 성능이 느리다.
LinkedHashSet	연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다.  저장된 순서에 따라 값이 정렬된다. 성능이 셋 중에 가장 나쁘다.

 

key-value 형태로 저장되는 Map
Map 에 저장되는 모든 데이터는 키와 값이 존재한다. 키가 없이 값만 저장될 수 없으며 값 없이 키만 저장할 수도 없다. 
키는 해당 Map 에서 고유해야만 하고 값은 Map 에서 중복되어도 전혀 상관 없다.

HashMap	내부적으로 배열로 되어 있다. 검색 성능이 O(1) 이다.
TreeMap	내부적으로 red-black 트리로 되어 있다. 키 값에 대한 Comparator 구현으로 정렬 순서를 바꿀 수 있고, 키 값이 알파벳 순서대로 정렬이 된다. 검색 성능은 O(logn) 이다.
LinkedHashMap	LinkedList 로 저장이 된다. 검색 성능이 O(n) 이다.