[F-Lab 모각코 챌린지 16일차] Set 인터페이스, HashSet 클래스 / LinkedList 클래스

TIL

1. Set 인터페이스
2. HashSet 클래스
3. LinkedList 클래스

 

---

 

Set 인터페이스

• 데이터의 중복을 허용하지 않고 순서를 유지하지 않는 데이터의 집합 리스트
• 순서 자체가 없으므로 index를 이용한 메소드도 존재하지 않는다.
• 중복 저장이 불가하므로 심지어 null 값도 하나만 저장할 수 있다.

 

 

 

Set이 필요한 이유

순서 상관 없이 어떤 데이터가 존재하는지를 확인하기 위한 용도로 많이 사용된다. 중복을 방지하고 원하는 값이 포함되어 있는지를 확인하다.

 

예를 들어, 어떤 서버에 1분간 사용자들이 요청한 로그가 쌓여있다. 이 서버에 요청한 IP를 기준으로 사용자 수가 얼마나 되는지 확인해보고자 한다. 1분간 이 서버에 요청하는 중복 사용자 수는 매우 많을 것이다. 만약 List로 확인하려고 하면 indexOf() 메소드를 사용해서 해당 객체가 있는지 확인 후, add() 메소드로 추가하는 작업을 반복해야만 한다.

그러나 Set을 구현한 클래스를 사용하면 그냥 데이터를 추가만 하면 된다. 알아서 중복 데이터를 걸러주니까.

 

Set은 데이터의 중복을 허용하지 않으므로 데이터가 같은지를 확인하는 작업이 핵심이다. equals()와 hashCode()를 구현하는 부분도 매우 중요하다. Set은 데이터의 순서를 보장하지 않기 때문에 get(int index)나 indexOf(Object o) 처럼 index를 사용한 메소드들이 존재하지 않는다.

 

 

 

HashSet

 

 

 

HashSet 생성자

// 1. 16개의 저장 공간과 0.75f의 로드팩터를 갖는 객체를 생성한다.
public HashSet() {
    map = new HashMap<>();
}

// 2. 매개변수로 받은 컬렉션 객체의 데이터를 HashSet에 담는다.
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

// 3. 매개변수로 받은 개수만큼의 데이터 저장공간, 0.75f 로드팩터를 갖는 객체를 생성한다.
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

// 4. 매개변수로 받은 개수만큼의 데이터 저장공간, 로드팩터를 갖는 객체를 생성한다.
public HashSet(int initialCapacity, float loadFactor) {
     map = new HashMap<>(initialCapacity, loadFactor);
}

생성자들을 보면 HashSet 생성자는 내부적으로 HashMap 객체를 생성한다. HashMap의 객체는 HashSet에 입력한 모든 요소를 저장한다. 여기서 문제가 발생한다. HashMap은 항상 key와 value 쌍을 기반으로 데이터를 저장한다. 그러나 HashSet에서는 값만 제공한다. 두 클래스의 자료구조가 달리 설계 되어있는데 어떻게 HashSet을 HashMap으로 매핑하는 것일까? HashSet의 add(E e) 메소드를 살펴보자.

 

 

 

ℹ 그런데 여기서 자꾸 나오는 로드팩터란 무엇일까?

로드팩터는 (데이터의 개수 / 저장공간)을 의미한다. 만약 데이터의 개수가 증가해서 로드팩터보다 커지면 그 때 저장공간의 크기는 증가되고 해시 재정리 작업(rehash)을 들어간다. 해시 재정리 작업에 들어가면 내부에 갖고 있는 자료구조를 다시 생성하는 단계를 거쳐야 하므로 성능에 영향을 끼친다.

 

로드팩터 값이 클수록 저장공간은 넉넉해지지만 데이터를 찾는 시간은 증가한다. 따라서 초기 데이터 저장공간 크기와 로드팩터를 데이터의 개수를 고려하여 산정하는 것이 좋다. 왜냐하면 초기 데이터 저장공간 크기가 (데이터의 개수 / 로드팩터) 보다 클 경우에 데이터를 쉽게 찾기 위한 해시 재정리 작업이 발생하지 않기 때문이다.

 

따라서, 대량의 데이터를 Set에 담아 처리할 때, 초기 데이터 저장공간 크기와 로드팩터 값을 조절해가며 가장 적당한 크기를 찾아야만 한다.

 

 

 

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

