컬렉션 프레임워크 - 해시(Hash), List vs Set, 직접 구현하는 Set, 해시 알고리즘(시작, index 사용, 메모리 낭비, 나머지 연산, 해시 충돌 설명, 해시 충돌 구현)

출처 : 인프런 - 김영한의 실전 자바 - 중급2편 (유료) / 김영한님  
유료 강의이므로 정리에 초점을 두고 코드는 일부만 인용

---

1. List vs Set

1) 리스트(List) vs 세트(Set)

(1) 리스트(List) - 복습

• 정의: 리스트는 순차적인 컬렉션으로 요소들은 특정 순서를 가지며, 같은 요소가 여러 번 나타날 수 있음
• 특징
  • 순서 유지: 리스트에 추가된 요소는 특정한 순서를 유지하며 순서는 요소가 추가된 순서를 반영할 수 있음
  • 중복 허용: 리스트는 동일한 값이나 객체의 중복을 허용하므로 같은 숫자나 문자열을 리스트 안에 여러번 저장할 수 있음
  • 인덱스 접근: 리스트의 각 요소는 인덱스를 통해 접근할 수 있으며 보통 0부터 시작함
• 용도: 순서가 중요하거나 중복된 요소를 허용해야 하는 경우에 주로 사용됨

(2) 세트(Set, 셋)

• 정의: 세트(셋)는 유일한 요소들의 컬렉션임, 세트보다는 셋으로 많이 불림
• 특징
  • 유일성: 셋에는 중복된 요소가 존재하지 않으므로 셋에 요소를 추가할 때 이미 존재하는 요소면 무시됨
  • 순서 미보장: 대부분의 셋 구현에서는 요소들의 순서를 보장하지 않으므로 요소를 출력할 때 입력 순서와 다를 수 있음
  • 빠른 검색: 요소의 유무를 빠르게 확인할 수 있도록 최적화 되어있어 데이터의 중복을 방지하고 빠른 조회를 가능하게 함
• 용도: 중복을 허용하지 않고 요소의 유무만 중요한 경우에 사용됨

(3) 예시

• List: 장바구니 목록, 순서가 중요한 일련의 이벤트 목록 등
• Set: 회원 ID 집합, 고유한 항목의 집합 등

---

2. 직접 구현하는 Set

1) 직접 구현 시작

(1) MyHashSetV0

• Set은 인덱스가 없기 때문에 단순히 데이터를 넣고 데이터가 있는지 확인하고 데이터를 삭제하는 기능에 데이터 추가 시 중복 여부만 체크해주면 충분하므로 단순한 방식으로 구현할 수 있음
• add(value): 셋에 중복된 값이 있는지 체크하고 중복된 값이 있으면 false를 반환하고 중복된 값이 없으면 값을 저장하고 true를 반환
• contains(value): 셋에 값이 있는지 확인, 셋에 값이 있으면 true를 반환하고 없으면 false를 반환
• remove(value): 셋에 있는 값을 제거
• 위 기능 중에서 단순한 Set 구현을 위해 배열에 데이터를 저장하고 크기도 10으로 고정하였으며 add()와 contains()만 구현
• toString(): IDE를 통해 구현하였지만 그냥 출력하면 배열의 빈 값까지 모두 출력되므로 Arrays.copyOf()를 사용하여 배열에 데이터가 입력된 만큼만 출력되도록 변경

package collection.set;

public class MyHashSetV0 {

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

    // 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 getSize() {
        return size;
    }

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

 

(2) MyHashSetV0Main

• add()로 데이터를 추가할 때 셋에 중복 데이터가 있는지 전체 데이터를 확인하는 로직이 들어있어 맨 처음 값을 입력할때는 O(1)의 성능을 보이지만 그다음부터는 O(n)으로 입력 성능이 나쁨
• contains()로 데이터를 찾을 때는 배열에 있는 모든 데이터를 찾고 비교해야 하므로 평균 O(n)이 걸림

package collection.set;

