해시 알고리즘

import java.util.Arrays;  

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(Arrays.toString(inputArray));  

        int searchValue = 8;  
        for (int inputValue : inputArray) {  
            if (inputValue == searchValue) {  
                System.out.println(inputValue);  
            }  
        }  
    }  
}

import java.util.Arrays;  

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

        int searchValue = 8;  
        Integer result = inputArray[searchValue];  
        System.out.println(result);  
    }  
}

두 개의 코드를 비교해보자
첫번째 코드는 일반적인 케이스로 배열에 순차적으로 값을 저장하는 방법이다.
이 경우에는 searchValue를 찾을때까지 배열을 순회하여 O(n)이다.
반면에 아래 코드를 살펴보면 배열에 들어가는 값에 맞게 인덱스를 설정하였다.
즉 인덱스와 데이터의 값이 일치하게 되면서 검색을 할 때 배열의 인덱스를 찾고자하는 값으로 조회하면 되기때문에 이 경우에는 O(1)이 나오게된다.
이를 통해 엄청난 성능 개선을 할 수 있게되었다.

하지만 단점 하나가 있다면 배열안에 null값이 많아진다는 것이다. 이는 메모리의 낭비를 의미하며 극단적인 예시로는 값이 1과 99단 두 개 밖에 없는데도 배열의 길이를 100으로 선언해주어야한다.

===이렇게 인덱스를 데이터의 값과 일치시킴으로써 엄청난 성능 개선은 있었지만 메모리의 낭비라는 단점이 발생하게 된다. 이 메모리의 낭비단점을 해결하기위해 나타난 개념이 해시 알고리즘이다.===

---

해시 알고리즘 구현

해시 알고리즘은 나머지 연산(%)을 통해 해시 인덱스를 통하여 구현한다.

public class HashStart3 {  
    static final int CAPACITY = 10;  

    public static void main(String[] args) {  
        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));  
    }  

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

앞에서 설명하길, 배열에 정수 데이터를 저장할 때 해당 정수와 일치하게 배열의 인덱스를 배정한다고 설명했었다.
하지만 이 때 메모리의 낭비를 최소화하기위해 해시알고리즘을 적용한다.
위 코드를 살펴보면 저장하고자하는 데이터 value를 배열의 길이(CAPACITY)로 나눈 나머지를 반환하는데 이 때 반환되는 값이 바로 해시인덱스이다. 반환된 해시인덱스에 값을 저장한다면 99를 저장한다고 하더라도 해시인덱스인 9가 나오고 이렇게하면 배열의 메모리 낭비를 방지할 수 있다.
또한 배열의 길이로 나머지연산을 수행하기때문에 배열의 길이를 초과하는 인덱스를 참조할 일도 없다.

위 코드의 실행결과를 살펴보자.

hashIndex(1) = 1
hashIndex(2) = 2
hashIndex(5) = 5
hashIndex(8) = 8
hashIndex(14) = 4
hashIndex(99) = 9

===결과 값은 모두 해시 인덱스를 의미한다===

이제 저장하려는 인덱스의 번호는 알았으니 데이터를 저장해보도록하자

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

해시알고리즘을 통해 배열에 값을 저장하는 메서드이다.
value의 해시인덱스를 구하고 구한 해시인덱스에 값을 넣어주는 간단한 메서드이다.

해시 알고리즘을 적용한 배열사용 및 검색해보기

import java.util.Arrays;  

public class HashStart3 {  
    static final int CAPACITY = 10;  

