🌱 해시(hash)란?

임의의 데이터를 고정된 길이의 값(숫자나 문자열)으로 바꿔주는 함수나 방법
👉 긴 데이터를 "짧고 고유한 번호"로 변환하는 것

예를 들어:

• "사과" → 123
• "바나나" → 456
• "포도" → 789

이렇게 바꿔주는 게 해시 함수이다.

🏠 집 주소 비유

• 우리가 집을 찾을 때 "이름"으로 찾으면 힘들다 (동네에 같은 이름 많음)
• 대신 "주소(예: 서울시 XX구 OO로 12)"를 쓰면 바로 찾아간다
  ➡️ 해시는 데이터를 찾을 때 쓰는 주소 같은 역할을 해준다.

---

⚡ 해시의 특징

1. 빠른 검색 (O(1))

• 데이터를 찾을 때, 전체를 뒤지지 않고 바로 위치(주소)로 점프 가능

2. 고정된 길이

• "사과", "바나나", "엄청 긴 글" 다 넣어도 해시 값은 보통 일정한 길이

3. 같은 입력 → 같은 해시

• "사과" 를 넣으면 항상 123 이 나와야 함

4. 충돌 가능

• "사과" → 123, "배" → 123 같은 경우 발생할 수 있음
  (이를 "해시 충돌"이라고 함)

---

📦 어디서 쓰일까?

• HashMap, HashSet 같은 자료구조
• 비밀번호 저장 (비밀번호를 해시로 변환해서 DB에 저장)
• 파일 무결성 검사 (파일 해시값 비교해서 바뀌었는지 확인)
• 블록체인 (트랜잭션 해시로 데이터 고유성 보장)

---

✅ HashSet 이란?

Set 인터페이스를 구현한 컬렉션 클래스

✔️ 순서, 중복이 없다.

• 집합 개념을 구현함 → 중복을 허용하지 않고, 순서도 보장하지 않는다.
• 내부적으로는 HashMap을 사용해서 만들어짐
• 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠르다.

• ❗️ 순서를 유지하려면, LinkedHashSet 클래스를 사용하면 된다.

---

📌 특징

1. 중복 ❌

• 같은 값이 들어오면 저장하지 않는다.
• 예: [1, 2, 3, 2] → 저장하면 [1, 2, 3]

2. 순서 ❌

• 넣은 순서를 보장하지 않는다. (ArrayList랑 다름)
• 예: set.add(5); set.add(1); set.add(3); → 결과: [1, 3, 5] 같은 식으로 순서가 뒤죽박죽.

3. 빠른 검색 ⏱ (O(1))

• 해시 기반이라서 원소를 찾는 속도가 빠르다.

---

📌 HashSet을 쓰는 경우

1. 중복을 허용하지 않고, 유일한 값만 저장하고 싶을 때

• 예: 회원가입 시 아이디 중복 방지
• 예: 로또 번호 추첨 (번호 중복 ❌)

HashSet<Integer> lotto = new HashSet<>();
while (lotto.size() < 6) {
    int num = (int)(Math.random() * 45) + 1;
    lotto.add(num); // 중복 자동 제거
}
System.out.println(lotto);

2. 순서가 중요하지 않을 때

• ArrayList 는 넣은 순서를 지켜야 할 때 사용하지만,HashSet 은 순서 상관없이 "있다/없다"만 중요할 때 사용한다.
• 예: 방문한 사이트 기록, 태그 모음 등.

3. 빠른 검색이 필요할 때

• ArrayList 는 특정 값 검색 시 O(n) (하나씩 다 확인)
• HashSet 은 해시 기반이라 O(1) (거의 즉시 찾음)
• 예: 블랙리스트 IP 차단

HashSet<String> blacklist = new HashSet<>();
blacklist.add("192.168.0.10");
blacklist.add("10.0.0.5");

if (blacklist.contains("192.168.0.10")) {
    System.out.println("차단된 IP!");
}