public class MyHashSetV0Main {
    public static void main(String[] args) {
        MyHashSetV0 set = new MyHashSetV0();
        set.add(1); // O(1)
        set.add(2); // O(n)
        set.add(3); // O(n)
        set.add(4); // O(n)
        System.out.println(set);

        boolean result = set.add(4);// 중복 데이터 저장
        System.out.println("중복 데이터 저장 결과 = " + result);
        System.out.println(set);

        System.out.println("set.contains(3) = " + set.contains(3));
        System.out.println("set.contains(99) = " + set.contains(99));
    }
}
/* 실행 결과
MyHashSetV0{elementData=[1, 2, 3, 4], size=4}
중복 데이터 저장 결과 = false
MyHashSetV0{elementData=[1, 2, 3, 4], size=4}
set.contains(3) = true
set.contains(99) = false
*/

 

(3) 정리

• 직접만든 셋의 구조는 단순하지만 데이터 추가, 검색 모두 O(n)으로 성능이 좋지 않으며 특히 데이터가 많아질 수록 효율은 매우 떨어짐
• 검색의 경우에는 ArrayList, LinkedList도 O(n)이기 때문에 어느정도 받아들일 수 있지만 데이터를 추가할 때에도 중복 데이터가 있는지 체크를 하기 위해 셋의 전체 데이터를 확인해야 하는 부분은 문제가 있음
• 이렇게 데이터를 추가할 때마다 성능이 느린 자료 구조는 사용하기 어렵기 때문에 데이터 추가 시 중복 데이터를 찾는 부분을 개선할 수 있으면 성능 개선이 가능함

---

3. 해시 알고리즘

1) 시작

(1) 문제 - 제시되는 문제를 해결하는 과정을 통해 해시 알고리즘을 이해

• 해시(Hash)알고리즘을 사용하면 데이터를 찾는 검색 성능을 평균 O(1)로 비약적으로 끌어올릴 수 있음
• 입력: 0~9 사이의 여러 값이 입력되며 중복된 값은 입력되지 않음
• 찾기: 0~9 사이의 값이 하나 입력되어 입력된 값 중에 찾는 값이 있는지 확인

(2) HashStart1

• 값을 1, 2, 5, 8로 차례대로 배열에 넣고 배열에서 검색 값 8을 찾으려면 배열에 들어있는 데이터를 모두 반복문으로 찾어서 값을 비교해야 함
• 즉, 배열에서 데이터를 반복문으로 순차적으로 찾기 때문에 O(n)의 성능이 보이는 것으로 이 방법을 변경해야 성능을 개선할 수 있음

package collection.set;

public class HashStart1 {
    public static void main(String[] args) {
        Integer[] inputArray = new Integer[4];
        inputArray[0] = 1;
        inputArray[1] = 2;
        inputArray[2] = 5;
        inputArray[3] = 8;
        System.out.println("inputArray = " + Arrays.toString(inputArray));

        int searchValue = 8;

        // 4번 반복 O(n)
        for (int inputValue : inputArray) {
            if (inputValue == searchValue) {
                System.out.println(inputValue);
            }
        }

    }
}
/* 실행 결과
inputArray = [1, 2, 5, 8]
8
*/

2) index 사용

(1) index를 강제로 활용

• 배열은 인덱스의 위치를 사용하여 데이터를 찾을 때 O(1)으로 매우 빠른 특징을 가지고 있지만 데이터를 검색할 때는 배열에 들어있는 데이터를 하나하나 모두 비교해야하므로 인덱스를 활용할 수 없어서 느릴 수 밖에 없음
• 그런데 만약, 데이터를 검색할 때도 인덱스를 활용하여 데이터를 한 번에 찾을 수 있다면 성능이 O(1)으로 좋아질 수 있음
• 일반적으로는 데이터와 인덱스는 서로 값이 다른게 정상적이지만 생각의 틀을 완전히 뒤집어서 데이터의 값 자체를 배열의 인덱스에 맞추어서 저장해보면 아래 그림처럼 결과가 나올 것임
• 즉, 인덱스1에는 1이, 인덱스 8에는 8이 입력되어있으므로 8의값을 검색할 때 array[8]을 입력하면 인덱스 8에 있는 8의 값이 나오게 됨

 

(2) HashStart2