    public static void main(String[] args) {  
        int[] inputArr = new int[CAPACITY];  
        add(inputArr, 1);  
        add(inputArr, 2);  
        add(inputArr, 5);  
        add(inputArr, 8);  
        add(inputArr, 14);  
        add(inputArr, 99);  

        System.out.println(Arrays.toString(inputArr));  
        int searchValue = 99;  
        int hashIndex = hashIndex(searchValue);  
        System.out.println(hashIndex);  
        int result = inputArr[hashIndex];  
        System.out.println(result); 
    }  

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

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

전체 배열조회 실행결과:
[0, 1, 2, 0, 14, 5, 0, 0, 8, 99]
저장하고자하는 정수들이 모두 정상적으로 해시인덱스에 맞추어 저장되어있음을 확인할 수 있다.
이 때 배열의 길이는 역시 10이다.

데이터 검색 실행결과:
99
데이터 검색부분을 유심히 살펴보면 for문이 전혀 돌아가고 있지 않음을 확인할 수 있다.

int searchValue = 99;  
int hashIndex = hashIndex(searchValue); //값의 인덱스 조회  

int result = inputArr[hashIndex]; //인덱스의 값 조회

그저 인덱스를 통하여 검색하고자하는 값의 데이터를 정확히 조회할 수 있으며
반대로 인덱스를 조회할 때에도 값을 통하여 인덱스를 바로 조회할 수 있다.

두 케이스 모두 O(1)을 갖게되며 add()메서드의 데이터 추가또한 O(1)이다

이 때 하나의 문제점이 남아있는데 바로 데이터의 중복이다.
만약 저장하고자하는 데이터의 값이 9, 29, 99와 같이 있다면 나머지 CAPACITY(10)연산을 수행할 경우 모두 해시인덱스는 9를 얻게되며 3개의 값 모두 inputArr[9]에 저장되려하며 실제로는 저장되지 않고 값이 덮어씌어지게된다.
이러한 문제를 ===해시 충돌===이라고 하며 해시 충돌은 해결하는 방법이 없어 자바에서는 이 문제를 인정하고 충돌이 났을 때 대비방안을 구현해두었다.

---

해시 충돌시 해결방안

자바에서는 해시충돌이 낮을 확률로 나타난다고 가정하고 낮은확률로 해시충돌이 나타났을 경우 해당 해시 인덱스에 겹치는 값을 모두 저장하고자 했다.
하지만 배열에서 하나의 인덱스에 2개이상의 데이터를 저장할 수 없기때문에 배열안에 배열을 넣는 2차원 배열구조로 이 문제를 해결하였다.

코드 구현에서 2차원 배열을 사용하면 이해하기 쉽지않기때문에 List컬렉션을 사용

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

public class HashStart4 {  
    static final int CAPACITY = 10;  

    public static void main(String[] args) {  
    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(Arrays.toString(buckets));  

}

    private static void add(LinkedList<Integer>[] buckets, int value) {  
        int hashIndex = hashIndex(value);  
        LinkedList<Integer> bucket = buckets[hashIndex];  
        if (!bucket.contains(value)) { 
            bucket.add(value);  
        }  
    }  

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

===참고로 위 코드는 Set자료구조를 구현하기위한 해시 알고리즘이기때문에 add()메서드에서 if문을 통해 중복되는 값이 들어오는 것을 막는다.===

이제 위 코드를 실행해보면 9해시인덱스에 99와 9 두개의 데이터가 모두 들어가있는 것을 확인할 수 있다.

해시 충돌 해결 후 데이터 검색

private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {  
    int hashIndex = hashIndex(searchValue);  
    LinkedList<Integer> bucket = buckets[hashIndex];  
    return bucket.contains(searchValue);  
}

위 코드를 이해하기전에 하나 정리하자면

1. 저장하려는 데이터의 나머지 값으로 해시인덱스를 구한다
2. 해당 해시인덱스에는 LinkedList가 생성되어있다
3. 이 LinkedList에는 중복된 값들이 저장될 수 있다. ex)CAPACITY = 10 일 때, [9, 99, 29]

이제 다시 위 코드를 살펴보면 해시인덱스로 LinkedList를 가져오고 그 LinkedList에 찾고자하는 데이터가 있는지 검색하여 있으면 true 없으면 false를 반환받는다.

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

public class HashStart4 {  
    static final int CAPACITY = 10;  

    public static void main(String[] args) {  
        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(Arrays.toString(buckets));  

        int searchValue = 9;  
        int searchValue2 = 99;  
        boolean contains = contains(buckets, searchValue2);  
        System.out.println(contains);  
    }  

