'김영한의 실전 자바 - 중급 2편' 강의를 들으면서 복습할만한 내용을 정리하였다.

6. 컬렉션 프레임워크 - 해시(Hash)

6.1 List vs Set

List는 순서가 있으며 중복을 허용하고 인덱스 접근을 한다.

순서가 중요하거나 중복된 요소를 허용해야 하는 경우에 주로 사용된다.

Set

Set 은 유일한 요소들의 컬렉션이다.

특징

• 유일성 : Set 에는 중복된 요소가 존재하지 않는다.
• 순서 미보장 : 대부분의 Set 구현에서는 요소들의 순서를 보장하지 않는다. 즉, 요소들을 출력할 때 입력 순서와 다를 수 있다.
• 빠른 검색 : Set 은 요소의 유무를 빠르게 확인할 수 있도록 최적화 되어 있다. 이는 데이터의 중복을 방지하고 빠른 조회를 가능하게 한다.

중복을 허용하지 않고, 요소의 유무만 중요한 경우에 사용된다.

6.2 해시 알고리즘 - index 사용

배열에 요소를 추가할 때, 중복 데이터가 있는지 전체 데이터를 항상 확인해야 한다. 따라서 O(n)으로 입력 성능이 나쁘다.

배열은 인덱스의 위치를 사용해서 데이터를 찾을 때 O(1)으로 매우 빠른 특징을 가지고 있다.

데이터의 값 자체를 배열의 인데스와 맞추어 저장한다.

즉, 데이터 1은 배열의 인덱스 [1] 위치에 저장된다.

6.3 해시 알고리즘 - 메모리 낭비

만약 입력 값의 범위가 int 숫자의 모든 범위를 입력할 수 있도록 하려면 메모리를 4byte * 42억 = 약 17기가바이트 를 사용하게 된다. 이는 심각한 메모리 낭비를 초래한다.

6.4 해시 알고리즘 - 나머지 연산

저장할 수 있는 배열의 크기를 10 이라고 가정하자. 그 크기에 맞추어 입력하는 데이터를 % 10 나머지 연산을 한 결과 값을 인덱스로 하여 배열에 저장하자.

이렇게 나머지 연산(해시 알고리즘)을 통해 구한 인덱스를 해시 인덱스라 한다.

• 입력 값의 범위가 넓어도 실제 모든 값이 들어오지는 않기 때문에 배열의 크기를 제한하고, 나머지 연산을 통해 메모리가 낭비되는 문제도 해결할 수 있다.
• 해시 인덱스를 사용해서 O(1) 의 성능으로 데이터를 저장하고, O(1) 의 성능으로 데이터를 조회할 수 있게 되었다.

6.5 해시 알고리즘 한계 - 해시 충돌

만약 데이터의 입력 값으로 9, 99 가 들어온다고 생각해보자. 이를 나머지 연산을 하면 같은 값인 9 가 해시 인덱스가 되고 이는 해시 충돌로 이어진다. 이러한 상황을 다른 값을 입력했지만 같은 해시 코드가 나오게 되는 해시 충돌이라고 한다.

이를 해결하는 방법은 해시 충돌을 인정하는 것이다. 해시 충돌은 낮은 확률로 일어날 수 있다고 가정하는 것이다. 해결 방안으로는 해시 충돌이 일어났을 때 같은 해시 인덱스에 함께 저장하는 것이다.

물론 여러 데이터를 배열의 하나의 공간에 함께 저장할 수는 없다. 대신에 배열 안에 배열을 만들면 된다.

6.5 해시 충돌 구현

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];
        for (int i = 0; i < CAPACITY; i++) {
       		buckets[i] = new LinkedList<>();
 		}
 
 		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)
	}
 	
    static int hashIndex(int value) {
 		return value % CAPACITY;
 	}
}

배열 선언

LinkedList<Integer>[] buckets = new LinkedList[CAPACITY]

LinkedList 는 하나의 바구니이고 이런 바구니가 여러개 모여 배열을 선언했다. 즉, 배열 안에 연결 리스트가 들어있고, 연결 리스트 안에 데이터가 들어가는 구조이다. 쉽게 이야기해서 리스트는 바구니, buckets 는 바구니들 인 것이다.

해시 인덱스 충돌 확률

해시 출동이 발생하면 데이터를 추가하거나 조회할 때, 연결 리시트 내부에서 O(n) 의 추가 연산을 해야 하므로 성능이 떨어진다. 따라서 해시 충돌은 가급적 발생하지 않도록 해야 한다.

해시 충돌이 발생할 확률은 입력하는 데이터의 수와 배열의 크기와 관련이 있다. 입력하는 데이터의 수와 비교해서 배열의 크기가 클 수록 충돌 확률은 낮아진다.

상황에 따라 다르겠지만 보통 75% 를 적절한 크기로 보고 기준으로 잡는 것이 효과적이다.

해시 인덱스를 사용하는 방식은 사실 최악의 경우(O(n))는 거의 발생하지 않는다. 배열의 크기만 적절하게 잡아주면 대부분 O(1) 에 가까운 매우 빠른 성능을 보여준다.