• 데이터를 입력할 때 배열의 인덱스 순서대로 입력하는 것이 아니라 데이터의 값을 배열의 인덱스로 사용하여 값을 저장
• 배열의 인덱스에 해당 값이 저장되었으므로 데이터를 조회할 때 데이터의 값을 인덱스로 사용해서 조회할 수 있어 O(1)의 성능으로 매우 빠르게 찾을 수 있음

package collection.set;

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];
        System.out.println("result = " + result);

    }
}

/* 실행 결과
inputArray = [null, 1, 2, null, null, 5, null, null, 8, null]
result = 8

*/

 

(3) 정리 및 문제

• 데이터의 값 자체를 배열의 인덱스로 사용하여 O(n)의 검색 성능을 O(1)로 획기적으로 개선할 수 있었음
• 그러나, 입력 값의 범위 만큼 큰 배열을 사용해야하므로 배열에 낭비되는 공간이 너무 많이 발생하게됨

3) 메모리 낭비

(1) HashStart3

• 입력 값의 범위를 0 ~ 99로 늘려서 값을 입력해보면 위에서 발생한 문제를 더욱 극명하게 확인할 수 있음
• 0~99 사이의 여러 값을 중복된 값 없이 입력하고 0 ~ 99 사이의 값으로 입력된 값 중에 찾는 값이 있는지 확인
• 일단 0 ~ 99 사이의 값을 입력해야하고 입력할 값을 인덱스로 활용해야하기 때문에 배열의 크기를 100으로 설정해야 함

package collection.set;

public class HashStart3 {
    public static void main(String[] args) {
        // {1, 2, 5, 8, 14, 99}
        // [null, 1, 2, null, null, 5, ... 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];
        System.out.println("result = " + result);

    }
}
/* 실행 결과
inputArray = [null, 1, 2, null, null, 5, null, null, 8, null, null, null, null, null, 14, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, 99]
result = 99
*/

 

(2) 한계

• 데이터의 값을 인덱스로 사용한덕분에 매우 빠른 검색 속도를 얻을 순 있지만 낭비되는 메모리가 너무 많음
• 만약 0 ~ 99 범위가아니라 int 숫자의 모든 범위를 입력할 수 있도록 하려면 배열의 크기가 17기가 바이트가 필요하게 되어 컴퓨터의 메모리가 거의 다 소모되어버림
• 여기에 값을 4개만 입력하면 4개의 값을 제외한 나머지의 메모리가 빈 공간으로 낭비되는 문제도 존재함
• 뿐만 아니라 처음 배열을 생성하기 위해 메모리를 할당하는데도 너무 오랜 시간이 소모되므로 데이터의 값을 인덱스로 사용하는 방식으로 문제해결을 기대하기는 어려움
• 데이터의 값을 인덱스로 사용하는 방법은 매우 빠른 성능을 보장하지만 입력 값의 범위가 조금만 커져도 메모리 낭비등의 여러 문제가 발생하므로 그대로 사용하기에는 문제가 많음

** 참고

• int는 4byte이므로 사이즈 100인 배열은 단순히 값의 크기로만 계산하면 400byte가 필요함
• 만약 int 범위인 -2,147,483,648 ~ 2,147,483,647의 범위라면 약 42억 사이즈의 배열이 필요하고 4 * 42억을 하면 약 17억의 바이트가 필요하게 됨

4) 나머지 연산

(1) 나머지 연산 활용

• 앞서 이야기한 것처럼 모든 숫자를 입력할 수 있다고 가정하면 입력값의 범위가 너무 넓어져서 데이터의 값을 인덱스로 사용하기에는 여러가지 문제가 발생하여 그대로 사용하기 어려움
• 저장할 수 있는 배열의 크기에 맞추어 나머지 연산을 사용하면 이러한 문제를 어느정도 해결하여 공간도 절약하고 넓은 범위의 값을 사용할 수 있음
• 만약 배열의 크기가 10이라고 가정하면 일반적인 방법으로는 크기가 10인 배열에 10보다 초과하는 값을 저장할수 없지만 나머지 연산의 결과를 사용하면 14는 4로, 99는 9로 10인 배열의 인덱스로 활용할 수 있음
• 즉 나머지 연산의 결과는 절대로 배열의 크기를 넘지 않기 때문에 안전하게 인덱스로 사용할 수 있음
• 1 % 14 -> 4
• 10 * 10 -> 0
• 99 * 10 -> 9

