[Java] Java Collection Framework의 모든것을 알아보자

Java Collection Framework(JCF)란?

Collection이란 객체 그룹을 나타내는 객체입니다. 

Collection <E>에 기본형 int를 넣지 못하고 객체인 Integer를 넣는 것을 떠올리시면 됩니다.

 

컬렉션 프레임워크는 컬렉션을 표현하고 조작하기 위한 통합 아키텍처로, 세부 구현 사항과 독립적으로 컬렉션을 조작할 수 있습니다.

 

데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래스로 구현해 놓은 것으로 생각하시면 됩니다.

 

Framework vs Library

둘 다 개발 생산성을 증가시켜준다는 공통점이 존재하지만 제어를 누가 할 수 있느냐에 따른 차이점이 있습니다.

라이브러리는 개발자가 라이브러리를 제어할 수 있으며, 프레임워크는 프레임워크가 개발자를 제어합니다.

 

Collection Framework의 구성 요소

공식문서에서는 Collection Framework의 구성요소들을 아래와 같이 설명합니다.

---

• Collection interfaces. Represent different types of collections, such as sets, lists, and maps. These interfaces form the basis of the framework.
• General-purpose implementations. Primary implementations of the collection interfaces.
• Legacy implementations. The collection classes from earlier releases, Vector and Hashtable, were retrofitted to implement the collection interfaces.
• Special-purpose implementations. Implementations designed for use in special situations. These implementations display nonstandard performance characteristics, usage restrictions, or behavior.
• Concurrent implementations. Implementations designed for highly concurrent use.
• Wrapper implementations. Add functionality, such as synchronization, to other implementations.
• Convenience implementations. High-performance "mini-implementations" of the collection interfaces.
• Abstract implementations. Partial implementations of the collection interfaces to facilitate custom implementations.
• Algorithms. Static methods that perform useful functions on collections, such as sorting a list.
• Infrastructure. Interfaces that provide essential support for the collection interfaces.
• Array Utilities. Utility functions for arrays of primitive types and reference objects. Not, strictly speaking, a part of the collections framework, this feature was added to the Java platform at the same time as the collections framework and relies on some of the same infrastructure.

---

• Interfaces: These are abstract data types that represent collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages, interfaces generally form a hierarchy.
• Implementations: These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.
• Algorithms: These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces. The algorithms are said to be polymorphic: that is, the same method can be used on many different implementations of the appropriate collection interface. In essence, algorithms are reusable functionality.

---

위의 내용을 요약하면 다음과 같습니다.

 

- 인터페이스를 사용하여 표현의 세부 사항과 독립적으로  컬렉션을 조작할 수 있습니다. 객체지향 언어에서 이러한 인터페이스는 일반적으로 계층 구조를 형성합니다.

 

- (일반, 레거시, 특수 목적, 동시성, 래퍼, 편리, 추상) 인터페이스를 구체적으로 구현합니다. 본질적으로 재사용 가능한 데이터 구조입니다.

 

- 목록 정렬과 같은 컬렉션에 유용한 기능을 하는 정적 메서드를 구현합니다. 다형성을 통해 다양한 컬렉션에서 동일한 메서드를 사용할 수 있습니다.

 

 

---

Java Collection Framework을 사용하는 이유?

공식문서에는 JCF를 사용하는 장점에 대해 아래와 같이 설명합니다.

• Reduces programming effort by providing data structures and algorithms so you don't have to write them yourself.
• Increases performance by providing high-performance implementations of data structures and algorithms. Because the various implementations of each interface are interchangeable, programs can be tuned by switching implementations.
• Provides interoperability between unrelated APIs by establishing a common language to pass collections back and forth.
• Reduces the effort required to learn APIs by requiring you to learn multiple ad hoc collection APIs.
• Reduces the effort required to design and implement APIs by not requiring you to produce ad hoc collections APIs.
• Fosters software reuse by providing a standard interface for collections and algorithms with which to manipulate them.

---

• Reduces programming effort: By providing useful data structures and algorithms, the Collections Framework frees you to concentrate on the important parts of your program rather than on the low-level "plumbing" required to make it work. By facilitating interoperability among unrelated APIs, the Java Collections Framework frees you from writing adapter objects or conversion code to connect APIs.
• Increases program speed and quality: This Collections Framework provides high-performance, high-quality implementations of useful data structures and algorithms. The various implementations of each interface are interchangeable, so programs can be easily tuned by switching collection implementations. Because you're freed from the drudgery of writing your own data structures, you'll have more time to devote to improving programs' quality and performance.
• Allows interoperability among unrelated APIs: The collection interfaces are the vernacular by which APIs pass collections back and forth. If my network administration API furnishes a collection of node names and if your GUI toolkit expects a collection of column headings, our APIs will interoperate seamlessly, even though they were written independently.
• Reduces effort to learn and to use new APIs: Many APIs naturally take collections on input and furnish them as output. In the past, each such API had a small sub-API devoted to manipulating its collections. There was little consistency among these ad hoc collections sub-APIs, so you had to learn each one from scratch, and it was easy to make mistakes when using them. With the advent of standard collection interfaces, the problem went away.
• Reduces effort to design new APIs: This is the flip side of the previous advantage. Designers and implementers don't have to reinvent the wheel each time they create an API that relies on collections; instead, they can use standard collection interfaces.
• Fosters software reuse: New data structures that conform to the standard collection interfaces are by nature reusable. The same goes for new algorithms that operate on objects that implement these interfaces.

