[Java] Hash 알고리즘과 Hash충돌

 

간단한 배열에서 값을 찾는 코드를 보자.

Integer[] arr = new Integer[4];
arr[0] = 1;
arr[1] = 2;
arr[2] = 5;
arr[3] = 8;

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

 

위 arr 배열에서 searchValue = 8을 찾으려면 foreach 문에서 처럼 배열을 모두 뒤져야 찾을수있다.

따라서 성능은 O(n) 이다.

 

배열의 장점이라고 할수있는 Index로 데이터를 검색했을때 매우 빠르게 검색할수있다. 즉 Index로 검색시 O(1)의 성능으로 찾을수있다.

 

만약 데이터를 검색할때도 Index를 활용해서 데이터를 한번에 찾을수있다면????

 

그럼 데이터의 값과 배열의 Index를 맞추어서 저장하면 데이터를 O(1)로 빠르게 가져올수있지않을까??해서 데이터의 값자체를 배열의 Index로 사용해보자

Integer[] arr = new Integer[10];
arr[1] = 1;
arr[2] = 2;
arr[5] = 5;
arr[8] = 8;

int searchValue = 8;
Integer result = arr[searchValue];
System.out.println("result = " + result);

//[null, 1 , 2, null, null, 5 , null, null, 8, null]

 

배열인덱스 = 데이터값

 

• index 1 = data 1
• index 2 = data 2
• index 5 = data 5
• index 8 = data 8

이렇게 되면 데이터 1을 찾고싶다면 arr[1] , 데이터 8을 검색하고싶다면?? arr[8]을 입력하면되니까 O(1)의 성능으로 매우빠르게 찾을수있다!

 

그치만... 배열길이가 10인데 배열에 데이터가 들어있는걸 보면 [null, 1 , 2, null, null, 5 , null, null, 8, null] 이네..

그럼 데이터 1, 2 ,5 , 8, 14, 99 를 넣으려면 최소 new Integer[100] 만큼의 배열이 필요하다.

이렇게 인덱스=데이터값으로 만든 배열의 문제는 입력값의 범위만큼 큰 배열을 사용해야해서 배열에 낭비되는 공간이 많이 발생한다.

 

 

여기서 해시알고리즘 비슷한걸 을 도입해본다면....

일단 배열의 크기를 100 에서 CAPACITY크기인 10으로 줄여보고, hashIndex를 구하는 함수를 value % CAPACITY(10)으로 정의해보자.

 

 

searchValue = 14를 위 배열에서 찾는다고 할때

searchValue를 해시인덱스화 시키면 '4' 가 나오고

arr[해시인덱스=4] = 14로 O(1)의 속도로 빠르게 찾을수있다.

 

 

해시(Hash) 알고리즘은 데이터를 찾는 검색 성능을 평균 O(1)로 데이터를 빠르게 찾을수있다.

 

hashcode를 만드는 실제 계산방법은 다음과같은데 

hashCode= s[0] × 31(n−1) + s[1] × 31(n−2) + … + s[n−1]

여기서 

• s[i] 는 문자열의 i번째 문자
• n은 문자열의 길이
• 31은 해시코드를 계산할때 사용하는 상수

인데..

이 계산하는건 어차피 컴퓨터가 해주는거니까 자세히 알필요는 딱히 없을거같다.

 

중요한건 해시알고리즘으로 1) 데이터를 해시인덱스화 시킨다 2) 배열의 인덱스=해시인덱스 공간에 데이터를 넣는다

3) 데이터를 찾을때 데이터를 해시인덱스화 시킨 값으로 배열[해시인덱스] 로 조회하면 O(1)로 빠르게 조회할수있다.

만 알면된다.

 

이 해시알고리즘에는 한계가 있다. 바로 '다른값을 입력했을 때 같은 해시코드가 나올수 있음' 이다.

 

간단히 말해서

해시알고리즘 비슷한걸 로 해시인덱스값을 구하는 방법이 10으로 나눈 나머지라고 할때

99 % 10 = 9 (해시값)

 9 % 9 = 9 (해시값)

 

으로 99와 9가 모두 해시값이 9로 같다.

이는 저장할 위치가 충돌할수 있다는 한계가있는데 이를 Hash충돌 이라고 한다.

 

해시 충돌 ㅠㅠ

 

이 해시충돌 문제를 해결하는 방법은 CAPACITY를 100으로 늘리면 해결되기는 하는데....

이건 메모리 낭비가 심하다는 맨 처음 한계를 해결할수가 없다.

 

해시 충돌 해결

 

해시 충돌은 낮은 확률로 일어날수있다고 가정하고 인정하는것이 바로 해결방법이다.

해시 충돌이 난 경우 내부의 데이터를 하나씩 비교해보면 원하는 결과를 찾을수 있다.

 

즉, 최악의 경우 [9, 19 , 29 , 99 ]를 해시인덱스화 시키면

 

그림 처럼 9 , 9 , 9 , 9로 같은 해시인덱스가 나오고

arr[9=해시인덱스]에 공간에 9, 19, 29, 99가 다들어간다... 

 

그럼 데이터를 찾을때 arr[9]에 있는 값을 다 뒤져봐야되는 O(n)이 되버린다.

 

그치만 hashcode를 만드는 실제 방법을 쓰면 거의 충돌이 일어나지 않게 계산이되고

충돌이 되더라도 배열을 쬐끔만 돌면 되기때문에 속도가 거의 O(1)이라고 할수있게되서 다들 Hash를 쓴다고한다...!