[컬렉션 프레임워크] Hash

List vs Set

 

* List

• 순서 보장(인덱스 기반 접근 가능)
• 중복 요소 허용
• 요소를 순차적으로 저장하며, 원하는 위치에 삽입/삭제 가능
• 인덱스를 기준으로 get(index)로 접근할 수 있음
• 대표 구현체
  • ArrayList : 배열 기반, 조회 빠름
  • LinkedList : 노드 기반, 삽입/삭제 빠름

* Set

• 순서를 보장하지 않거나, 구현체에 따라 부분적으로 보장할 수 있음
• 중복된 요소를 허용하지 않음 -> 유일한 값 저장 시 사용
• get(index) 같은 인덱스 기반 접근 불가능
• 내부적으로 해시 구조, 정렬 트리, 링크드 해시 등을 사용해 동작
• 대표 구현체
  • HashSet : 순서x, 해시 기반
  • LinkedHashSet : 삽입 순서 유지
  • TreeSet : 정렬된 상태 유지

 

* List vs Set

항목	List	Set
순서 유지	O(인덱스 존재)	X(HashSet 등), 일부 O
중복 허용	O	X
인덱스 접근	O(get(index) 사용 가능)	X(get 메서드 없음)
탐색 방식	인덱스 기반, 순회	해시 기반(HashSet 기준)
주요 구현체	ArrayList, LinkedList	HashSet, TreeSet, LinkedHashSet

 

* 사용하는 경우

상황	선택
데이터의 순서가 중요한 경우	List
중복된 데이터를 저장해야 하는 경우	List
중복을 제거하고 유일한 값만 저장하고 싶은 경우	Set
빠른 검색 성능이 필요한 경우(key 존재 여부 등)	Set(HashSet)

---

Set을 직접 구현

 

* 직접 구현한 Set

package collection.set;

import java.util.Arrays;

public class MyHashSetV0 {

    private int[] elementData = new int[10];
    private int size = 0;

    // O(n)
    public boolean add(int value) {

        if (contains(value)) {
            return false;
        }

        elementData[size] = value;
        size++;
        return true;
    }

    // O(n)
    public boolean contains(int value) {
        for (int data : elementData) {
            if (data == value) {
                return true;
            }
        }
        return false;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSetV0{" +
                "elementData=" + Arrays.toString(Arrays.copyOf(elementData, size)) +
                ", size=" + size +
                '}';
    }
}

* 문제점

• add() 할 때 중복을 막기 위해 내부적으로 contains() 호출
• contains()는 배열의 처음부터 끝까지 확인 -> O(n)
• 즉, add()의 시간복잡도도 O(n)

*결론 : 해시(Hash) 구조가 필요함

1. 배열 기반 Set의 한계 (= 직접 구현한 Set의 한계)

• 중복 체크를 위해 contains()에서 모든 요소를 순차 탐색 해야함 -> O(n)
• 데이터가 많아질수록 성능 저하 -> 선형 탐색 방식은 비효율적
• 삽입 시에도 중복 검사를 함 -> O(n)

2. 빠른 탐색을 위함

• 중복 검사나 탐색을 O(1) 수준으로 빠르게 하기 위해 Hash 구조를 사용
• Hasing : 데이터를 특정 알고리즘으로 변환하여 고유한 인덱스를 계산
• 계산된 인덱스를 배열의 위치로 사용 -> 탐색/삽입 속도 향상

3. 해시 구조의 장점

• 탐색/삽입 모두 O(1) 수준의 성능(버킷 충돌이 없을 경우)
• 중복 검사도 빠르게 가능
• 대용량 데이터에서도 성능 유지에 강함

---

해시 알고리즘

 

1. 배열 인덱스를 활용한 탐색

• 배열은 인덱스를 통해 O(1)로 빠르게 요소에 접근 가능
• 문제점 : 일반적인 값 기반 탐색 시 전체 순회 -> O(n)
  • 데이터가 많아질수록 탐색 속도가 느려지고 성능 저하
• 해결 : 값 -> 인덱스로 매핑해주는 로직 필요

package collection.set;

import java.util.Arrays;

public class HashStart2 {

