Collection(List, Map, Set)

<출처 : https://thenicesj.tistory.com/282>

List

: 데이터들이 순서대로 저장, 중복 허용

 

Map

: 순서가 보장되지 않고, Key값 중복은 No, Value값 중복은 OK

 

Set

: 순서가 보장되지 않고, 데이터들의 중복을 허용 X

 

보통 List > Set > Map 순으로 조회 성능차이 발생

 

 

List:

순서 존재

인덱스로 원소에 접근 가능

 

종류

• LinkedList
  
  • 양방향 포인터 구조로 데이터 삽입, 삭제가 빠르다.
    양방향의 연결 리스트로 구성되어 있어 참조하려는 원소에 따라 처음부터 정방향 또는 역순으로 순회 가능 
    데이터를 추가·삭제시 가리키고 있는 주소값만 변경해주면 되기 때문에 ArrayList에 비해 상당히 효율적이다.
  • ArrayList보다 검색이 느리다. 
    인덱스 사용 안하니까 검색 느림, 해당 노드 이동 위해서는 노드 간 포인터 타고 가야 하니까 
• ArrayList
  • 단반향 포인터 구조로 데이터 순차적 접근에 강점을 가진다.
  • 배열을 기반으로 데이터를 저장한다.
    일반 배열과 달리 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있다.
  • 데이터 삽입, 삭제가 느리다.
    데이터의 삽입과 삭제시 ArrayList는 그만큼 위치를 맞춰주어야 한다.
    위의 사진으로 예를들면 5개의 데이터가 있을 때 맨 앞의 2를 삭제했다면 나머지 뒤의 4개를 앞으로 한칸씩 이동해야 한다.
  • 데이터 검색이 빠르다.(인덱스)

 

Set:

순서 존재 X

중복된 데이터 허용 X

(객체를 중복해서 저장할 수 없고, 하나의 null만 저장할 수 있다.)

인덱스 존재하지 않음 -> iterator를 사용

(인덱스가 존재하지 않아서 객체를 확인할 방법이 없어서 iterator로 확인)

 

종류

 

• HashSet
  • 인스턴스의 해시값을 기준으로 저장하기 때문에 순서를 보장하지 않는다.
    • HashSet은 객체를 저장하기 전에 먼저 객체의 hashCode()메소드를 호출해서
      
      해시 코드를 얻어낸 다음 저장되어 있는 객체들의 해시 코드와 비교한 뒤 같은 해시 코드가 있다면 다시 equals() 메소드로
      
      두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않는다.
  • NULL 값을 허용한다.
  • TreeSet보다 삽입, 삭제가 빠르다.

• LinkedHashSet
  
  • 입력된 순서를 보장한다.
• TreeSet
  • 이진 탐색 트리(Red-Black Tree)를 기반으로 한다.
  • 데이터들이 오름차순으로 정렬된다.
  • 데이터 삽입, 삭제에는 시간이 걸리지만 검색, 정렬이 빠르다.

 

Map:

순서 보장 X

인덱스가 따로 존재하지 않음 ->  iterator 사용

단 Map은 Collection을 상속받지 않기 때문에 iterator 바로 사용 불가능

따라서 key값이나 key, value값을 가진 entry객체를 set으로 받아와서 iterator를 사용하게 함

 

Key, Value의 한쌍으로 이루어지는 데이터의 집합
Key에 대한 중복 없음

(중복된 key값이 들어온다면 기존의 값은 없어지고 새로운 값으로 대치)

종류별 특징

 

• HashMap
  • Key에 대한 중복이 없으며 순서를 보장하지 않는다.
  • Key와 Value 값으로 NULL을 허용한다.
  • 동기화가 보장되지 않는다.
  • 검색에 가장 뛰어난 성능을 가진다.
• HashTable
  • 동기화가 보장되어 병렬 프로그래밍이 가능하고 HashMap 보다 처리속도가 느리다.
  • Key와 Value 값으로 NULL을 허용하지 않는다.
• LinkedHashMap
  • 입력된 순서를 보장한다.
• TreeMap
  • 이진 탐색 트리(Red-Black Tree)를 기반으로 키와 값을 저장한다.
  • Key 값을 기준으로 오름차순 정렬되고 빠른 검색이 가능하다.
  • 저장 시 정렬을 하기 때문에 시간이 다소 오래 걸린다.

---

 

참고:

 

Hash값 충돌

 

자바에서 해시값을 생성하는 메소드인 hashCode()의 결과 자료형은 int이다. 
32비트 정수 자료형으로는 완전한 자료 해시 함수를 만들 수 없다.

 

• java hashMap은 해시값 충돌을 피하는 방법으로 Separate Chaining,Open Addressing이 있다.
• http://egloos.zum.com/sweeper/v/925740