---

위의 내용을 요약하면 다음과 같습니다.

 

- 데이터 구조와 알고리즘을 제공하여 직접 작성할 필요가 없도록 해줍니다.(시간 절약)

 

- 데이터 구조 및 알고리즘을 고성능으로 구현하여 제공합니다. 

 

- 각 인터페이스의 다양한 구현이 상호 교환 가능하기 때문에 프로그램 구현을 전환하여 프로그래밍을 조정할 수 있습니다.

 

- 여러가지 collection api들을 학습하지 않도록 해줍니다.  과거에는 컬렉션을 조작하는 데 사용되는 작은 하위 API가 존재했으며 하위 API의 일관성이 거의 없었기 때문에 처음부터 각각 배워야 했고 사용할 때 실수하기 쉬웠습니다.

 

- 새로운 API를 설계하기 위해 디자이너와 구현자는 새로운 것을 발명하기보다는 표준 인터페이스를 사용할 수 있습니다.

 

- 표준 인터페이스를 제공하여 소프트웨어 재사용을 촉진합니다.

---

Java Collection Framework의 도입 배경

JCF가 존재하기 전에는 데이터를 그룹핑하기 위해 Array, Vector, Hashtable을 사용했습니다.

이 Collection들에는 공통 인터페이스가 존재하지 않았기 때문에 사용 목적이 동일하더라도 각자 따로 정의해야 하는 문제가 있었습니다.

또한 각각의 Collection마다 사용하는 메서드, 문법, 생성자가 달랐기 때문에 개발자가 이들을 사용하면서 혼동하기 쉬웠습니다.

예를 들면 데이터를 추가하기 위해 vector는 addElement() 메서드를 사용하고, Hashtable은 put메서드를 사용합니다.

따라서 공통 인터페이스가 필요하다고 판단하였고 JCF가 등장하게 됩니다.

---

Java Collection Framework의 계층구조

