Hash

List VS Set

1. List
   요소들의 순차적 컬랙션, 특정 순서를 가지며, 같은 요소 여러번 나타날 수 있다.

• 순서 유지, 중복 허용

2. Set
   유일한 요소들의 컬렉션

• 유일성, 순서 미보장, 빠른 검색

Set 직접 구현

add(value) : 셋에 값을 추가한다. 중복 데이터는 저장하지 않는다.
contains(value) : 셋에 값이 있는지 확인한다.
remove(value) : 셋에 있는 값을 제거한다.

public class MyHashSetV0 {
    private int[] elementData = new int[10];
    private int size = 0;

    //O(n)
    public boolean add(int val) {
        if (contain(val)) {
            return false;
        }

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

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

    public int getSize(){
        return size;
    }

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

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)
        set.add(5); //O(n)
        set.add(3); //O(n)

        boolean rst = set.add(4);
        System.out.println("rst = " + rst);
        System.out.println(set);

        //O(n)
        System.out.println("set.contain(3) = " + set.contain(3));
        System.out.println("set.contain(3) = " + set.contain(99));
    }
}

add()
데이터 추가시, 중복 데이터 확인하기 위해 전체 데이터 확인 O(n)

contains()
데이터를 찾을 때는 배열에 있는 모든 데이터를 찾고 비교 O(n)

해시 알고리즘 시작

public class HashStart1 {
    public static void main(String[] args) {
        Integer[] inputArray = new Integer[4];
        inputArray[0] = 1;
        inputArray[1] = 2;
        inputArray[2] = 3;
        inputArray[3] = 4;

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

        int searchVal = 8;

        for (int inputVal : inputArray) {
            if (inputVal == searchVal){
                System.out.println(inputVal);
            }
        }
     }
}

배열에서 특정 데이터를 찾는 성능은 O(n)으로 느리다.

해시 알고리즘 - index 사용

public class HashStart2 {
    public static void main(String[] args) {
        Integer[] inputArray = new Integer[10];
        inputArray[1] = 1;
        inputArray[2] = 2;
        inputArray[5] = 5;
        inputArray[8] = 8;

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

        int searchVal = 8;

        Integer rst = inputArray[searchVal];
        System.out.println(rst);
    }
}

배열에 낭비되는 공간이 많이 발생함

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

public class HashStart3 {
    public static void main(String[] args) {
        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("Arrays.toString(inputArray) = " + Arrays.toString(inputArray));

        System.out.println();

        int searchVal =99;

        Integer rst = inputArray[searchVal];
        System.out.println(rst);
    }
}

낭비되는 메모리 공간이 너무 많다

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

해시 인덱스
이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스(hashIndex)라 한다

• 저장할 값에 나머지 연산자를 사용해서 해시 인덱스를 구한다.
  -- 1 % 10 = 1
  -- 2 % 10 = 2
  -- 5 % 10 = 5
  -- 8 % 10 = 8
  -- 14 % 10 = 4
  -- 99 % 10 = 9

• 해시 인덱스를 배열의 인덱스로 사용해서 데이터를 저장한다
  인덱스만 해시 인덱스를 사용하고, 값은 원래 값을 저장한다.

public class HashStart4 {

    private static final int CAPACTIY = 10;

    public static void main(String[] args) {

        System.out.println("hashIndex(1) = " + hashIndex(1));
        System.out.println("hashIndex(1) = " + hashIndex(2));
        System.out.println("hashIndex(1) = " + hashIndex(5));
        System.out.println("hashIndex(1) = " + hashIndex(8));
        System.out.println("hashIndex(1) = " + hashIndex(14));
        System.out.println("hashIndex(1) = " + hashIndex(99));

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

        int searchVal = 14;
        int hashIndex = hashIndex(searchVal);
        System.out.println("hashIndex = " + hashIndex);
        Integer rst = inputArray[hashIndex];
        System.out.println("rst = " + rst);
    }

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

    static int hashIndex(int val){
        return val % CAPACTIY;
    }
}

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

해시 인덱스를 사용해서 O(1)의 성능으로 데이터를 저장하고, O(1)의 성능으로 데이터를 조회할 수 있게 되었다.덕분에 자료 구조의 조회 속도를 비약적으로 향상할 수 있게 되었다

한계 - 해시 충돌
저장할 위치가 충돌할 수 있다는 한계

해시 알고리즘 - 해시 충돌

이 문제를 간단하게 해결하는 방법은 CAPACITY 값의 입력 범위 만큼 키우면 된다.
단 메모리 낭비가 큼

해결

여러 데이터를 배열의 하나의 공간에 함께 저장 X, 배열 안에 배열을 만들면 된다.

public class HashStart5 {

    private static final int CAPACTIY = 10;

    public static void main(String[] args) {

        //링크드 리스트를 넣을 수 있는 배열 (배열 안에 배열)
        LinkedList<Integer>[] list = new LinkedList[CAPACTIY];
        for (int i = 0; i < CAPACTIY; i++) {
            list[i] = new LinkedList<>();
        }

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

        int searchVal = 9;
        boolean contains = contains(list, searchVal);
        System.out.println("list.contains( " + searchVal + ") = " + contains);
    }

    private static boolean contains(LinkedList<Integer>[] list, int searchVal) {
        int hashIndex = hashIndex(searchVal);
        //중복으로 들어갈 수 있게 자료 구조를 넣어주어야 한다.
        LinkedList<Integer> bucket = list[hashIndex];
        return bucket.contains(searchVal);
    }

    public static void add(LinkedList<Integer>[] buckets, int val) {
        int hashIndex = hashIndex(val);
        LinkedList<Integer> bucket = buckets[hashIndex];
        //중복 check
        if (!bucket.contains(val)) {
            bucket.add(val);
        }
    }

    static int hashIndex(int val){
        return val % CAPACTIY;
    }
}

배열 선언

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

배열 안에 배열 대신 편리하게 사용할 수 있는 연결리스트 사용
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)) { //O(n)
 bucket.add(value);
 }
}

데이터 등록 -> hashIndex 구한다.
해시 인덱스로 배열의 인덱스를 찾는다. 배열에는 연결리스트 들어있다.
바구니에 값을 저장하기 전에 contains() 를 사용해서 중복 여부를
확인한다. 만약 바구니에 같은 데이터가 없다면 데이터를 저장한다.

데이터 검색

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)
}

해시 인덱스 충돌 확률

데이터의 수가 배열의 크기를 75% 넘지 않는다면 인덱스는 충돌 확률 줄어든다.