[컬렉션 프레임워크] 해시(Hash)

 

자바 자료구조- 해시(Hash) : 빠른 데이터 조회와 중복 방지 가능!

 

1. 리스트 vs 셋(Set)

구조	순서	중복	특징
List	O	O	인덱스 기반, 순서 유지
Set	X	X	중복 제거, 빠른 탐색

 

List<String> cart = List.of("apple", "apple", "banana");
Set<String> ids = Set.of("user1", "user2"); // "user1" 중복 추가 불가

---

2. Set 구현 코드 예시

☑︎ O(n)의 선형 탐색 -> 중복은 잘 막지만 느리다.

// 내부 배열: 고정 크기 10
private int[] elementData = new int[10];
private int size = 0;

// 중복 없이 값 추가
public boolean add(int value) {
    if (contains(value)) return false; // 이미 존재하면 추가 X
    elementData[size++] = value;       // 배열에 저장 후 size 증가
    return true;
}

// 특정 값이 있는지 확인
public boolean contains(int value) {
    for (int data : elementData) {
        if (data == value) return true; // 찾으면 true 반환
    }
    return false;
}

---

3. 해시(Hash)의 등장

☑︎ 선형 탐색 : O(n)의 

int[] data = {1, 2, 5, 8};
int target = 8;
for (int i : data) {
    if (i == target) return true;
}

 

☑︎ 인덱스 기반 접근 : O(1)

Integer[] hashArray = new Integer[10];
hashArray[8] = 8; // 값이 곧 인덱스 역할을 함
System.out.println(hashArray[8]); // 결과: 8

 

---

4. But,,,, 메모리 낭비 심함...

☑︎ 예) 값의 범위를 늘려보면?

 - 값은 몇개 없는데 메모리 공간이 너무 커서 낭비가 심하게 발생하게 됨

// 실제로는 몇 개만 쓰는데 배열은 100칸
Integer[] inputArray = new Integer[100];
inputArray[99] = 99;

 

---

5. 해시 인덱스(Hash Index) 발견

✅ 나머지 연산을 활용하자!

// 범위가 넚은 값을 제한된 배열 공간에 효율적으로 매핑이 가능하다
int hashIndex = value % 10;  // 항상 0~9 사이 값만 나옴

 

☑️ 저장

int index = value % 10;
inputArray[index] = value; // 해시 인덱스를 배열 인덱스로 사용

 

☑️ 조회

int result = inputArray[searchValue % 10]; // 해시 인덱스로 바로 접근

---

6. 해시 충돌의 문제

// 99 % 10 = 9  
// 9 % 10 = 9  
// → 둘 다 index 9에 저장됨

 

해결방법 : 배열 안에 리스트(버킷) 넣기

// 크기 10짜리 LinkedList 배열
LinkedList<Integer>[] buckets = new LinkedList[10];

for (int i = 0; i < 10; i++) {
    buckets[i] = new LinkedList<>(); // 각 인덱스에 리스트 초기화
}

void add(LinkedList<Integer>[] buckets, int value) {
    int index = value % 10;
    if (!buckets[index].contains(value)) {
        buckets[index].add(value);
    }
}

---

7. 충돌까지 고려한 HashSet 구현 예제

static final int CAPACITY = 10;

public static void main(String[] args) {
    // 해시 버킷 초기화
    LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
    for (int i = 0; i < CAPACITY; i++) {
        buckets[i] = new LinkedList<>();
    }

    // 값 추가 (충돌 고려)
    add(buckets, 1);
    add(buckets, 99); // 99 % 10 = 9 → 충돌 발생

    // 값 검색
    int searchValue = 99;
    boolean contains = contains(buckets, searchValue);
    System.out.println(searchValue + " 존재 여부: " + contains);
}

 

☑️ 값 추가 메서드

private static void add(LinkedList<Integer>[] buckets, int value) {
    int index = value % CAPACITY;          // 해시 인덱스 계산
    LinkedList<Integer> bucket = buckets[index]; // 해당 인덱스의 리스트 가져오기

    if (!bucket.contains(value)) {         // 중복 방지
        bucket.add(value);                 // 리스트에 값 추가
    }
}

 

☑️ 값 검색 메서드

private static boolean contains(LinkedList<Integer>[] buckets, int value) {
    int index = value % CAPACITY;              // 해시 인덱스 계산
    LinkedList<Integer> bucket = buckets[index]; // 리스트 가져오기
    return bucket.contains(value);             // 리스트 내부 탐색
}

---

8.Hash 성능과 충돌 확률

배열 크기(CAPACITY)	충돌 발생 가능성
작을 수록	높음
클수록	낮음

 ☑︎ 충돌 줄이기 : 적절한 배열 크기

 ☑︎ 일반적으로 : 사용량의 75% 이하가 되도록 설정

 ☑︎ 출동 시 연결리스트 순회로 인해 최악의 경우 O(n) 발생될 수 있음

---

9. 정리

항목	해시 인덱스 방식
저장 속도	평균 O(1), 최악 O(n)
조회 속도	형균 O(1), 최악 O(n)
중복 허용 여부	X (Set 구조 기준)
공간 활용 효율성	나머지 연상 + 버킷으로 최적화 가능
충돌 해결	버킷(리스트)에 저장, contains()로 확인

 

 

<참고> - 김영한의 실전 자바 중급2편 강의 섹션 7. 컬렉션 프레임워크 해시(Hash)