JCF계층 구조 (https://velog.io/@hong-brother/JAVACollection-JCF)

Interface Iterable <T>

가장 최상위 인터페이스로 Iterable 인터페이스를 구현하고 있는 객체들은 for-each 반복을 수행할 수 있습니다.

for (T t : this)
	action.accept(t);

 

Interface Collection <E>

컬렉션 계층 구조의 루트 인터페이스입니다.

컬렉션은 요소라고 하는 객체 그룹을 나타냅니다.

일부 컬렉션은 중복 요소를 허용하고 다른 일부 컬렉션을 허용하지 않습니다.

일부 컬렉션은 정렬되며 다른 일부 컬렉션을 정렬되지 않습니다.

JDK는 Collection 인터페이스의 직접적인 구현을 제공하지 않으며 하위 인터페이스(Set, List, Queue, Deque)의 구현을 제공합니다.

 

Interface Set <E>

Collection 인터페이스를 확장하는 인터페이스로 수학적 집합 추상화를 모델링한 중복 요소가 없고 순서가 존재하지 않는 컬렉션입니다.

 

Set 인터페이스는 어떻게 중복 요소를 제거할까요?

1. hashCode를 비교합니다.

2. equals 메서드를 통해 값을 비교합니다.

 

둘 중 하나라도 같지 않으면 중복요소라고 판단하지 않고 집합에 추가하고 true를 반환합니다.

하지만 둘 다 모두 같으면 이는 같은 요소라고 판단하고 집합에 추가하지 않고 false를 반환합니다.

 

hashCode란?

해시 코드란 객체를 식별하는 하나의 정수 값을 말합니다. Object의 hashCode() 메서드는 객체의 메모리 번지를 이용하여 해시 코드를 만들어 반환하기 때문에 객체마다 다른 값을 가지고 있습니다.

public native int hashCode();

native 키워드는 메서드가 JNI라는 native code로 구현되었음을 의미합니다.

Java가 아닌 C/ C++ 등의 언어로 구현된 부분을 JNI를 통해 Java에서 이용하고자 할 때 사용됩니다.

 

equals 메서드란?

public boolean equals(Object obj) {
	return (this == obj)
}

2개의 객체가 동일한지 검사하기 위해 사용되는 메서드로 2개의 객체가 가리키는 곳이 동일한 메모리 주소일 경우에만 동일한 객체가 됩니다.

 

hashCode와 equals 메서드

Object o1 = new Object();
Object o2 = new Object();
System.out.println(o1.hashCode());
System.out.println(o2.hashCode());
System.out.println(o1==o2);
System.out.println(o1==o1);
//결과
705927765
366712642
false
true

 

 

객체는 서로 다른 주소를 가질 것이며 <E>는 객체 타입일 텐데 어떻게 Set <Integer>가 중복제거를 할 수 있을까요?

Integer o1 = new Integer(3);
Integer o2 = new Integer(3);	
System.out.println(o1==o2);
System.out.println(o1.hashCode());
System.out.println(o2.hashCode());
System.out.println(o1.equals(o2));
//결과
false
3
3
true

어떻게 hashCode가 3이 나오고 o1==o2는 false인데 o1.equals(o2)는 true가 나올 수 있을까요?

 

내부적으로 Integer 객체가 hashCode()와 equals()를 재정의하고 있기 때문입니다.

@Override
public int hashCode() {
	return Integer.hashCode(value);
}
    
public static int hashCode(int value) {
	return value;
}

  public boolean equals(Object obj) {
	if (obj instanceof Integer) {
		return value == ((Integer)obj).intValue();
	}
	return false;
}

 

 

그러면 Set <String>은 중복제거를 할 수 있을까요?

String o1 = "hello";
String o2 = "hello";		
System.out.println(o1==o2);
System.out.println(o1.hashCode());
System.out.println(o2.hashCode());
System.out.println(o1.equals(o2));
//결과
true
99162322
99162322
true

메모리의 주소도 동일하고 hashCode값도 동일하기 때문에 가능합니다.

근데 서로 다른 객체인데 왜 메모리 주소가 동일할까요?

이는 String이 불변 객체이기 때문인 것과 관련이 있는데 다음 글을 보시면 이해하실 수 있습니다.

https://junuuu.tistory.com/134?category=989459 

[Java] String이 불변 객체인 이유는?

 

String 클래스 또한 hashCode()와 equals()를 재정의하고 있습니다.

public int hashCode() {
	int h = hash;
		if (h == 0 && value.length > 0) {
			char val[] = value;
            
			for (int i = 0; i < value.length; i++) {
				h = 31 * h + val[i];
			}
			hash = h;
		}
	return h;
}

public boolean equals(Object anObject) {
	if (this == anObject) {
		return true;
	}
	if (anObject instanceof String) {
		String anotherString = (String)anObject;
		int n = value.length;
		if (n == anotherString.value.length) {
			char v1[] = value;
			char v2[] = anotherString.value;
			int i = 0;
			while (n-- != 0) {
				if (v1[i] != v2[i])
					return false;
					i++;
			}
			return true;
		}
	}
	return false;
}

실제 문자열 값인 value를 통해 hashCode를 생성하고 값을 비교하기 때문에 중복제거가 가능합니다.

 

 

그러면 우리가 정의한 Set <MyClass>은 중복제거를 할 수 있을까요?

class myClass {
	int x;
	int y;

	public myClass(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}

public class CollectionTest {

	public static void main(String[] args) {
    
		myClass o1 = new myClass(1,2);
		myClass o2 = new myClass(1,2);
        
		System.out.println(o1 == o2);
		System.out.println(o1.hashCode());
		System.out.println(o2.hashCode());
		System.out.println(o1.equals(o2));
	}
}

//결과
false
705927765
366712642
false

메모리 주소도 다르고 실제 x, y값은 동일하지만 o1.equals(o2) 또한 false로 나옵니다.

 

위의 Integer 객체와 String객체가 hashCode()와 eqauls()를 재정의한 것처럼 MyClass객체 또한 hashCode와 equals메서드를 재정의해야 중복제거가 가능합니다.

@Override
public int hashCode() {
	final int prime = 31;
	int result = 1;
	result = prime * result + x;
	result = prime * result + y;
	return result;
}

@Override
public boolean equals(Object obj) {
	if (this == obj)
		return true;
	if (obj == null)
		return false;
	if (getClass() != obj.getClass())
		return false;
	myClass other = (myClass) obj;
	if (x != other.x)
		return false;
	if (y != other.y)
		return false;
	return true;
}

hashCode와 equals 메서드를 재정의하고 실행하면 hashCode도 같게 나오고 equals도 true로 출력됩니다.

 

해쉬 코드 생성에 31이라는 수를 사용하는 이유는 무엇일까요?

31N = 32N - N으로 32는 2^5로 어떤 수에 대한 32를 곱한 값은 shift 연산을 통해 쉽게 구현할 수 있습니다.

따라서 31 * i = (i << 5) - i의 식이 성립합니다.

곱셈보다 비트 연산이 성능이 훨씬 빠르기 때문에 31이라는 값을 선택한 것입니다.

 

컬렉션과는 조금 관련 없지만 다음은 결과는 어떻게 될까요?

//String str = "hello"
String str = new String("hello");
Object o1 = new Object();
System.out.println(str);
System.out.println(o1);

String str = "hello"라고 사용하는 것이 조금 더 바람직하지만 형식의 통일을 위해 new 키워드를 사용해보겠습니다.

String과 Object는 둘 다 객체인데 다음의 결과는 어떻게 될까요?

println(str) = hello

println(o1) = java.lang.Object@2a139a55

 

str과 o1은 객체이기 때문에 둘 다 메모리 주소가 나와야 하는 것 아닐까요? 어떻게 이것이 가능할까요?

println(Object x) 메서드의 내부구조를 보게 되면 다음과 같습니다

 public void println(Object x) {
        String s = String.valueOf(x);
        synchronized (this) {
            print(s);
            newLine();
        }
    }

String.valueOf(x)의 내부구조를 보게 되면 다음과 같습니다

  public static String valueOf(Object obj) {
        return (obj == null) ? "null" : obj.toString();
    }

obj가 null이 아니라면 toString() 메서드를 호출하여 반환합니다.

 

그러면 이제 String 클래스와 Object 클래스의 toString() 메서드를 살펴보겠습니다.

Object.toString()의 내부구조

    public String toString() {
        return getClass().getName() + "@" + Integer.toHexString(hashCode());
    }

String.toString()의 내부구조

 public String toString() {
        return this;
    }

이러한 이유 때문에 String은 값을 출력하게 되고 Object는 클래스이름@hashCode()값을 출력하게 됩니다.

 

Interface List <E>

순서가 지정된 컬렉션으로 사용자는 목록에서 각 요소가 삽입되는 위치를 정밀하게 제어할 수 있습니다.

이는 인덱스로 접근 가능함을 의미하고, set 인터페이스와는 다르게 중복요소를 허용합니다.

 

Interface Queue <E>

FIFO(First In First Out) 선입선출 구조를 일반적으로 가지지만 반드시 그런 것은 아닙니다.

실제로 priorityQueue는 FIFO가 아닌 지정된 우선순위에 따라 요소가 먼저 나갑니다.

 

Inferface Deque <E>

doubl ended queue의 약자로 양쪽 끝에서 요소 삽입 밑 제거를 지원하는 선형 컬렉션입니다.

FIFO 선입선출 큐로도 사용할 수 있으며 LIFO(Last In Last Out) 후입 선출 스택으로도 사용할 수 있습니다.

레거시인 stack 클래스보다 덱을 사용해야 합니다.

 

Inferface Map <K, V>

key를 value에 매핑하는 객체입니다.

Entry는 key-value 쌍을 의미합니다.

맵에는 중복 key가 포함될 수 없지만 value는 중복이 가능합니다.

데이터의 순서가 보장되지 않습니다.

---

JCF 비교 및 디테일

Array vs ArrayList

우선 Array와 ArrayList는 거의 모든 것이 동일합니다.

가장 큰 차이점으로 Array는 정적 배열로 초기에 크기를 정하면 고정되어 조정할 수 없습니다.

ArrayList는 가변 길이를 가지지만 내부적으로는 배열로 구성되어 있습니다. 

 

ArrayList는 길이를 지정하지 않으면 초기 용량으로는 10을 가집니다.

만약 용량을 지정하면 그 용량만큼 생성되기 때문에 적절한 용량을 지정하는 것이 효율적입니다.

만약 초기 용량에서 빈번하게 배열의 복사가 발생한다면 비효율적일 것입니다.

private static final int DEFAULT_CAPACITY = 10;

 

ArrayList는 어떻게 길이를 증가시키는 것이고 크기는 얼마씩 증가할까요?

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); //기존 용량 + 기존 용량 /2 (우측 shift 연산)
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

만약 설정한 capacity를 넘어서 더 많은 객체가 들어오게 된다면 배열 크기를 1.5배 증가시킵니다.

이후에 크기가 늘어난 배열에 기존의 배열을 copy 합니다.

 

ArrayList vs Vector

vector는 예전에 자바에서 제공했던 레거시 클래스입니다.

필요에 따라 크기를 동적으로 조절할 수 있는 동적 배열을 구현합니다.

 

ArrayList와 Vector의 첫 번째 주요한 차이점은 동기화의 차이입니다.

 public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

Vector 클래스의 경우에는 메서드가 synchronized로 동기화되어 있습니다.

이는 즉 한 번에 하나의 스레드만 접근 가능함을 의미합니다.

하지만 ArrayList는 동시에 여러 스레드가 접근할 수 있습니다.

하지만 멀티스레드 환경에서도 Vector는 레거시 클래스이기 때문에 사용이 권장되지 않습니다.

 

ArrayList와 Vector의 두 번째 주요한 차이점은 배열의 크기 증가량의 차이가 존재합니다

private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
						capacityIncrement : oldCapacity);
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList는 1.5배 증가한 반면에 Vector는 특별하게 capacityIncrement를 지정하지 않는다면 2배만큼 증가합니다.

 

