[Java] Hash

1. Set

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

유일성

• Set 에는 중복된 요소가 존재하지 않는다.

순서 미보장

• 대부분의 Set 구현에서는 요소들의 순서를 보장하지 않는다.

• 입력 순서와 출력 순서가 다를 수 있다.

빠른 검색

• Set 은 요소의 유무를 빠르게 확인할 수 있도록 최적화 돼 있다.

• 데이터의 중복을 방지하고 빠른 조회가 가능하다.

---

2. 해시 알고리즘 - index 사용

배열에 중복 데이터가 있는지 확인하려면 항상 전체 데이터를 확인해야 한다.
-> 성능이 나쁘다.

---

3. 해시 알고리즘 - 메모리 낭비

만약 입력 값의 범위가 int 인 모든 범위를 입력할 수 있도록 하려면 심각한 메모리 낭비를 초래한다.

---

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

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

나머지 연산을 통해 구한 인덱스를 해시 인덱스라 한다.

• 입력 값의 범위가 넓어도 배열의 크기를 제한하고, 나머지 연산을 통해 메모리가 낭비되는 문제도 해결할 수있다.

• 해시 인덱스를 사용해 O(1) 의 성능으로 데이터를 저장하고, 조회할 때도 같은 성능으로 조회할 수 있다.

---

5. 해시 알고리즘의 한계 - 해시 충돌

만약 데이터의 입력 값으로 9, 99 가 들어온다면 나머지 연산 후 같은 곳에 2개의 데이터가 저장될 것이다.
다른 값을 입력했는데 같은 해시 코드가 나오는 이것이 해시 충돌이다.

이를 해결하는 방법은 해시 충돌을 인정하는 것이다.
해시 충돌이 일어났을 때 해시 인덱스와 함께 저장하는 것이다.

---

6. 해시 충돌 구현

public class HashStart {
	
    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;
 	}
}

해시 인덱스 충돌 확률

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

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

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

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