다음은 HashSet에 구현 되어 있는 add(E e) 메소드이다. 파라미터로 넘어온 이 요소는 HashMap 객체의 key로 저장되고 value로는 PRESENT라는 상수를 저장한다. 여기서 PRESENT는 Object 클래스의 static final object이다.

 

 

 

 

add(E e) 메소드는 HashMap의 put(e, PRESNT) 메소드를 호출하며 이 put() 메소드는 파라미터로 넘어온 요소 e가 HashMap에 존재하지 않으면 null을 반환한다. 요소 e가 있으면 그 요소를 반환한다.

 

 

 

Queue가 필요한 이유

웹 서버에 100명의 사용자가 요청을 했다. 만약 LIFO(Last In First Out)로 처리해서 사용자에게 응답을 준다면, 가장 먼저 줄을 서있던 사용자가 마지막에 응답을 받게 된다. 이렇게 되면 이 사용자는 해당 서비스로부터 탈주하게 될 것이다. 이런 경우엔 사용자들의 요청을 들어온 순서대로 처리해야한다. 이럴 때, 큐를 사용한다.

 

LinkedList 클래스가 구현한 인터페이스 중에는 Java6에 추가 된 Dequeue(Double Ended Queue)라는 것이 있다. Dequeue는 Queue 인터페이스를 확장했기 때문에 Queue 기능을 전부 포함한다. 대신, 맨 앞에 값을 넣거나 빼는 작업 / 맨 뒤에 값을 넣거나 빼는 작업이 쉽다.

 

 

 

LinkedList

• 노드(객체)를 연결하여 리스트처럼 만든 컬렉션이다. (배열 아님)
• 데이터의 중간 삽입, 삭제가 빈번할 경우 빠른 성능을 보장한다.
• 하지만 임의의 요소에 대한 접근 성능은 좋지 않다.
• 자바의 LinkedList는 Doubly LinkedList(양방향 포인터 구조)로 이루어져 있다.

 

LinkedList는 List도 되고 Queue도 된다. 두 인터페이스의 기능을 모두 구현한 특이한 클래스이다. Queue 인터페이스를 구현하므로 맨 앞과 맨 끝의 데이터도 쉽게 처리할 수 있다.

 

LinkedList는 일반적인 배열 타입의 클래스와는 다르게 객체를 생성할 때, 크기를 정하지 않는다. 왜냐하면 각 데이터들의 앞 뒤로 연결되는 구조이기 때문에 미리 공간을 만들어 놓을 필요가 없는 것이다.

 

LinkedList는 ArrayList와 마찬가지로 중복 요소를 포함할 수 있고 삽입 순서를 유지한다. LinkedList 각각의 모든 요소는 next 노드의 주소를 저장한다. Head는 LinkedList의 첫번째 노드이고 Tail 마지막 노드이다. Head에는 previous 노드의 주소가 없고 Tail에는 next 노드의 주소가 없다.

또한, LinkedList 클래스는 동기화되지 않는다.

 

 

 

LinkedList 데이터 추가/삭제

public static void main(String[] args) {
    LinkedList<String> firstList = new LinkedList<String>();

    firstList.add("Java"); // 1)
    firstList.add("Goal"); // 2)
    firstList.add("Website"); // 3)

    firstList.remove("Goal"); // 4)
}

 

1)

 

 

2)

 

 

3)

 

 

4)

 

 

 

LinkedList가 필요한 이유

Array와 ArrayList는 연속적인 메모리에 데이터를 저장할 수 있지만 LinkedList의 데이터 구조는 이와 다르다.

배열은 그 크기가 고정되어 있어 배열 생성 시, 크기를 결정해야 한다. 그러나 ArrayList는 조작 중에 배열 크기를 동적으로 늘리거나 줄일 수 있다. LinkedList 역시 동적으로 크기를 조절 할 수 있지만 ArrayList처럼 공간을 낭비하지 않는다.

ArrayList는 내부적으로 ArrayList 타입의 새 객체를 생성하고 이전 객체에 있던 모든 데이터를 복사한다.

 

Array와 ArrayList는 인접한 메모리 위치에 각 데이터를 저장한다. 따라서 특정 index에 데이터를 추가하거나 제거하면 모든 요소가 이동하며 이는 성능에 영향을 미친다. LinkedList는 데이터를 추가하거나 삭제하는 작업을 수행하는데 ArrayList보다 빠르다. LinkedList에서 요소를 추가하거나 제거하면 JVM은 내부적으로 링크를 만들거나 끊기 때문이다.

 

 

 

📚 참고
자바의 신 23장
HashSet in java
Java LinkedList class
Java Collections Framework 종류 💯 총정리