ArrayList vs LinkedList

두 클래스 모두 중복을 허용하고 순서를 유지하며 원소들을 관리합니다.

하지만 index의 삽입, 삭제에 다른 시간 복잡도를 가지므로 사용할 자료구조의 특성에 맞추어 적절하게 사용해야 합니다.

https://devlog-wjdrbs96.tistory.com/64

 

또한 순차 접근도 참조의 지역성(한번 참조한 데이터는 다시 참조될 가능성이 높음)때문에 LinkedList보다 ArrayList가 훨씬 빠릅니다.

n개의 자료를 저장할 때 LinkedList는 자료들을 저장공간에 불연속적 단위로 저장합니다.

LinkedList는 메모리 이곳 저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모됩니다.

 

 

 

Legacy Collection인 vector와 stack의 상속관계의 오류

stack은 LIFO(Last In First Out) 마지막에 들어온 데이터가 먼저 나가는 자료구조입니다.

따라서 스택의 꼭대기에 있는 원소를 참조할 수 있어야 하지만 vector를 확장하여 stack을 구현하고 있기 때문에 꼭대기가 아닌 맨 아래에 있는 원소를 참조하거나, 중간에 원소를 추가하는 것 또한 가능합니다.

 

멀티스레드 프로그래밍

 

동시성 문제란?