    public static void main(String[] args) {
        // 입력: 1,2,5,8
        // [null, 1, 2, null, null, 5, null, null, 8, null]
        Integer[] inputArray = new Integer[10];
        inputArray[1] = 1;
        inputArray[2] = 2;
        inputArray[5] = 5;
        inputArray[8] = 8;
        System.out.println("inputArray = " + Arrays.toString(inputArray));

        int searchValue = 8;
        Integer result = inputArray[searchValue]; // O(1)
        System.out.println("result = " + result);

    }
}

 

2. 메모리 낭비 문제

• 값 자체를 배열의 인덱스로 사용하면 탐색속도를 개선할 수 있음 -> O(1)
• 문제 : 값 자체를 인덱스로 사용하는 방식은 단순하고 빠르지만, 값의 범위가 넓거나 불균형한 경우 메모리 낭비
  • value = 100, arr[100] = true

boolean[] exists = new boolean[1000];
exists[3] = true;
exists[999] = true;

• 값이 위 예시와 같이 들어갈 경우 대부분의 공간이 비게 됨 = 저장할 값은 적은데 메모리 공간은 큼
• 결론 : 메모리 낭비 -> 비효율적
• 해결 : 메모리는 절약하고 빠른 탐색을 유지하는 구조 적용

package collection.set;

import java.util.Arrays;

public class HashStart3 {

    public static void main(String[] args) {
        // 입력: {1,2,5,8,14,99}
        // [null, 1, 2, null, null, 5, null, null, 8, ... , 14, ..., 99]
        Integer[] inputArray = new Integer[100];
        inputArray[1] = 1;
        inputArray[2] = 2;
        inputArray[5] = 5;
        inputArray[8] = 8;
        inputArray[14] = 14;
        inputArray[99] = 99;
        System.out.println("inputArray = " + Arrays.toString(inputArray));

        int searchValue = 99;
        Integer result = inputArray[searchValue]; // O(1)
        System.out.println("result = " + result);
    }
}

 

3. 나머지 연산(%)을 활용한 버킷 인덱싱 -> 해시 함수

• 메모리를 절약하기 위해 고정 크기 배열을 사용하고, 나머지 연산을 통해 인덱스를 분포시킴
• 적은 공간으로도 많은 데이터를 분산 저장 가능
• 탐색할 때도 해당 인덱스의 버킷만 확인하면 됨 -> 탐색 성능 개선
• 문제 : 서로 다른 값인데 같은 인덱스를 가질 수 있음 -> 해시 충돌
• 해결 : 같은 해시 인덱스의 값을 같은 인덱스에 저장

package collection.set;

import java.util.Arrays;

public class HashStart4 {

    static final int CAPACITY = 10;

    public static void main(String[] args) {
        // {1,2,5,8,14,99}
        System.out.println("hashIndex(1) = " + hashIndex(1));
        System.out.println("hashIndex(2) = " + hashIndex(2));
        System.out.println("hashIndex(5) = " + hashIndex(5));
        System.out.println("hashIndex(8) = " + hashIndex(8));
        System.out.println("hashIndex(14) = " + hashIndex(14));
        System.out.println("hashIndex(99) = " + hashIndex(99));

        Integer[] inputArray = new Integer[CAPACITY];
        add(inputArray, 1);
        add(inputArray, 2);
        add(inputArray, 5);
        add(inputArray, 8);
        add(inputArray, 14);
        add(inputArray, 99);
        System.out.println("inputArray = " + Arrays.toString(inputArray));

        // 검색
        int searchValue = 14;
        int hashIndex = hashIndex(searchValue);
        System.out.println("hashIndex = " + hashIndex);
        Integer result = inputArray[hashIndex];
        System.out.println(result);
    }

    static int hashIndex(int value) {
        return value % CAPACITY;
    }

    private static void add(Integer[] inputArray, int value) {
        int hashIndex = hashIndex(value);
        inputArray[hashIndex] = value;
    }
}

 

4. 해시 충돌(Hash Collision)

• 정의
  • 서로 다른 값인데, 해시 함수를 거친 뒤 같은 인덱스에 저장(매핑)되는 현상
• 문제
  • 동일한 인덱스에 여러 값이 들어가게 되면 덮어쓰기, 데이터 손실, 오류 발생 가능성이 있음
• 해결 방법 : 체이닝(Chaining)
  • 하나의 버킷 인덱스에 여러 값을 저장할 수 있도록 버킷을 리스트(LinkedList)로 구성
  • 충돌이 발생하면 해당 인덱스 리스트에 값을 추가
  • 탐색 시에도 해당 버킷 리스트 안에서만 선형 탐색하면 됨
• 시간 복잡도
  • 이상적 : O(1), 해시 분포가 고르게 되어 충돌이 적은 경우
  • 최악 : O(n), 모든 값이 한 버킷에 몰릴 경우, 리스트 내부 선형 탐색 필요

package collection.set;

import java.util.Arrays;
import java.util.LinkedList;

public class HashStart5 {