---

📌 기본 사용법

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();

        // 값 추가
        set.add("Apple");
        set.add("Banana");
        set.add("Orange");
        set.add("Apple"); // 중복 ❌

        System.out.println(set); // [Apple, Banana, Orange] (순서 일정하지 않음)

        // 특정 값 포함 여부
        System.out.println(set.contains("Banana")); // true
        System.out.println(set.contains("Grape"));  // false

        // 값 제거
        set.remove("Orange");
        System.out.println(set); // [Apple, Banana]

        // 전체 반복
        for (String fruit : set) {
            System.out.println(fruit);
        }
    }
}

---

✏️ HashSet 생성자

• initialCapacity: 배열의 용량
• loadFactor: 언제 용량을 늘릴것인지

✏️ HashSet 메서드

❗️Set은 집합이기 때문에 이러한 기능이 가능하다.

• addAll: 합집합
• removeAll: 교집합
• retainAll: 차집합

1️⃣ add(value) 동작 방식

예: set.add("바나나")

1. "바나나".hashCode() 실행 → 해시값 얻음 (예: 94328)
2. 해시값을 HashMap처럼 배열 인덱스로 변환 → 94328 % 16 = 8
3. 배열 8번 칸에 "바나나" 라는 key를 저장 (value는 DUMMY)
4. 만약 이미 "바나나" 가 있으면? equals() 검사 후 중복이므로 추가 안 함 ✅

• contains: 요소가 있는지 확인

---

📎 HashSet 객체 저장

• 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인해야 한다.
  같은 객체가 없으면 저장하고, 있으면 저장하지 않는다.

• boolean add(Object o) 는 저장할 객체의 equals() 와 hashcode() 를 호출한다.
  equals() 와 hashcode() 가 같이 오버라이딩 되어 있어야 한다.

✏️ 객체 중복 예제

import java.util.*;

public class HashSetObject {
    public static void main(String[] args) {
        HashSet set = new HashSet();
		
        // 같은 String
        set.add("abc");
        set.add("abc");
        
        // 같은 사람
        set.add(new Person("Jennie" , 25) );
        set.add(new Person("Jennie", 25));

        System.out.println(set);

    }
}
class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        setAge(age);
        setName(name);
    }
    @Override
    public String toString() {
        return name + ": " + age;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public int getAge() {
        return age;
    }
}

[abc, Jennie: 25, Jennie: 25]

• HashSet 은 중복을 제거하지만 객체안에서 어떤것이 같은지 아닌지를 모르기 때문에 위 예시처럼 그대로 나온다.
• 이렇듯 이름과 나이가 같으면 같은 사람이라는 것을 객체 안에다 지정해줘야 한다.

✏️ equals()와 hashCode() 오버라이딩

    @Override
    public boolean equals(Object o) {
        if(o == null || !(o instanceof Person)) {
            return false;
        }
        Person other = (Person) o;
        return name.equals(other.getName()) && age == other.getAge();
    }

    @Override
    public int hashCode() {
        // int hash(Object ... values) 가변인자
        return Objects.hash(name, age);
    }

• 이렇게 만들어줘야 HashSet 이 중복을 소거해준다.

✏️ 총정리 결과

import java.util.*;

public class HashSetObject {
    public static void main(String[] args) {
        HashSet set = new HashSet();

        set.add("abc");
        set.add("abc");
        set.add(new Person("Jennie" , 25) );
        set.add(new Person("Jennie", 25));

        System.out.println(set);

    }
}
class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        setAge(age);
        setName(name);
    }
    @Override
    public String toString() {
        return name + ": " + age;
    }

    @Override
    public boolean equals(Object o) {
        if(o == null || !(o instanceof Person)) {
            return false;
        }
        Person other = (Person) o;
        return name.equals(other.getName()) && age == other.getAge();
    }

    @Override
    public int hashCode() {
        // int hash(Object ... values) 가변인자
        return Objects.hash(name, age);
    }

    public void setName(String name) {
        this.name = name;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public int getAge() {
        return age;
    }
}

