package collection.set;import java.util.Arrays;import java.util.LinkedList;public class HashStart5 { static final int CAPACITY = 10; public static void main(String[] args) { //{1,2,5,8,14,99} LinkedList[] buckets = new LinkedList[CAPACITY]; System.out.println("buckets = " + Arrays.toString(buckets)); for (int i = 0; i (); } System.out.println("buck..

해시 충돌99, 9의 두 값은 10으로 나누면 9가 된다. 따라서 다른 값을 입력했지만 같은 값의 해시 코드가 나오게 되는데 이것을 해시 충돌이라 한다.99 % 10 = 99 % 10 = 9 해시 충돌이 발생하면 어떤 문제가 나타나는지 알아보자.먼저 99의 값을 저장한다. 해시 인덱스는 9이므로 9번 인덱스에 99 값을 저장한다.다음으로 9의 값을 저장한다. 해시 인덱스는 9이므로 9번 인덱스에 9 값을 저장한다결과적으로 배열의 인덱스 9 에는 처음에 저장한 값 99는 사라지고, 마지막에 저장한 값 9만 남게된다. 이 문제를 해결하는 가장 단순한 방법은 CAPACITY를 값의 입력 범위만큼 키우면 된다. 여기서는 99까지만 입력하므로 CAPACITY를 100으로 늘리면 된다. 그러면 충돌이 발생하지 않는..

앞에서 이야기한 것 처럼 모든 숫자를 입력할 수 있다고 가정하면, 입력값의 범위가 너무 넓어져서 데이터의 값을 인덱스로 사용하기는 어렵다. 하지만 입력 값의 범위가 넓어도 해당 범위의 값을 모두 다 입력하는 것은 아니다.앞의 예에서 0~99 범위의 값 중에 1,2,5,8,14,99만 입력했다. 따라서 대부분의 공간은 낭비되었다. 공간도 절약하면서, 넓은 범위의 값을 사용할 수 있는 방법이 있는데, 바로 나머지 연산을 사용하는 것이다.저장할 수 있는 배열의 크기(CAPACITY)를 10이라고 가정하자. 그 크기에 맞추어 나머지 연산을 사용하면 된다.여기서 14,99는 10보다 큰 값이다. 따라서 일반적인 방법으로는 크기가 10인 배열의 인덱스로 사용할 수 없다.하지만 나머지 연산의 결과를 사용하면 14는 ..

이번에는 입력값의 범위를 0~99까지 넓혀보자. 문제입력 : 0~99 사이의 여러 값이 입력된다. 중복된 값은 입력되지 않는다.찾기 : 0~99 사이의 값이 하나 입력된다. 입력된 값 중에 찾는 값이 있는지 확인해보자.검색 속도를 높이기 위해 앞서 학습한 것 처럼 데이터의 값을 배열의 인덱스로 사용하자.따라서 데이터가 0~99 까지 입력될 수 있다면 인덱스도 0~99까지 사용할 수 있어야 한다. 따라서 크기 100의 배열이 필요하다.package collection.set;import java.util.Arrays;public class HashStart3 { public static void main(String[] args) { //입력 1,2,5,8,14,99 Inte..

배열은 인덱스의 위치를 사용해서 데이터를 찾을 때 O(1)로 매우 빠른 특징을 가지고 있다.반면에 데이터를 검색할 때는 배열에 들어있는 데이터 하나하나를 모두 비교해야 하므로 인덱스를 활용할 수 없다.그런데 만약에 데이터를 검색할 때도 인덱스를 활용해서 데이터를 한 번에 찾을 수 있다면 어떻게 될까?이렇게만 할 수 있다면 O(n) -> O(1)로 바꾸어서 성능을 획기적으로 끌어올릴 수 있을 것이다. 물론 인덱스와 데이터의 값은 서로 다르기 때문에 이것은 불가능하다.인덱스 0에는 데이터 1이 들어있고, 인덱스 3에는 데이터 8이 들어있다.결국 여기에 8이라는 데이터가 있는지 찾으려면 순서대로 모든 데이터를 비교해야 한다. 여기서 생각의 틀을 완전히 뒤집어보자.데이터의 값 자체를 배열의 인덱스와 맞추어 저장..

해시(hash)알고리즘을 사용하면 데이터를 찾는 검색 성능을 평균 O(1)로 비약적으로 끌어올릴 수 있다.해시 알고리즘을 이해하기 위해 먼저 간단한 예제를 만들어보자. 문제입력 : 0~9 사이의 여러 값이 입력된다. 중복된 값은 입력되지 않는다.찾기 : 0~9 사이의 값이 하나 입력된다. 입력된 값 중에 찾는 값이 있는지 확인해보자.package collection.set;import java.util.Arrays;public class HashStart1 { public static void main(String[] args) { Integer[] inputArray = new Integer[4]; inputArray[0]=1; inputArray[1]=2; ..