java Collection, Hash 연관 정리

1. java Collection framework 개념

Collection 인터페이스, 구현 클래스, 유틸리티 클래스, 정렬, iterator, 동기화, stream, spliterator, comparator/comparable 등을 포함하고 있음.

데이터를 효율적으로 저장/관리/검색/순회/정렬할 수 있게 해주는 인터페이스 + 구현체 + 유틸리티 클래스의 생태계 전체

 

2. Collection 개념

데이터의 집합을 다루기 위한 인터페이스 계층 구조, 여러 객체를 효율적으로 추가/삭제/검색 할 수 있도록 도와주는 인터페이스

List, Set, Queue 같은 "요소들의 집합"을 다루는 인터페이스 계층 구조

 

3. Collection 종류

Collection	List, Set, Queue의 부모 인터페이스
List	순서가 있는 데이터 집합 (중복 허용)
Set	순서가 없고 중복을 허용하지 않음
Queue	FIFO 구조 (먼저 넣은 게 먼저 나옴)
Map	키-값 쌍으로 저장 (Collection은 아님)

* 일반적으로 Collection을 학습할 때 Map을 함께 학습함.

 

4. Collection 조합

List + Set	중복 제거 후 순서 유지
List + Map	순서 유지하면서 빠른 조회
Set + Map	조건 필터링된 조회
List<Map<>>	복잡한 데이터 구조 (DB, JSON 등)
Queue + Set	BFS, 이벤트 중복 방지

 

5. Hash 개념

특정 값을 고정된 크기의 정수값(hash code)으로 바꾸는 기능.

같은 입력 값이면 항상 동일한 해시값을 가지기 때문에 빠른 검색과 비교에 용이함.

빠른검색, 빠른 삽입/삭제, 키 기반 접근
HashMap, HashSet, ConcurrentHashMap, hashCode()

 

* 간혹 Hash를 정수값(hash code)이 아닌, 주소값이라고 표현하는 경우가 있는데 이는 틀린 표현.

특정 환경에서는 메모리 기반의 주소 값을 활용하는 사례가 있지만, java에서 hash는 항상 32bit 고정 크기 정수임

ex) "hash".hashCode() -> 3198781

s[0]*31ⁿ⁻¹ + s[1]*31ⁿ⁻² + ... + s[n-1]

 

6. Hash Collision 개념

동일한 hash code를 갖는 경우가 있음, 32bit 의 고정 정수(약 43억 개)의 경우의 수 보다 입력의 가능성의 수가 훨씬 많기 때문에 같은 해시코드를 가질 가능성이 있음.

ex) "Aa".hashCode() == "BB".hashCode() // 두 문자열의 hash code는 같다.

 

장애 발현이 흔하지 않은 이유?

java에서 내부적으로 충돌을 처리해주는 구조로 기능을 제공하고 있음.

같은 hash code를 가진 값을 비교하면, hash code 이후에 equals를 활용하고 있음.

(= hashCode() 또는 equals()를 잘못 구현하는 경우 장애로 이어질 수 있음)

 

1) 체이닝(LinkedList) 활용

해시 충돌 발생 시 같은 버킷에 들어온 값들을 연결해서 저장하는 방식.

HashSet, HashMap의 경우 같은 hash code가 저장된 경우, 동일한 인덱스에 여러 값들을 저장해두고, equals를 활용하여 정확한 값을 찾아내고 있다.

 

2) 트리(Red-Black Tree) 활용 Java 8이상

체이닝만 사용하는 경우 충돌이 잦을 때, 성능이 O(n)으로 낮아짐

동일 버킷에 8개 이상 발생하는 경우, 해당 버킷을 Red-Black Tree로 전환해서 탐색 성능을 O(log n)으로 향상 시킴

 

7. @Override hashCode(), equals() 

ORM( JPA ) 사용 시 혹은 HashMap, HashSet등 hash 인터페이스의 key로 dto 사용 시 필요함.

Class User {
  String name;
  
  User(String name) {
    this.name = name;
  }
}

User A = new User("A");
Set<User> userSet = new HashSet<>();
userSet.add(A);

userSet.contains(new User("A")); // false

 

* 직접 @Override 구현

public class User {
    private String name;
    private int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User other = (User) o;
        return this.age == other.age && Objects.equals(this.name, other.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

User A = new User("A");
Set<User> userSet = new HashSet<>();
userSet.add(A);

userSet.contains(new User("A")); // true

 

* Lombok 사용

@EqualsAndHashCode
public class User {
    private String name;
    private int age;
}

@EqualsAndHashCode(of = {"name"}) // 부분 일치로 dto 가 일치하는지 체크할 수 있다
public class User {
    private String name;
    private int age;
}

 

* Record 사용(java 14이상, 불변 데이터의 경우 활용)

public record User(String name, int age) {
    // equals()와 hashCode()는 자동 생성됨
}

 

8. Comparable/ Comparator

구분	Comparable	Comparator
어디에 정의?	객체 클래스 내부	클래스 외부 또는 람다식
인터페이스명	Comparable<T>	Comparator<T>
메서드명	int compareTo(T o)	int compare(T o1, T o2)
기본 정렬?	가능	기본은 아님, 원하는 만큼 만들 수 있음
사용 예	Collections.sort(list)	list.sort(comparator), TreeSet<>(comparator)

* 간단하게 dto 내부 한 요소 등으로 정렬하는 경우 = Comparable, 여러 요소를 기준으로 정렬한다면 Comparator 활용