[abc, Jennie: 25]

---

📌 HashSet vs ArrayList 차이

특징	HashSet	ArrayList
중복	허용 ❌	허용 ⭕
순서	보장 ❌	추가한 순서 보장 ⭕
검색 속도	빠름 (O(1))	느림 (O(n))
사용 목적	"고유한 값만 저장"	"순서대로 여러 개 저장"

---

✅ TreeSet 이란?

Set 인터페이스 구현체 중 하나: "정렬된 집합"

• 내부적으로 Tree 구조(레드-블랙 트리, Red-Black Tree) 를 사용한다.
• 중복 ❌ (Set이니까!)
• 자동 정렬 ⭕ (HashSet과 큰 차이!)

👉 즉, 저장하면서 오름차순 정렬까지 알아서 해주는 Set.

---

📌 특징

1. 정렬된 상태 유지

• Integer , String 같은 Comparable 객체면 기본 정렬(숫자 오름차순, 알파벳 순)
• 직접 정렬 규칙을 만들고 싶으면 Comparator를 넣을 수도 있다.

2. 중복 없음

• HashSet처럼 같은 값은 들어가지 못한다.

3.검색 속도 O(log n)

• 트리 구조라 HashSet보다는 느리지만(해시는 O(1)), 대신 정렬 기능을 제공.

4. 이진 탐색 트리(binary search tree)로 구현

• 범위 검색과 정렬에 유리한 Collection
• 이진 트리는 모든 노드가 최대 2개의 하위노드를 갖는다.
• 각 요소(node)가 나무(tree)형태로 연결(LinkedList 변형)

class TreeNode {
	TreeNode left; // 왼쪽 자식노드
    Object elelment; // 저장할 객체
    TreeNode right; // 오른쪽 자식노드
}

---

📎 이진 탐색 트리(Binary Search Tree, BST)

• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
• 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

---

📌 TreeSet의 데이터 저장과정

✔️ boolean add(Object o)

• 루트부터 트리를 따라 내려가며 값을 비교한다.
• 작으면 왼쪽, 크면 오른쪽에 저장한다.

HashSet은 equals(), hashCode() 로 비교
TreeSet은 compare() 를 호출해서 비교

---

📌 TreeSet을 쓰는 경우

1. 데이터를 자동 정렬된 상태로 유지하고 싶을 때

• 별도로 Collections.sort() 안 해도 됨.
• 예: 학생 점수 저장 → 항상 낮은 점수 → 높은 점수 순서 유지.

TreeSet<Integer> scores = new TreeSet<>();
scores.add(95);
scores.add(70);
scores.add(85);
System.out.println(scores); // [70, 85, 95]

2. 중복을 허용하지 않으면서 정렬도 필요한 경우

• HashSet은 중복만 막고, 순서는 제멋대로.
• TreeSet은 중복 ❌ + 순서 ⭕.
• 예: 로또 번호 추첨 + 오름차순 정렬

TreeSet<Integer> lotto = new TreeSet<>();
while (lotto.size() < 6) {
    lotto.add((int)(Math.random() * 45) + 1);
}
System.out.println(lotto); // 자동으로 오름차순

3. 범위 검색이 필요할 때

• 트리 구조라 구간 탐색이 아주 쉬움.
• 예: 특정 값보다 작은 데이터, 큰 데이터 추출.

TreeSet<Integer> set = new TreeSet<>();
set.add(10); set.add(20); set.add(30); set.add(40);

System.out.println(set.headSet(25)); // [10, 20] (25보다 작은 값들)
System.out.println(set.tailSet(20)); // [20, 30, 40] (20 이상 값들)

4. 커스텀 정렬이 필요할 때

• Comparator 넣으면 원하는 방식으로 정렬 가능.
• 예: 문자열 길이 기준 정렬, 내림차순 정렬 등.