여러 개의 Thread에서 동시에 컬렉션에 접근하는 경우에는 사용하고자 하는 컬렉션이 thread-safety 한지 API reference를 확인해 볼 필요가 있습니다.

 

Collections.synchronizedList vs vector

보통 vector 대신에 ArrayList를 사용하라는 말이 많이 듣습니다.

Vector는 동기화된 함수로 가득 차 있기 때문에 싱글 스레드 프로그램에서 효율적이지 않습니다.

따라서 multi-thread 프로그램을 짤 때는 Collections.synchronizedList를 사용합니다.

 

그러면 syncronized 되면 multi-thread에 안전한가?

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class concurrencyTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		final List<String> list = Collections.synchronizedList(new ArrayList<String>());
		final int nThreads = 2;
		ExecutorService es = Executors.newFixedThreadPool(nThreads);
		for (int i = 0; i < nThreads; i++) {
			es.execute(new Runnable() {
				public void run() {
					while (true) {
						try {
							list.clear();
							list.add("888");
							list.remove(0);
						} catch (IndexOutOfBoundsException ioobe) {
							ioobe.printStackTrace();
						}
					}
				}
			});
		}

	}

}

Thread A가 remove(0)을 하려는 순간 Thread B가 clear()를 한다면 remove를 수행할 것이 없는데 remove를 수행하기 때문에 문제가 발생할 수 있습니다.

 

따라서 다음과 같이 함수들을 묶어서 동기화시켜주어야 합니다.

synchronized (list) {
	list.clear();
	list.add("888");
	list.remove(0);
}

즉, Collections.synchronizedList를 쓴다고 해서 동기화 문제를 회피할 수 있지는 않습니다.

 

java.uti.concurrent.CopyOnWirteArrayList 클래스

동기화시키는 synchronizedList 메서드와는 다르게 copy-on-write를 이용하여 충돌을 막습니다.

ArrayList wirte 할 때 copy 한다는 의미'로 컬렉션에 대하여 write 할 때마다, 내부에 확보된 배열을 통째로 복사하여 충돌을 막습니다.

 

실제로 내부구조를 보면 synchronized()를 사용하지 않고 ReentrantLock을 사용하여 동기화를 진행합니다.

Collections.synchronizedList와 동일하게 CopyOnWriteArrayList 클래스를 사용한다고 동기화 문제가 모두 해결되지 않습니다.

해결방법은 위와 동일하게 synchronized(list)로 함수들을 묶어 동기화시켜주면 됩니다.

 

아니면 lock을 사용하여 함수 위아래로 lock을 걸어주면 됩니다

ReentrantLock lock = new ReentrantLock();

lock.lock();
list.clear();
list.add("888");
list.remove(0);
lock.unlock();

 

 

Collection vs Collections의 차이점?

Collection은 인터페이스로 컬렉션 프레임워크의 루트 인터페이스입니다.