(2) 해시 인덱스

• 이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스(HashIndex)라고 함
• 즉, 위의 예시에서는 14의 해시 인덱스는 4, 99의 해시 인덱스는 9가 됨

(3) 해시 인덱스와 데이터 저장

• 1, 2, 5, 8, 14, 99의 값을 크기가 10인 배열에 저장하려고 할때 저장할 값에 나머지 연산자를 사용하여 해시 인덱스를 구함
• 나머지의 연산 결과로 해시 인덱스가 1, 2, 5, 8, 4, 9 처럼 나오게 되고 해시 인덱스를 배열의 인덱스로 사용하여 데이터를 저장
• 데이터를 저장할 때는 인덱스만 해시 인덱스를 사용하고 값은 원래 실제 값을 저장
• 해시 인덱스를 생성하고 해시 인덱스를 사용하여 배열에 값을 저장하는 두번의 연산이 이루어지지만 두 연산 모두 O(1)의 성능이므로 결과적으로 값을 저장하는데 O(1)의 빠른 성능을 보임

(4) 해시 인덱스와 데이터 조회

• 조회할 값에 나머지 연산자를 사용하여 해시 인덱스를 구한다음 해시 인덱스를 배열의 인덱스로 사용하여 데이터를 조회함
• 해시 인덱스를 사용한 배열에는 원래의 값이 들어가있으므로 원래 값이 조회됨
• 조회도 마찬가지로 해시 인덱스를 구하는데 O(1), 해시 인덱스를 사용해 배열에서 값을 조회하는데 O(1)의 연산이 필요하여 결과적으로 값을 조회하는데 O(1)의 빠른 성능을 제공함

(4) HashStart4

• hashIndex(): 입력 값을 배열의 크기로 나머지 연산을 하여 입력 값을 계산해서 인덱스로 사용하는 해시 인덱스를 반환함
• add(): 해시 인덱스를 먼저 구한 뒤 해시 인덱스를 인덱스로하여 데이터를 저장
• 조회: 해시 인덱스를 구한다음 배열에 해시 인덱스를 대입하여 값을 조회
• 실행 결과를 보면 정상적으로 해시 인덱스가 구해지고, 해시 인덱스를 활용하여 데이터를 저장하고 조회하는 기능이 동작하는 것을 확인할 수 있음

package collection.set;

public class HashStart4 {

    static final int CAPACITY = 10;

    public static void main(String[] args) {
        // {1, 2, 5, 8, 14, 99}
        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);
    }

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


    static int hashIndex(int value) {
        return value % CAPACITY;
    }
}
/* 실행 결과
hashIndex(2) = 2
hashIndex(5) = 5
hashIndex(8) = 8
hashIndex(14) = 4
hashIndex(99) = 9
inputArray = [null, 1, 2, null, 14, 5, null, null, 8, 99]
hashIndex = 4
14
*/

 

(5) 정리

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

(6) 한계 - 해시 충돌

• 그러나 지금까지 설명한 내용은 저장할 때 충돌할 수 있다는 한계가 있음
• 예를 들어 1, 11의 두 값을 10으로 나누게 되면 같은 값인 1이 나와버려 같은 해시 인덱스가 나와버리게 되어 충돌이 발생함

5) 해시 충돌 설명

(1) 해시 충돌

• 위 처럼 서로 다른 값을 입력했지만 같은 해시코드가 나오게 되는 것을 해시 충돌이라고 함
• 해시 충돌이 일어나게되면 같은 해시 인덱스로 값을 저장하기 때문에 나중에 값을 저장한 값만 배열에 남아있게 되는 문제가 발생함
• 이 문제를 해결하는 가장 단순한 방법은 CAPACITY를 값의 입력 범위만큼 키우면 충돌이 발생하지 않겠지만 이 방법은 앞서 다뤄보았듯이 메모리 낭비가 너무 심하기 때문에 이방법으로 해결할 수 없음

(2-2) 해시 충돌 해결 - 저장