---

📌 기본 사용법

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();

        // 값 추가
        set.add("Apple");
        set.add("Banana");
        set.add("Orange");
        set.add("Apple"); // 중복 ❌

        System.out.println(set); // [Apple, Banana, Orange] (순서 일정하지 않음)

        // 특정 값 포함 여부
        System.out.println(set.contains("Banana")); // true
        System.out.println(set.contains("Grape"));  // false

        // 값 제거
        set.remove("Orange");
        System.out.println(set); // [Apple, Banana]

        // 전체 반복
        for (String fruit : set) {
            System.out.println(fruit);
        }
    }
}

---

✏️ TreeSet 생성자

✏️ TreeSet 메서드

• Object first() : 오름차순으로 제일 작은 값을 나타낸다. (last() : 큰 값)
• Object ceiling(Object o) : 올림 (floor() : 버림)

✏️ TreeSet 예제

✏️ 정렬이 돼서 나오는 TreeSet

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        // 범위 검색, 정렬.
        Set set = new TreeSet();

        for(int i = 0; set.size() < 6; i++) {
            int num = (int)(Math.random() * 45) + 1;
            set.add(num); // set.add(new Integer(num));
            // Integer클래스 안에 정렬기준을 이용했다.
        }
        System.out.println(set);

    }
}

[13, 14, 16, 21, 33, 36]

TreeSet은 정렬이 된 상태로 결과값이 나온다는 것을 알 수 있다.

✏️ 비교기준을 나타내야 한다.

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        Set set = new TreeSet();

        for(int i = 0; set.size() < 6; i++) {
            int num = (int)(Math.random() * 45) + 1;
            set.add(new Test()); 
        }
        System.out.println(set);
    }
}
class Test {} // 비교 기준이 없음

Exception in thread "main" java.lang.ClassCastException: class Test cannot be cast to class java.lang.Comparable (Test is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
	at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
	at java.base/java.util.TreeMap.put(TreeMap.java:536)
	at java.base/java.util.TreeSet.add(TreeSet.java:255)
	at TreeSetEx1.main(TreeSetEx1.java:9)

형변환 예외가 나온다. 그 이유는 비교기준이 없기 때문이다.

✏️ 비교기준 설정 comparator

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        Set set = new TreeSet(new TestComp()); // TreeSet에다 새로운 비교기준을 넣어준다.

        set.add(new TestComp());
        set.add(new TestComp());
        set.add(new TestComp());
        set.add(new TestComp());

        System.out.println(set);
    }
}

class TestComp implements Comparator {
    @Override
    public int compare(Object o1, Object o2) {
        return 1;
    }
}

[TestComp@1cd072a9, TestComp@7c75222b, TestComp@4c203ea1, TestComp@27f674d]

✏️ 비교기준 설정 comparable

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        Set set = new TreeSet();

        set.add(new TestComp());
        set.add(new TestComp());
        set.add(new TestComp());
        set.add(new TestComp());

        System.out.println(set);
    }
}

class TestComp implements Comparable {
    @Override
    public int compareTo(Object o) {
        return 1;
    }
}

[TestComp@4c203ea1, TestComp@27f674d, TestComp@1d251891, TestComp@48140564]

✏️ 범위 검색에 유용한 TreeSet

import java.util.*;

public class TreeSetEx1 {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        int[] score = {80, 95, 50, 35, 45, 65, 10, 100};

        for(int i = 0; i < score.length; i++) {
            set.add(new Integer(score[i]));
        }
        System.out.println("50보다 작은 값: " + set.headSet(50));
        System.out.println("50보다 같거나 큰 값: " + set.tailSet(50));
        System.out.println("40과 80사이의 값: " + set.subSet(40, 80));
    }
}

50보다 작은 값: [10, 35, 45]
50보다 같거나 큰 값: [50, 65, 80, 95, 100]
40과 80사이의 값: [45, 50, 65]

표를 그려보면 이렇다.