Collections는 클래스로 개발자가 Collection Framework와 효과적으로 작업할 수 있도록 필요한 정렬 검색과 같은 정적 메서드들이 존재합니다.

대표적으로 sort(), min(), max() 등이 존재합니다.

 

Collection을 정렬하기 위해 비교하기 위해서 어떻게 해야 하나?

java.util.Collections 클래스의 static 메서드인 sort()를 이용합니다.

API문서에는 오버 로딩된 두 개의 sort() 메서드가 존재합니다.

 

Comparable <T> 인터페이스 이용

public static <T extends Comparable<? super T>>
void sort​(List<T> list)

우리가 만든 클래스를 정렬하고 싶다면 Comparable 인터페이스를 구현하여 compareTo 메서드를 구현한 뒤 Collection.sort(myList); 를 통해 정렬할 수 있습니다.

 

근데 interface를 구현하는데 implements가 아닌 extends를 사용하는 이유는 무엇일까요?

자바 엔지니어들이 제네릭을 설계할 때, 일반 클래스의 하위 클래스로 제한하는 것뿐만 아니라, 특정 인터페이스를 구현하는 클래스로 타입을 제한하는 방법도 필요했습니다.

즉, extends와 implements를 모두 지칭하기 위한 키워드가 필요했습니다.

하지만 새로운 키워드를 함부로 만든다면 이미 구현되어 있는 코드가 작동하지 않을 수도 있기 때문에 extends로 사용하자는 결론이 났다고 합니다.

 

Comparator <T> 인터페이스 이용

public static <T> void sort​(List<T> list, Comparator<? super T> c)

Comparator 인터페이스를 구현하여 compare 메서드를 구현한 뒤 Collections.sort(myList, new myClass()); 를 통해 정렬할 수 있습니다.

 

 

 

Java HashMap의 동작 과정

list 형태를 사용하지 않고 hash를 사용하면 삽입, 검색에 대해 시간 복잡도 O(1)이라는 이점을 가집니다.

Boolean과 같이 서로 구별되는 객체의 종류가 적거나 Integer, Long, Double과 같은 Number 객체는 값 자체를 해시값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있지만 String이나 POJO에 대해서는 사실상 불가능합니다.

hashCode() 메서드의 반환 값은 int형이기 때문에 32비트 정수 자료형으로는 완전한 자료 해시 함수를 만들 수 없습니다.

논리적으로 생성 가능한 객체의 수가 2^32보다 많을 수 있으며 O(1)을 보장하기 위해 2^32인 배열의 모든 HashMap을 가지고 있어야 하기 때문입니다.

따라서 메모리를 절약하기 위해 실제 해시 함수의 표현 정수 범위보다 작은 M개의 원소가 있는 배열을 사용합니다.

int index = X.hashCode() % M;

위의 방식을 사용하면 서로 다른 해시 코드를 가지는 서로 다른 객체가 1/M의 확률로 같은 해시 버킷을 사용하게 됩니다. 

해시 충돌을 해결하기 위해서는 대표적으로 2가지가 존재합니다.

1. Open Addressing

2. Separate Chaining

https://d2.naver.com/helloworld/831311

Open Addressing

데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 다른 해시 버킷에 해당 데이터를 삽입하는 방식

 

 

Seperate Chaining

데이터를 삽입하려는 해시 버킷이 이미 사용 중인 경우 연결 리스트를 통해 해당 데이터를 삽입하는 방식

 

Java HashMap에서 사용하는 방식은 Seperate Chaining 방식이다.

Open Addressing은 키를 삭제할 때 DEL으로 표시하는 방법을 사용할 수 있는데 HashMap에는 삽입, 삭제가 빈번하게 일어나므로 모든 슬롯이 DEL으로 표시된다면 매우 비효율적이게 변합니다.

또한 Open Addressing은 load factor(전체 해시 크기에서 사용 중인 비율)이 증가할수록 삽입하기 위해 필요한 탐사 횟수가 비약적으로 증가합니다. 테이블이 꽉 차게 되면 삽입이 불가능할 수도 있습니다.

 

그에 비해 separate Chaining 방식은 연결 리스트를 사용하기 때문에 load factor가 증가하더라도 삽입하기 위한 필요한 탐사 횟수가 선형적으로 증가합니다.

또한 삭제 시에도 단순히 연결 리스트의 요소를 지우기 때문에 효율적입니다.

 

하지만 계속 해시 충돌이 일어나게 되면 O(N)의 시작 복잡도를 가지게 됩니다.

따라서 Java8 HashMap에는 하나의 해시 버킷에 특정 수의 key-value 쌍이 모이면 링크 리스트를 트리로 변경합니다.