• 해시 충돌은 낮은 확률로 일어날 수 있다고 가정하여 해시 충돌을 인정하면 문제 해결의 실마리가 보임
• 즉, 해시 충돌이 일어났을 때 같은 해시 인덱스의 값을 같은 인덱스에 함께 저장해 버리는 것임
• 물론 여러 데이터를 배열의 하나의 공간에 함께 저장할 수 없으므로 배열 안에 배열을 만들면 됨(다른 자료구조를 사용해도 됨)
• 99와 9의 해시 인덱스는 둘다 9이므로 9번 해시 인덱스의 안에 또다른 자료 구조로 99와 9가 저장되는 것임

(2-2) 해시 충돌 해결 - 조회

• 해시 충돌이 난 경우 내부의 데이터를 하나씩 비교해보면 원하는 결과를 찾을 수 있음
• 99의 해시 인덱스는 9이므로 처음 배열에서 9번 인덱스를 찾으면 또 배열이 존재하게 되는데, 여기에서는 모든 값을 검색할 값과 하나씩 비교하여 검색 대상의 값을 조회함
• 9도 해시 인덱스가 9이므로 처음 배열에서 9번 인덱스를 찾으면 나오는 배열의 값을 찾으려는 값과 모두 비교하여 대상의 값을 조회하면됨
• 처음 배열에서 해시 인덱스로 접근하는 것은 한번에 접근이 가능하므로 매우 빠르지만 실제 값을 찾을때에는 값을 하나하나 비교하기때문에 성능이 느려질 수 있지만 해시 충돌이 낮은 확률로 발생한다고 가정하고 이를 인정하는 것임

(2-3) 최악의 경우

• 값을 만약 9, 19, 29, 99만 저장한다고하면 모든 해시 인덱스가 9가 되어 9번 인덱 안에있는 또다른 자료구조에 모든 데이터가 저장됨
• 이렇게 되면 데이터를 찾을 때 결국 9번에 가서 저장한 데이터의 수 만큼 값을 반복해서 비교해야 하므로 최악의 경우 O(n)의 성능을 보임

(3) 정리

• 해시 인덱스를 사용하는 방식은 최악의 경우 O(n)의 성능을 보임
• 하지만 확률적으로 보면 어느 정도 넓게 퍼지기 때문에 평균적으로 보면 대부분 O(1)의 성능을 제공함
• 해시 충돌이 가끔 발생해도 내부에서 값을 몇 번만 비교하는 수준이기 때문에 대부분의 경우 매우 빠르게 값을 찾을 수 있음

6) 해시 충돌 구현

(1) Hashstart5

• LinkedList타입 배열로 해시 충돌을 구현

package collection.set;

public class HashStart5 {

    static final int CAPACITY = 10;

    public static void main(String[] args) {

        // LinkedList 배열
        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("bucket.contains(" + searchValue + ") = " + contains);
    }

    private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<Integer> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);    // 반복해서 값을 찾는 기능이 이미 LinkedList에 구현이 되어있음
    }

    private static void add(LinkedList<Integer>[] buckets, int value) {
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex];    // O(1)
        if (!bucket.contains(value)) {  // Set을 구현할 것이므로 중복값은 저장 안되도록 구현
            bucket.add(value);
        }
    }

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

}
/* 실행 결과
buckets = [[], [1], [2], [], [14], [5], [], [], [8], [99, 9]]
bucket.contains(9) = true
*/

 

(2) 배열 선언

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

• 배열 안에 단순히 값이 들어가는 것이 아니라 해시 충돌을 고려하여 배열 안에 배열이 들어가야 해시 충돌이 발생했을 때 여러 값을 담을 수 있음
• 여기서는 배열 안에 배열 대신에편리하게 사용할 수 있는 연결 리스트를 사용하였음
• LinkedList는 하나의 바구니이고, 이 바구니를 여러개 모아서 배열을 선언하여 배열 안에 연결 리스트가 들어있고 연결 리스트 안에 데이터가 들어가는 구조임
• 즉, 바구니들 안에 각각의 바구니가 있고 바구니 안에 데이터가 들어가있는 구조를 구현함

(3) 데이터 등록