    private static void add(LinkedList<Integer>[] buckets, int value) {  
        int hashIndex = hashIndex(value);  
        LinkedList<Integer> bucket = buckets[hashIndex];  
        if (!bucket.contains(value)) { 
            bucket.add(value);  
        }  
    }  

    private static boolean contains(LinkedList<Integer>[] buckets, int searchValue) {  
        int hashIndex = hashIndex(searchValue);  
        LinkedList<Integer> bucket = buckets[hashIndex];  
        return bucket.contains(searchValue);  
    }  

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

강조! 현재는 Set자료구조를 구현중이기때문에 add메서드에서 중복값을 제외한다.
여기서 중복값이란 데이터가 아예 똑같은 값을 의미한다. ex) 99, 99

만약 해시충돌이 발생한다면 LinkedList를 순회해야하기때문에 O(n)의 성능이 나오고
충돌이 발생하지 않을때에는 데이터가 1개만 들어가기때문에 O(1)의 성능을 제공한다.

[!NOTE] 해시 인덱스 충돌 확률
하지만 실질적으로 이 해시 충돌의 확률은 낮다고한다.
통계적으로 데이터의 수가 배열의 크기75%를 넘지 않으면 해시 인덱스는 자주 충돌하지 않고 데이터의 수가 75%를 넘을 경우에는 자주 충돌한다고 한다.
즉, 상황에 따라 다르지만 일반적으로 배열의 크기를 데이터의 수의 +25%로 만들면 해시충돌을 최소화하면서 데이터를 관리할 수 있다.

해시 인덱스의 빅오표기법

• 데이터 저장
  • 평균:O(1)
  • 최악:O(n)
• 데이터 조회
  • 평균:O(1)
  • 최악:O(n)

---

해시알고리즘에서 equals()와 hashCode()재정의의 중요성

중요성을 알아보기전에 먼저 equals()와 hashCode()의 역할을 다시 되새겨보자면

hashCode()의 역할

• 저장하고자하는 데이터의 해시 코드를 리턴해주며 리턴된 정수값으로 데이터를 저장할 배열의 해시 인덱스를 산출해낸다.
  • 이 때 해시코드를 리턴해주는 이유는 문자열 또는 객체와 같은 오브젝트들은 나누기연산을 수행하는 해시 인덱스를 산출해낼 수 없기때문이다.
  • 이 때 해시코드의 리턴된 정수값은 인덱스로 사용되기때문에 반드시 양수가 와야하는데 메서드 내부에서 abs()연산을 수행하여 절대값으로 산출해준다.

equals()의 역할

• 해시 인덱스를 기반으로 데이터를 저장하였을 때 해당 인덱스에 반드시 하나의 값만 저장되는 보장이 없다.
  • 자바는 해시인덱스의 충돌을 인정했기때문
• 해시 알고리즘의 연산결과가 같은 데이터는 같은 해시인덱스에 저장되며 이 과정을 해시 충돌이라고한다.
• 해시 충돌이 나게되면 두 개이상의 값이 같은 인덱스에 저장되는데 배열의 하나의 인덱스에는 하나의 값만 저장 할 수 있다.
• 이 문제를 인덱스 안에 배열 또는 리스트를 만들어서(2차원 배열구조)여러 개의 값을 저장할 수 있도록 대비책을 마련하였다.
• 이 때 같은 인덱스에는 저장된다고는 하지만 저장 기준은 해시알고리즘 기준이기때문에 인덱스에 저장되는 데이터 자체는 다를 수 있다.
• 때문에 해당 인덱스에 어떤값이 존재하는지 확인하기위해서 equals()메서드가 필요하다.

해시 알고리즘을 적용할 때 euqals()와 hashCode()의 역할을 설명해보았고 그렇다면 왜 굳이 재정의를 해야하며 재정의가 왜 중요한것인지 알아보도록하겠다

hashCode()
기본적으로 해시코드 메서드는 Object클래스의 메서드로 객체의 참조값을 기준으로 해시코드를 산출해낸다.

Object obj1 = new Object();  
Object obj2 = new Object();  
System.out.println("obj1.hashCode() = " + obj1.hashCode());  
System.out.println("obj2.hashCode() = " + obj2.hashCode());

//실행결과
obj1.hashCode() = 713338599
obj2.hashCode() = 1067040082

따라서 obj1과 obj2는 서로 다른 참조값을 가지고있기때문에 서로 다른 해시코드를 산출한다는 것을 확인할 수 있다.

하지만 우리가 보통 객체를 사용할 때 다른 참조값을 가지고있더라도 같은 인스턴스임을 의미하도록 설계해야할 때가 종종있다. 이 의미를 '동등성'이라고 한다.
그리고 예시로는 회원의 id, 주문의 주문번호 등등이있다.

아래와 같이 Member라는 클래스가 있다고 가정해보자 이 클래스는 id를 기준으로 각각의 회원들을 분리하고 구분하며 독립성을 갖는다.

이 Member객체를 자료구조에 저장한다고 가정해보자,

public class Member{
    private String id;  