    static final int CAPACITY = 10;

    public static void main(String[] args) {
        // {1,2,5,8,14,99,9}
        LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
        System.out.println("buckets = " + Arrays.toString(buckets));

        for (int i = 0; i < CAPACITY; i++) {
            buckets[i] = new LinkedList<>();
        }

        System.out.println("buckets = " + Arrays.toString(buckets));

        add(buckets, 1);
        add(buckets, 2);
        add(buckets, 5);
        add(buckets, 8);
        add(buckets, 14);
        add(buckets, 99);
        add(buckets, 9); // 중복
        System.out.println("buckets = " + Arrays.toString(buckets));

        // 검색
        int searchValue = 9;
        boolean contains = contains(buckets, searchValue);
        System.out.println("buckets.contains(" + searchValue + ") =" +contains);
    }

    private static void add(LinkedList<Integer>[] buckets, int value) {
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)

        if (!bucket.contains(value)) { // O(n)
            bucket.add(value);
        }
    }

    private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)

        return bucket.contains(searchValue); //O(n)

//        for (Integer integer : bucket) {
//            if (integer == searchValue) {
//                return true;
//            }
//        }
    }

    static int hashIndex(int value) {
        return value % CAPACITY;
    }
}

---

Hash

 

* Hash(해시)란?

값을 고유한 숫자(인덱스)로 바꿔주는 기술이며, 이를 통해 데이터를 빠르고 효율적으로 다룰 수 있는 자료구조를 만들 수 있음

해시 함수(Hash Function)를 통해 데이터를 특정 위치(버킷)에 저장할 수 있는 매핑(Mapping) 기술

 

* Hash 사용 이유

• 데이터를 빠르게 찾기 위함
• 값을 인덱스로 변환하여 O(1) 수준의 성능 확보
• 배열처럼 직접 접근하면서 유연하게 확장 가능

* Hash 핵심 개념

• 해시 함수 : 값을 받아서 인덱스로 변환 (ex. value % capacity -> 나머지 연산)
• 해시 테이블 : 해시 함수로 변환된 인덱스에 데이터를 저장하는 배열 구조
• 버킷(Bucket) : 같은 인덱스에 여러 값이 저장될 수 있는 공간(충돌 대비)
• 해시 충돌 : 서로 다른 값이 같은 해시 인덱스를 갖는 현상 -> 체이닝 방식(리스트 등)으로 해결

* Hash 자료 구조가 정렬을 보장하지 않는 이유

• 해시 자료구조의 목적
  • 빠른 탐색과 삽입/삭제 : 해시는 O(1)의 성능으로 데이터를 검색하고 추가/삭제할 수 있도록 설계된 자료 구조
• 해시와 정렬의 설계 방향이 다름
  • 해시 구조 : key -> hashCode() -> 인덱스로 변환 -> 버킷에 저장 => 순서 무관, 빠른 접근
  • 정렬 구조(Tree 등) : 데이터 간 비교 가능성을 기준으로 트리나 배열에 정렬된 구조 유지
  • 즉, 해시는 내부에서 값을 정렬된 순서가 아니라 해시 값을 기반으로 저장하기 때문에 순서를 신경 쓰지 않음
• 해시는 위치가 데이터 값이 아니라 해시값에 의해 결정
  • 정렬 자료구조(TreeSet, TreeMap)는 비교 기준(Comparable, Comparator)으로 크기 기준 순서 유지
  • 해시 자료구조(HashSet, HashMap)는 해시 인덱스 기준으로 위치 결정
  • 결론
  • 논리적 순서 ≠ 저장 순서
  • 순서를 유지할 이유가 없음

---

총정리

• 배열은 인덱스로 조회 시 O(1)이지만, 값 기준 탐색은 O(n) -> 성능 저하
• 값을 인덱스로 매핑하면 탐색 성능 개선 가능 -> 값이 커지면 배열 대부분이 비게 되어 메모리 낭비
• 나머지 연산을 사용해 값을 제한된 인덱스로 변환 -> 해시 함수
  • 공간을 줄이면서도 빠른 접근 가능
  • 서로 다른 값이 같은 인덱스를 가질 수 있음 -> 해시 충돌 발생
• 해결 : 체이닝(Chaining) -> 같은 인덱스에 여러 값을 LinkedList로 저장
  • 탐색 시 버킷 안에서만 확인하므로 효율적
  • 시간 복잡도
    • 평균 : O(1)
    • 최악 : O(n)

---

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