8 이상이면 트리를 쓰고 6 이하이면 트리를 사용하지 않습니다.

2의 차이를 둔 이유는 만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 연결 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있습니다.

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

 

해시 버킷의 동적 확정

해시 버킷의 개수가 적다면 메모리 사용량을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생합니다.

따라서 HashMap은 key-value 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 2배로 늘립니다.

여기서의 일정 개수란 현재 데이터 개수 > 'load factor * 현재의 해시 버킷 개수'를 초과하면 버킷의 크기가 2배로 확장됩니다.

초기 용량은 16이며, load factor의 기본값은 0.75입니다.

 

하지만 버킷의 개수가 증가할 때마다 새로운 Separate Chaining을 구성해야 하므로 초기에 적절한 해시 버킷을 개수를 지정하는 것이 효율적입니다.

public HashSet(int initialCapacity, float loadFactor) {
	map = new HashMap<>(initialCapacity, loadFactor);
}

/* the specified initial capacity and default load factor (0.75) */

 

 

Hashtable vs HashMap

Hashtable은 Vector와 같은 레거시 클래스입니다.

HashMap과 Hashtable은 key-value 형태이고 key는 중복될 수 없고, value는 중복될 수 있는 Map의 특성을 가지고 있습니다.

HashMap은 null을 허용한다는 점과 동기화되지 않는다는 점을 제외하면 Hashtable과 거의 동일합니다

 

Hashtable은 null을 허용하지 않고 synchronized 되어있습니다.

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

 

Hashtable vs ConcurrentHashMap

둘 다 thread-safe 하며 key와 value에 null을 허용하지 않는 공통점이 존재하지만 성능이 ConcurrentHashMap이 우수하다. ( HashMap은 key, value에 null 허용)

 

Hashtable은 vector 클래스처럼 메서드에 synchronized가 걸려있고 ConcurrentHashMap은 구현부에 synchonized를 적용하여 성능을 향상했습니다.

 

 

HashMap vs LinkedHashMap

Map은 원래 데이터의 순서가 보장되지 않습니다.

따라서 HashMap은 순서가 보장되지 않지만, LinkedHashMap은 순서가 보장됩니다.

 

 

 

 

Collection의 직렬화

Serializable 인터페이스를 구현하는 컬렉션은 직렬화가 가능하다고 보장할 수 있을까요?

보장할 수 없음 Collection <E>의 E가 직렬화 불가능할 수 있음

https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/Collection.html

Collection (Java SE 16 & JDK 16)

 

 

Map interface가 Collection을 상속받지 않는 이유는?

매핑은 컬랙션이 아니고 컬랙션은 매핑이 아니라고 느껴 의도적으로 설계되었습니다.

만약 Map 이 Colection이라면 요소는 무엇일까요?

합리적인 대답은 key-value의 쌍이지만 이는 매우 제한적인 맵 추상화를 제공합니다.

collection.remove(Obejct o)를 사용해야 할 때 Map이 Collection을 상속받았다면 key-value 형태로 값을 넣어줘야 하지만 실제로 map.remove()의 인자는 key값으로 받습니다. 

이처럼 Map interface는 요소의 모호함과 구조상 맞지 않는 부분 때문에 Collection 인터페이스를 상속받지 않습니다.

 

Iterator가 Enumeration을 상속받지 않는 이유는?

Enumeration이름을 매우 길기 때문에 새로운 프레임워크를 생성한다는 점을 감안할 때 이름을 개선할 수 있는 기회를 사용하지 않는 것이 어리석다고 생각하여 상속받지 않습니다.

 

 

사용자 지정 컬렉션 구현(Custom Collection Implementations)

만약 기존의 Collection들보다 더 나은 성능이나 특별한 목적 더 편하게 사용하기 위해서 사용자 지정 Collection을 구현할 수 있습니다.

인터페이스를 구현하는데 필요한 노력을 최소화시키기 위해 AbstractMap 또는 AbstractList와 같은 클래스를 제공합니다.

https://docs.oracle.com/javase/tutorial/collections/custom-implementations/index.html

 

Immutable Collection이란?

아이템 추가, 수정, 삭제가 불가능한 Collection ( read-only)

신규 아이템을 추가하거나 기존 아이템을 수정 제거하려고 하면 java.lang.UnsupportedOperationException이 발생합니다.

 

Immutable Collection 만들기

List<String> fruits = new ArrayList<>();

fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
fruits = Collections.unmodifiableList(fruits);

fruits.add("Lemon"); // UnsupportedOperationException

 

핵심 collection interface들에서 선택적 연산(optional operation)에서 직접 불변성을 지원하지 않는 이유는?

불변 컬렉션을 수정하려고 하면 런타임 시 UnsupportedOperationException이 유발되는데 컴파일 단계에서 에러를 처리하지 않는 이유

 