    public Member(String id) {  
        this.id = id;  
    }
}

Member클래스의 hashCode()를 오버라이딩하기 전

Member member1 = new Member("member1");  
Member member2 = new Member("member1");  
System.out.println(member1);  
System.out.println(member2);

//실행결과
mid2.collection.set.member.Member@a09ee92
mid2.collection.set.member.Member@30f39991

id="member1"로 같은 멤버아이디를 가졌음에도 서로 다른 참조값을 가지고있다는 것을 확인할 수 있음

Member클래스 hashCode()재정의

@Override  
public int hashCode() {  
    return Objects.hash(id);  
}

다시 코드를 실행해본 결과

Member member1 = new Member("member1");  
Member member2 = new Member("member1");  
System.out.println(member1);  
System.out.println(member2);

//실행결과
mid2.collection.set.member.Member@388ec8f6
mid2.collection.set.member.Member@388ec8f6

객체의 참조값이 아닌 id필드를 기반으로 해시코드를 리턴하도록 재정의하니 객체의 참조값이 같아짐을 확인할 수 있다.

hashCode()를 재정의함으로써 나온 결론:
메서드를 재정의하기전에는 논리적으로 동일한 회원을 만들고자했는데도 객체의 참조가 다르기때문에 서로 다른 해시코드가 산출되게된다.
이러면 같은 데이터임에도 불구하고 member1, member2모두 서로 다른 해시 인덱스에 저장되며 이는 데이터의 중복저장이 발생된다.

메서드를 id기반으로 해시코드를 산출하도록 재정의함으로써 논리적으로 동등성을 맞추었으며 같은 해시코드를 산출해내기때문에 서로 다른 해시인덱스에 저장되는 일을 걱정할 필요없게되었다.

equals()
hashCode()를 재정의함으로써 논리적 동일성을 갖추었고 같은 MemberId를 가진 멤버데이터를 저장하고자할 때 같은 해시인덱스를 반환받도록 재정의하였다.
이 때 아래 코드와 같이 set에 데이터를 저장한다고 가정해보자

Member member1 = new Member("member1");  
Member member2 = new Member("member1");
set.add(member2);  
set.add(member1);

이렇게 되면 member1과 member2는 같은 해시 인덱스에 저장되게되고(정확히는 해시인덱스 배열 내부 리스트 또는 배열)
그러면 중복되는 데이터가 저장되게된다.

데이터를 저장할 때 contains()메서드로 중복되는 값이 있는지 없는지의 여부를 판별해야하는데 이 때 contains()메서드 내부적으로 equals()메서드를 통해 중복여부를 판별해낸다.
equlas()메서드 또한 Object클래스의 메서드로 기본적으로 객체의 참조값을 기준으로 중복여부를 true, false를 판별하도록 설계되어있다.

@Override  
public boolean equals(Object object) {  
    if (this == object)  
        return true;  
    if (object == null || getClass() != object.getClass())  
        return false;  
    Member member = (Member) object;  
    return Objects.equals(id, member.id);  
}

때문에 위와같이 member의 id를 기준으로 return을 반환하도록 설계해주어야 중복되는 데이터의 저장을 막을 수 있으며 데이터를 검색할 때도 equals()메서드를 재정의함으로써 정확한 데이터의 검색을 할 수 있다.