private static void add(LinkedList<Integer>[] buckets, int value) {
    int hashIndex = hashIndex(value);
    LinkedList<Integer> bucket = buckets[hashIndex];    // O(1)
    if (!bucket.contains(value)) {  // Set을 구현할 것이므로 중복값은 저장 안되도록 구현
        bucket.add(value);
    }
}

• 데이터를 등록할 대 먼저 해시 인덱스를 구한다음 해시 인덱스로 배열의 인덱스를 찾으면 그 안의 연결 리스트를 찾을 수 있음
• 셋은 중복된 값을 저장하지 않기 때문에 값을 저장하기 전에 LinkedList가 제공하는 contains()를 사용하여 중복 여부를 확인하고 같은 데이터가 없으면 데이터를 저장함
• LinkedList의 contains는 모든 항목을 다 순회하기 때문에 O(n)의 성능을 보이지만 해시 충돌이 발생하지 않으면 데이터가 1개만 들어있기 때문에 대부분 O(1)의 성능을 보이고 가끔 해시 충돌이 발생했을때에만 O(n)의 성능을 보임

(4) 데이터 검색

private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {
    int hashIndex = hashIndex(searchValue);
    LinkedList<Integer> bucket = buckets[hashIndex];
    return bucket.contains(searchValue);    // 반복해서 값을 찾는 기능이 이미 LinkedList에 구현이 되어있음
}

• 해시 인덱스로 배열의 인덱스를 찾고 들어있는 연결리스트를 찾은 후 연결 리스가 제공하는 contains()메서드를 통해 찾는 데이터가 있는지 확인
• 마찬 가지로 해시 충돌이 발생하지 않으면 데이터가 1개만 들어있기 때문에 O(1)의 대부분은 성능을 제공하고 해시 충돌이 발생하면 O(n)의 성능이 제공됨

(5) 해시 인덱스 충돌 확률

• 해시 충돌이 발생하면 O(n)의 추가 연산을 해야하므로 성능이 떨어지기 때문에 가급적 발생하지 않도록 해야 함
• 해시 충돌이 발생할 확률은 입력하는 데이터의 수와 배열의 크기와 관련이 있기 때문에 입력하는 데이터의 수와 비교하여 배열의 크기가 클 수록 충돌 확률은 낮아짐
• 위에서 작성한 코드에 CAPACITY의 값을 1, 3, 5, 10, 11, 15로 배열의 크기를 변경하면서 실행해보면 대충 그 확률을 알 수 있음
• 아래의 실행 결과에 CAPACITY가 3일때와 10일때의 결과를 비교해보면 해시 충돌의 빈도수가 꽤 많이 나는 것을 확인할 수 있음
• 간단한 예제로 알아보았지만 통계적으로 입력한 데이터의 수가 배열의 크기를 75%를 넘지 않으면 해시 인덱스는 자주 충돌하지 않고 75%를 넘으면 자주 충돌하기 시작함
• 배열의 크기를 크게 만들면 해시 충돌은 줄어들어서 성능이 좋아지지만 메모리가 낭비되고 반대로 배열의 크기를 너무 작게 만들면 해시 충돌이 자주 발생하여 성능이 나빠지기 때문에 상황에 따라 다르겠지만 보통 75%를 적절한 크기로 보고 기준을 잡는 것이 효과적임

실행 결과
CAPACITY = 1 : [[1, 2, 5, 8, 14, 99, 9]]
CAPACITY = 3 : [[99, 9], [1], [2, 5, 8, 14]]
CAPACITY = 5 : [[5], [1], [2], [8], [14, 99, 9]]
CAPACITY = 10: [[], [1], [2], [], [14], [5], [], [], [8], [99, 9]]
CAPACITY = 11: [[99], [1], [2], [14], [], [5], [], [], [8], [9], []]
CAPACITY = 15: [[], [1], [2], [], [], [5], [], [], [8], [99, 9], [], [], [], [], [14]]

 

(6) 정리

• 해시 인덱스를 사용하는 경우 데이터 저장,조회시에 평균적으로 O(1), 최악으로 O(n)의 성능이 보임
• 사실 해시 인덱스를 사용하는 방식은 최악의 경우는 정말 거의 발생하지 않음
• 배열의 크기만 적절하게 잡아주면 대부분 O(1)에 가까운 매우 빠른 성능을 보여줌