그렇게 되면 인터페이스 계층이 폭발적으로 증가합니다.

여러 가지의 interface와 iteratior가 추가적으로 필요합니다.

따라서는 런타임 예외를 던질 수 있는 아주 작은 코어 인터페이스 세트를 제공함으로써 전체 문제를 회피하는 것이 건전한 엔지니어링 타협이라고 합니다.

 

UnsupportedOperationException이 발생했을 때를 대비해 try- catch를 사용하도록 하지 않는 것도 프로그램이 이러한 예외를 잡는 것이 원래의 의도와는 달랐기 때문에 unchecked Exception으로 설정했습니다.

 

 

Immutable Collection, Immutable Object를 사용하는 이유?

 

1. Thread-safe 하여 병렬 프로그래밍에 유용하며, 동기화를 고려하지 않아도 됩니다.

멀티스레드 환경에서 동기화 문제가 발생하는 이유는 공유 자원에 동시에 쓰기 때문입니다.

 

2. 실패 원자적인  메서드를 만들 수 있다.

가변 객체를 통해 어떤 작업을 하는 도중 예외에 발생하면 해당 객체가 불안정한 상태에 빠질 수 있습니다.

하지만 불변 객체는 어떠한 예외가 발생하더라도 메서드 호출 전의 상태를 유지합니다.

 

3. Cache로 활용하기 좋습니다.

한번 데이터가 저장된 이후에 값이 변경되는 것을 고려하지 않아도 되기 때문에 캐시로 사용하기 좋습니다.

 

4. 부수 효과를 피해 오류 가능성을 최소화합니다.

부수 효과란 변수의 값이 변경되거나, 필드 값이 설정되는 등의 변화가 발생하는 효과를 의미합니다.

하지만 불변 객체는 값이 변하지 않기 때문에 안전하게 다시 사용할 수 있습니다.

 

5. 협업 시 다른 사람이 작성한 함수를 예측 가능하고 안전하게 사용할 수 있습니다.

협업 시 불변성이 보장된 함수라면 다른 사람이 작성한 함수에 대해 코드 변경에 대한 불안 없이 이용할 수 있습니다.

 

6. GC의 성능을 높일 수 있습니다.

GC가 스캔해야 하는 객체의 수가 줄기 때문에 자연스럽게 GC의 수행 시간이 빨라집니다.

 

final 키워드를 사용하면 되는 것이 아닌가요?

final은 정확히 불변이 아니라 재할당만 금지합니다.

final Map<String, Boolean> collection = new HashMap<>();

collection.put("1",true); // OK
collection = new HashMap<>(); // compile Error

위의 코드에는 final을 사용했지만 값이 추가됩니다.

하지만 collection = new HashMap <>(); 을 재사용한다면 final로 할당된 코드를 재할당 할 수 없기 때문에 컴파일 에러가 발생합니다.

 

 

---

출처

https://docs.oracle.com/en/java/javase/16/docs/api/java.base/java/util/Collection.html(JDK16 Collection API)

https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html(JDK8 Collection 공식문서)

https://www.daleseo.com/java9-immutable-collections/(불변 컬렉션 생성)

https://jojoldu.tistory.com/412(일급컬렉션)

https://mangkyu.tistory.com/131(불변 객체)

https://www.youtube.com/watch?v=SLifMOhW1VA(제이온의JCF : 우아한Tech 10분 테코톡)

https://velog.io/@hong-brother/JAVACollection-JCF(Collection)
https://gona.tistory.com/62(JCF)

https://hamait.tistory.com/229(자바언어에서 동기화의 어려움)

https://202psj.tistory.com/1614(자바 동기화의 어려움 관련 모음)

https://steady-coding.tistory.com/556(synchronized 키워드란?)

https://mangkyu.tistory.com/101(equals와 hashCode 함수)

https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier(해시코드에 31을 사용하는이유)

https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-vs-ArrayList(Array vs ArrayList)

https://yeolco.tistory.com/94(ArrayList vs Vector)

https://d2.naver.com/helloworld/831311(Java HashMap은 어떻게 동작하는가?)

https://github.com/wjdrbs96/Today-I-Learn/blob/master/Java/Collection/Map/HashMap%EC%9D%B4%EB%9E%80%3F.md#%ED%95%B4%EC%8B%9C-%EC%B6%A9%EB%8F%8Ccollisions(HashMap이란?)

https://devlog-wjdrbs96.tistory.com/253(HashMap vs Hashtable 차이는 무엇일까?)

https://wjheo.tistory.com/entry/Java-%EC%A0%95%EB%A0%AC%EB%B0%A9%EB%B2%95-Collectionssort(Java 정렬방법 Collections.sort()

https://ict-nroo.tistory.com/76(Hashing 개요)