[JAVA] 컬렉션 프레임워크 - List, Hash

0. 개요

List에 대해 알아보자

1. 리스트 추상화1 - 인터페이스 도입

자료 구조에 다형성과 OCP 원칙이 어떻게 적용되는지 알아보자.

List 자료 구조

• 순서가 있고, 중복을 허용하는 자료 구조를 리스트(List)라 한다.
• 우리가 지금까지 만든 MyArrayList 와 MyLinkedList는 내부 구현만 다를 뿐 같은 기능을 제공하는 리스트이다.
• 물론 내부 구현이 다르기 때문에 상황에 따라 성능은 달라질 수 있다. 핵심은 사용자 입장에서 보면 같은 기능을 제공한다는 것이다.
• 이 둘의 공통 기능을 인터페이스로 뽑아서 추상화하면 다형성을 활용한 다양한 이득을 얻을 수 있다.

같은 기능을 제공하는 메서드를 MyList 인터페이스로 뽑아보자.
지금부터 collection.list 패키지를 사용한다. 패키지 위치에 주의하자.

public interface MyList<E> {

    int size();

    void add(E e);

    void add(int index, E e);

    E get(int index);

    E set(int index, E element);

    E remove(int index);

    int indexOf(E o);
}

• collection.array.MyArrayListV4 코드를 복사해서 MyList 인터페이스를 구현하는 MyArrayList를 만들자.

package collection.list;

import java.util.Arrays;

public class MyArrayList<E> implements MyList<E> {
	//...
}

• collection.link.MyLinkedListV3 코드를 복사해서 MyList 인터페이스를 구현하는 MyLinkedList를 만들자.

package collection.list;

public class MyLinkedList<E> implements MyList<E> {
	//...
}

• 메서드 이름이 같기 때문에 문제가 발생하지 않는다.
• 추가로 재정의한 메서드에 @Override 에노테이션도 넣어준다.

2. 리스트 추상화2 - 의존관계 주입

• MyArrayList를 활용해서 많은 데이터를 처리하는 BatchProcessor 클래스를 개발하고 있다고 가정하자.
• 그런데 막상 프로그램을 개발하고 보니 데이터를 앞에서 추가하는 일이 많은 상황이라고 가정해보자.
• 데이터를 앞에서 추가하거나 삭제하는 일이 많다면 MyArrayList 보다는 MyLinkedList를 사용하는 것이 훨씬 효율적이다.

• 구체적인 MyArrayList 를 구현한 코드를 MyLinkedList로 변경하려면 BatchProcessor 의 내부 코드도 MyArrayList 에서 MyLinkedList 를 사용하도록 함께 변경해야 한다.
• 이렇게 구체적인 클래스에 직접 의존하면 MyArrayList 를 MyLinkedList 로 변경할 때 마다 여기에 의존하는 BatchProcessor 의 코드도 함께 수정해
  야 한다.
• 이를 해결하는 방법으로는 BatchProcessor 가 구체적인 클래스에 의존하는 대신 추상적인 MyList 인터페이스에 의존하는 방법도 있다.

추상적인 MyList에 의존하는 BatchProcessor 예시

public class BatchProcessor {

    private final MyList<Integer> list;

	public BatchProcessor(MyList<Integer> list) {
		this.list = list;
	}

	public void logic(int size) {
		for (int i = 0; i < size; i++) {
			list.add(0, i); //앞에 추가
		}
	}
}

main() {
	new BatchProcessor(new MyArrayList()); //MyArrayList를 사용하고 싶을 때
	new BatchProcessor(new MyLinkedList()); //MyLinkedList를 사용하고 싶을 때
}

• 그리고 BatchProcessor 를 생성하는 시점에 생성자를 통해 원하는 리스트 전략을 선택해서 전달하면 된다.
• 이렇게 하면 MyList 를 사용하는 클라이언트 코드인 BatchProcessor 를 전혀 변경하지 않고, 원하는 리스트 전략을 런타임에 지정할 수 있다.
• 정리하면 다형성과 추상화를 활용하면 BatchProcessor 코드를 전혀 변경하지 않고 리스트 전략을 MyArrayList에서 MyLinkedList로 변경할 수 있다.

실제 코드를 작성해보자

public class BatchProcessor {
    private final MyList<Integer> list ;

    public BatchProcessor(MyList<Integer> list){
        this.list = list;
    }

    public void logic(int size){
        long startTime = System.currentTimeMillis();
        for(int i=0; i<size; i++){
            list.add(0, i); // 앞에 추가
        }
        long endTime = System.currentTimeMillis();
        System.out.println("크기: " + size + ", 계산 시간: " + (endTime - startTime)
                + "ms");
    }
}

• logic(int size) 메서드는 매우 복잡한 비즈니스 로직을 다룬다고 가정하자. 이 메서드는 list의 앞 부분에 데이터를 추가한다.
• 어떤 MyList list의 구현체를 선택할 지는 실행 시점에 생성자를 통해서 결정한다.
• 생성자를 통해서 MyList 구현체가 전달된다.
  • MyArrayList의 인스턴스가 들어올 수도 있고, MyLinkedList의 인스턴스가 들어올 수도 있다.
• 이것은 BatchProcessor의 외부에서 의존관계가 결정되어서 BatchProcessor 인스턴스에 들어오는 것 같다. 마치 의존관계가 외부에서 주입되는 것 같다고 해서 이것을 의존관계 주입이라 한다.
• 참고로 생성자를 통해서 의존관계를 주입했기 때문에 생성자 의존관계 주입이라 한다.

의존관계 주입

public class BatchProcessorMain {
    public static void main(String[] args) {
        MyArrayList<Integer> list = new MyArrayList<>();
        //MyLinkedList<Integer> list = new MyLinkedList<>();

        BatchProcessor processor = new BatchProcessor(list);
        processor.logic(50_000);
    }
}

• BatchProcessor의 생성자에 MyArrayList를 사용할지, MyLinkedList를 사용할지 결정해서 넘겨야 한다.
• 이후에 processor.logic()를 호출하면 생성자로 넘긴 자료 구조를 사용해서 실행한다.

MyLinkedList 를 사용한 덕분에 MyArrayList를 사용했을 때의 O(n)이 O(1)로 훨씬 더 성능이 개선 된 것을 확인할 수 있다. 데이터가 증가할수록 성능의 차이는 더 벌어진다.

3. 리스트 추상화3 - 컴파일 타임, 런타임 의존관계

의존관계는 크게 컴파일 타임 의존관계와 런타임 의존관계로 나눌 수 있다. (둘다 사용)

• 컴파일 타임 : 코드 컴파일 시점을 뜻한다.
• 런타임 : 프로그램 실행 시점을 뜻한다.

1) 컴파일 타임 의존관계

• 컴파일 타임 의존관계는 자바 컴파일러가 보는 의존관계이다. 클래스에 모든 의존관계가 다 나타난다.
• 쉽게 이야기해서 클래스에 바로 보이는 의존관계이다. 그리고 실행하지 않은 소스 코드에 정적으로 나타나는 의존관계이다.
• BatchProcessor 클래스를 보면 MyList 인터페이스만 사용한다. 코드 어디에도 MyArrayList나 MyLinkedList 같은 정보는 보이지 않는다. 따라서, BatchProcessor는 MyList 인터페이스에만 의존한다.

2) 런타임 의존관계

• 런타임 의존관계는 실제 프로그램이 작동할 때 보이는 의존관계다. 주로 생성된 인스턴스와 그것을 참조하는 의존관게이다.
• 쉽게 이야기해서 프로그램이 실행될 때 인스턴스 간에 의존관계로 보면 된다.
• 런타임 의존관계는 프로그램 실행 중에 게속 변할 수 있다.

다음과 같이 코드를 작성하고 실행한다고 가정하자.

MyArrayList<Integer> list = new MyArrayList<>();
BatchProcessor processor = new BatchProcessor(list);
processor.logic(50_000);

• BatchProcessor 인스턴스의 MyList list 는 생성자를 통해 MyArrayList(x001) 인스턴스를 참조한다.
  • BatchProcessor 인스턴스에 MyArrayList(x001) 의존관계를 주입한다.
• 따라서 이후 logic() 을 호출하면 MyArrayList 인스턴스를 사용하게 된다.

정리

• MyList 인터페이스의 도입으로 같은 리스트 자료구조를 그대로 사용하면서 원하는 구현을 변경할 수 있게 되었다.
• BatchProcessor에서 다음과 같이 처음부터 MyArrayList를 사용하도록 컴파일 타임 의존관계를 지정했다면 이후에 MyLinkedList로 수정하기 위해서는 BatchProcessor의 코드를 변경해야 한다.

public class BatchProcessor {
	private final MyArrayList<Integer> list = new MyArrayList(); //코드 변경 필요
}

• BatchProcessor 클래스는 구체적인 MyArrayList 나 MyLinkedList 에 의존하는 것이 아니라 추상적인 MyList 에 의존한다. 따라서 런타임에 MyList 의 구현체를 얼마든지 선택할 수 있다.
• BatchProcessor 에서 사용하는 리스트의 의존관계를 클래스에서 미리 결정하는 것이 아니라, 런타임에 객체를 생성하는 시점으로 미룬다. 따라서 런타임에 MyList 의 구현체를 변경해도 BatchProcessor 의 코드는 전혀 변경하지 않아도 된다.
• 이렇게 생성자를 통해 런타임 의존관계를 주입하는 것을 생성자 의존관계 주입 또는 줄여서 생성자 주입이라 한다.

4. 직접 구현한 리스트의 성능 비교

이론적으로 MyLinkedList가 평균 추가(중간 삽입)에 있어 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화 등을 고려할 때 MyArrayList가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

배열 리스트 vs 연결 리스트
대부분의 경우 배열 리스트가 성능상 유리하다. 이런 이유로 실무에서는 주로 배열 리스트를 기본으로 사용한다. 만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.

5. 자바 리스트

List 자료 구조
순서가 있고, 중복을 허용하는 자료 구조를 리스트라 한다. 리스트와 관련된 컬렉션 프레임워크는 다음 구조를 가진다.

1) Collection 인터페이스

• Collection 인터페이스는 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나이다. 이 인터페이스는 자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의한다.
• Collection 인터페이스는 List ,Set , Queue 와 같은 다양한 하위 인터페이스와 함께 사용되며, 이를 통해 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있다.

2) List 인터페이스

• List 인터페이스는 java.util 패키지에 있는 컬렉션 프레임워크의 일부다. - List 는 객체들의 순서가 있는 컬렉션을 나타내며, 같은 객체의 중복 저장을 허용한다. 이 리스트는 배열과 비슷하지만, 크기가 동적으로 변화하는 컬렉션을 다룰 때 유연하게 사용할 수 있다.

• List 인터페이스는 ArrayList , LinkedList 와 같은 여러 구현 클래스를 가지고 있으며, 각 클래스는 List 인터페이스의 메서드를 구현한다.

3) 자바 ArrayList

• java.util.ArrayList
• 자바가 제공하는 ArrayList 는 우리가 직접 만든 MyArrayList 와 거의 비슷하다. 특징은 다음과 같다.

3-1) 자바 ArrayList의 특징

• 배열을 사용해서 데이터를 관리한다.

• 기본 CAPACITY는 10이다.( DEFAULT_CAPACITY = 10 )
  • CAPACITY 를 넘어가면 배열을 50% 증가한다.
  • 10 15 22 33 49로 증가한다. (최적화는 자바 버전에 따라 달라질 수 있다.)

• 메모리 고속 복사 연산을 사용한다.
  • ArrayList 의 중간 위치에 데이터를 추가하면, 추가할 위치 이후의 모든 요소를 한 칸씩 뒤로 이동시켜야 한다.
  • 자바가 제공하는 ArrayList 는 이 부분을 최적화 하는데, 배열의 요소 이동은 시스템 레벨에서 최적화된 메모리 고속 복사 연산을 사용해서 비교적 빠르게 수행된다. 참고로 System.arraycopy() 를 사용한다.

데이터 추가 - 한 칸씩 이동하는 방식 vs 메모리 고속 복사 연산 사용

1. 한 칸씩 이동하는 방식

• 데이터를 루프를 돌면서 하나씩 이동해야 하기 때문에 매우 느리다.
• MyArrayList에서 사용한 방식이다.

2. 메모리 고속 복사 연산 사용

• 시스템 레벨에서 배열을 한 번에 아주 빠르게 복사한다. 이 부분은 OS, 하드웨어에 따라 성능이 다르기 때문에 정확한 측정이 어렵지만, 한 칸씩 이동하는 방식과 비교하면 보통 수 배 이상의 빠른 성능을 제공한다.

4) 자바 LinkedList

java.util.LinkedList
자바가 제공하는 LinkedList 는 우리가 직접 만든 MyLinkedList 와 거의 비슷하다. 특징은 다음과 같다.

4-1) 자바의 LinkedList 특징

• 이중 연결 리스트 구조
• 첫 번째 노드와 마지막 노드 둘다 참조

단일 연결 리스트

• 우리가 직접 만든 MyLinkedList의 노드는 다음 노드로만 이동할 수 있는 단일 연결 구조이다. 따라서, 이전 노드로 이동할 수 없다는 단점이 있다.

이중 연결 리스트

• 자바가 제공하는 LinkedList는 이중 연결 구조를 사용한다. 이 구조는 다음 노드 뿐만 아니라 이전 노드로도 이동할 수 있다.
  • node.next를 호출하면 다음 노드로, nod.prev를 호출하면 이전 노드로 이동한다.
• 마지막 노드에 대한 참조를 제공한다. 따라서 데이터를 마지막에 추가하는 경우에도 O(1) 의 성능을 제공한다.
• 이전 노드로 이동할 수 있기 때문에 마지막 노드부터 앞으로, 그러니까 역방향으로 조회할 수 있다.

6. 자바 리스트의 성능 비교

자바가 제공하는 리스트의 성능을 비교해보자.

이론적으로 LinkedList 가 중간 삽입에 있어 더 효율적일 수 있지만, 현대 컴퓨터 시스템의 메모리 접근 패턴, CPU 캐시 최적화, 메모리 고속 복사 등을 고려할 때 ArrayList 가 실제 사용 환경에서 더 나은 성능을 보여주는 경우가 많다.

배열 리스트 vs 연결 리스트
대부분의 경우 배열 리스트가 성능상 유리하다. 이런 이유로 실무에서는 주로 배열 리스트를 기본으로 사용한다. 만약 데이터를 앞쪽에서 자주 추가하거나 삭제할 일이 있다면 연결 리스트를 고려하자.

컬렉션 프레임워크 - 해시(Hash)

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

자료 구조에서의 List 와 Set 은 각각 특정한 방식으로 데이터를 저장하고 관리하는 데 사용된다.

1. List(리스트)

정의 : 리스트는 요소들의 순차적인 컬렉션이다. 요소들은 특정 순서를 가지며, 같은 요소가 여러 번 나타날 수 있다.

2. Set(셋)

• 정의 : set 은 유일한 요소들의 컬렉션이다.
• 특징 :
  • 유일성
  • 순서 미보장
  • 빠른 검색
• 용도 : 중복을 허용하지 않고, 요소의 유무만 중요한 경우에 사용한다.

예시

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

0. 직접 구현하는 Set0 - 시작

셋을 구현하는 것은 아주 단순하다. 인덱스가 없기 때문에 단순히 데이터를 넣고, 데이터가 있는지 확인하고, 데이터를 삭제하는 정도면 충분하다. 그리고 데이터를 추가할 때 중복 여부만 체크해주면 된다.

• 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 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 +
                '}';
    }
}

• 예제에서는 단순함을 위해 배열에 데이터를 저장한다. 배열의 크기도 10으로 고정했다.
• add(value) : 셋에 중복된 값이 있는지 체크하고, 중복된 값이 있으면 false 를 반환한다. 중복된 값이 없으면 값을 저장하고 true 를 반환한다.
• contains(value) : 셋에 값이 있는지 확인한다. 값이 있으면 true 를 반환하고, 값이 없으면 false 를 반환한다.
• toString() : 배열을 출력하는 부분에 Arrays.copyOf() 를 사용해서 배열에 데이터가 입력된 만큼만 출력한다.

정리
우리가 만든 셋은 구조는 단순하지만, 데이터 추가, 검색 모두 O(n) 으로 성능이 좋지 않다.

1. 해시 알고리즘1 - 시작

해시 알고리즘을 사용하면 데이터를 찾는 검색 기능을 평균 O(1)로 비약적으로 끌어올릴 수 있다.

문제

• 입력 : 0~9 사이의 여러 값이 입력된다. 중복된 값은 입력되지 않는다.
• 찾기 : 0~9 사이의 값이 하나 입력된다. 입력된 값 중에 찾는 값이 있는지 확인해보자.

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

• 입력 값은 1,2,5,8 이다. 이 값을 배열에 넣고, 배열에서 검색 값 8을 찾아보자.
• 이 값을 찾으려면 배열에 들어있는 데이터를 모두 찾아서 값을 비교해야 한다.
• 따라서, 배열에서 특정 데이터를 찾는 성능은 O(n) 으로 느리다. 물론, 데이터가 많아질 수록 더 느려진다.

2. 해시 알고리즘2 - index 사용

• 배열은 인덱스의 위치를 사용해서 데이터를 찾을 때 O(1)로 매우 빠른 특징을 가지고 있다.
• 반면에, 데이터를 검색할 때는 배열에 들어있는 데이터 하나하나를 모두 비교해야 하므로 인덱스를 사용할 수 없다.
• 그런데 만약에 데이터를 검색할 때도 인덱스를 활용해서 데이터를 한 번에 찾을 수 있다면 성능을 O(1)로 바꾸어서 성능을 획기적으로 끌어올릴 수 있을 것이다.

물론 인덱스와 데이터의 값은 서로 다르기 때문에 이것은 불가능하다.

• 인덱스 0 -> 데이터 1
• 인덱스 1 -> 데이터 2
• 인덱스 2 -> 데이터 5
• 인덱스 3 -> 데이터 8

• 인덱스 0에는 데이터1이 들어있고, 인덱스 3에는 데이터 8이 들어있다.
• 결국, 8이라는 데이터가 있는지 찾으려면 순서대로 모든 데이터를 비교해야 한다.

하지만, 데이터의 값 자체를 인덱스와 맞추어 저장하면 어떻게 될까?

• 인덱스 1 -> 데이터 1
• 인덱스 2 -> 데이터 2
• 인덱스 5 -> 데이터 5
• 인덱스 8 -> 데이터 8

인덱스 1에는 데이터 1이 들어있고, 인덱스 8에는 데이터 8이 들어있다.
저장하는 데이터와 인덱스를 완전히 맞춘 것이다. 이제 인덱스 번호가 데이터가 되고, 데이터가 인덱스 번호가 되었다.

이제 데이터를 검색해보자.

• 데이터 1을 찾으려면 array[1]을 입력하면 된다.
• 데이터 2을 찾으려면 array[2]을 입력하면 된다.
• 데이터 5을 찾으려면 array[5]을 입력하면 된다.
• 데이터 8을 찾으려면 array[8]을 입력하면 된다.

• 이제 데이터가 인덱스 번호가 된다.
  따라서, 배열의 인덱스를 활용해서 단번에 필요한 데이터를 찾을 수 있다.
• 데이터의 값을 인덱스 번호로 사용하는 아주 간단한 아이디어 하나로 O(n) 의 검색 연산은 O(1) 의 검색 연산으로 바꿀 수 있다.

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]; // O(1)
        System.out.println(result);
    }
}

문제
입력 값의 범위 만큼 큰 배열을 사용해야 한다. 따라서, 배열에 낭비되는 공간이 많이 발생한다.

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

이번에는 입력 값의 범위를 0~99로 넓혀보자.

• 입력 : 0~99 사이의 여러 값이 입려된다. 중복된 값은 입력되지 않는다.
• 찾기 : 0~99 사이의 값이 하나 입력된다. 입력된 값 중에 찾는 값이 있는지 확인해보자.

한계

• 데이터의 값을 인덱스로 사용한 덕분에 O(1)의 매우 빠른 검색 속도를 얻을 수 있다. 그리고 이 코드는 정상적으로 수행된다.
• 하지만, 낭비되는 메모리 공간이 너무 많다.

만약 입력 값의 범위를 0~99 를 넘어서 int 숫자의 모든 범위를 입력할 수 있도록 하려면 배열의 크기를 얼마로 잡아야 할까?

• 0~99 까지 범위 입력
  • 사이즈 100의 배열이 필요 : 4byte * 100 ( 단순히 값의 크기로만 계산 )
• int 범위 입력
  • int 범위 : -2,147,483,648 ~ 2,147,483,647
  • 약 42억 사이지의 배열 필요
  • 4byte * 42억 = 약 17기가바이트 필요 (단순히 값의 크기로만 계산)

• 데이터의 값을 인덱스로 사용할 때, 입력할 수 있는 값의 범위가 int 라면 한번의 연산에 최신 컴퓨터의 메모리가 거의 다 소모되어 버린다.
• 만약 사용자가 1, 2, 1000, 200000의 네 개의 값만 입력한다면 나머지 대부분의 메모리가 빈 공간으로 낭비될 것이다. 뿐만 아니라 처음 배열을 생성하기 위해 메모리를 할당하는데도 너무 오랜 시간이 소모된다.
• 따라서 데이터의 값을 인덱스로 사용하는 방식은 입력 값의 범위가 넓다면 사용하기 어려워 보인다.
• 데이터의 값을 인덱스로 사용하는 방법은 매우 빠른 성능을 보장하지만, 입력 값의 범위가 조금만 커져도 메모리 낭비가 너무 심하다. 따라서 그대로 사용하기에는 문제가 있다.

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

• 앞에서 이야기한 것처럼 모든 숫자를 입력할 수 있다고 가정하면, 입력값의 범위가 너무 넓어져서 데이터의 값을 인덱스로 사용하기는 어렵다.
• 하지만 입력 값의 범위가 넓어도 해당 범위의 값을 모두 다 입력하는 것은 아니다.
• 앞의 예에서 0 ~ 99 범위의 값 중에 1, 2, 5, 8, 14, 99만 입력했다. 따라서 대부분의 공간은 낭비되었다.

공간도 절약하면서, 넓은 범위의 값을 사용할 수 있는 방법이 있는데, 바로 나머지 연산을 사용하는 것이다. 저장할 수 있는 배열의 크기를 10이라고 가정하자.

나머지 연산

• 1 % 10 = 1
• 2 % 10 = 2
• 5 % 10 = 5
• 8 % 10 = 8
• 14 % 10 = 4
• 99 % 10 = 9

• 여기서 14, 99는 10보다 큰 값이다. 따라서, 일반적인 방법으로는 크기가 10인 배열의 인덱스로 사용할 수 없다.
• 하지만, 나머지 연산의 결과를 사용하면 14는 4로, 99는 9로 크기가 10인 배열의 인덱스로 활용할 수 있다.
• 나머지 연산의 결과는 절대로 배열의 크기를 넘지 않는다. 따라서, 연산 결과는 배열의 크기를 넘지 않으므로 안전하게 인덱스로 사용할 수 있다.

해시 인덱스

• 이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스라 한다.
  • 14의 해시 인덱스는 4, 99의 해시 인덱스는 9이다.
• 이렇게 나머지 연산을 통해 해시 인덱스를 구하고, 해시 인덱스를 배열의 인덱스로 사용해보자.

해시 인덱스와 데이터 저장
1, 2, 5, 8, 14, 99의 값을 크기가 10인 배열에 저장해보자.

• 저장할 값에 나머지 연산자를 사용해서 해시 인덱스를 구한다.
• 해시 인덱스를 배열의 인덱스로 사용해서 데이터를 저장한다.
  예) inputArray[hashIndex] = value
  • 인덱스만 해시 인덱스를 사용하고, 값은 원래 값을 저장한다.
• 배열의 인덱스를 사용하기 때문에 하나의 값을 저장하는데 O(1) 로 빠른 성능을 제공한다.
  • 해시 인덱스 생성 O(1) +해시 인덱스 사용해 배열에 값 저장 O(1) -> O(1)

정리

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

한계(중요!)

• 그런데 지금까지 설명한 내용은 저장할 위치가 충돌할 수 있다는 한계가 있다.
• 예를 들어 1, 11의 두 값은 이렇게 10으로 나누면 같은 값 1이 된다. 둘다 같은 해시 인덱스가 나와버리는 것이다.

5. 해시 알고리즘5 - 해시 충돌 설명

해시 충돌

99, 9의 두 값은 10으로 나누면 9가 된다. 따라서, 다른 값을 입력했지만 같은 해시 코드가 나오게 되는데 이것을 해시 충돌이라 한다.

• 99%10 = 9
• 9%10 = 9

해시 충돌 해결

• 해시 충돌을 인정하면 문제 해결의 실마리가 보인다.
• 해시 충돌은 낮은 확률로 일어날 수 있다고 가정하는 것이다.
• 해결 방안은 바로 해시 충돌이 일어났을 때 단순하게 해시 인덱스의 값을 같은 인덱스에 함께 저장해버리는 것이다.

해시 충돌과 저장

• 물론 여러 데이터를 배열의 하나의 공간에 함께 저장할 수는 없다.
• 대신에 배열 안에 배열을 만들면 된다.
• 물론 배열 안에 리스트 같은 다른 자료구조를 사용해도 된다.

해시 충돌과 조회
해시 충돌이 난 경우 내부의 데이터를 하나씩 비교해보면 원하는 결과를 찾을 수 있다. 예를 들어, 99를 조회한다고 가정해보자.

• 9의 해시 인덱스는 9이다. 배열에서 9번 인덱스를 찾는다.
• 배열 안에는 또 배열이 들어있다. 여기에 있는 모든 값을 검색할 값과 하나씩 비교한다.
  • [99,9]의 데이터가 들어있다. 첫 비교에서 99 equals 9 는 거짓이므로 실패한다. 다음 비교에서 9 equals 9 이므로 원하는 데이터를 찾았다.
  • 비교시 equals 를 사용했지만 기본형이라면 물론 == 을 사용해도 된다.

해시 조회 최악의 경우

• 값을 9,19,29,99만 저장한다고 가정해보자. 이 경우 모든 해시 인덱스가 9가 된다.
• 따라서 9번 인덱스에 데이터가 모두 저장된다.
• 이렇게 되면 데이터를 찾을 때 결국 9번에 가서 저장한 데이터의 수만큼 값을 반복해서 비교해야 한다.
• 따라서, 최악의 경우 O(n)의 성능을 보인다.

정리

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

6. 해시 알고리즘6 - 해시 충돌 구현

해시 충돌 상황까지 고려해서 코드를 구현해보자.

• buckets 이라는 바구니를 추가해서 구분하였음

public class HashStart5 {

    static final int CAPACITY = 10;

    public static void main(String[] args) {
        //{1, 2, 5, 8, 14, 99 ,9}
        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("buckets.contains(" + searchValue + ") = " +
                contains);
    }

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

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

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

실행 결과

buckets = [[], [1], [2], [], [14], [5], [], [], [8], [99, 9]]
bucket.contains(9) = true

해시 인덱스 충돌 확률

• 해시 충돌이 발생하면 데이터를 추가하거나 조회할 때, 연결 리스트 내부에서 O(n) 의 추가 연산을 해야 하므로 성능이 떨어진다.
• 따라서, 해시 충돌은 가급적 발생하지 않도록 해야 한다.
• 해시 충돌이 발생할 확률은 입력하는 데이터의 수와 배열의 크기와 관련이 있다. 입력하는 데이터의 수와 비교해서 배열의 크기가 클수록 충돌 확률은 낮아진다.

정리
해시 인덱스를 사용하는 경우

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

해시 인덱스를 사용하는 방식은 사실 최악의 경우는 거의 발생하지 않는다. 배열의 크기만 적절하게 잡아주면 대부분 O(1) 에 가까운 매우 빠른 성능을 보여준다.

번외) 해시 충돌 처리

1. 체이닝으로 처리하기

체이닝은 해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법입니다. 체이닝은 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결합니다.

그림을 보면 키 B와 C를 해싱했을 때 3입니다. 즉, 해시 테이블의 같은 위치를 가리키므로 데이터를 저장할 때 충돌이 발생합니다. 이때, 체이닝은 링크드리스트로 충돌한 데이터를 연결하는 방식으로 충돌을 해결합니다. 이후, 어떤 데이터가 해시 테이블 상 같은 위치에 저장되어야 하며 이런 방식으로 데이터를 저장합니다.

체이닝의 단점

• 해시 테이블 공간 활용성이 떨어짐 : 충돌이 많아지면 그만큼 링크드리스트의 길이가 길어지고, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어짐.

검색 성능이 떨어짐

• 충돌이 많으면 링크드리스트 자체의 한계 때문에 검색 성능이 떨어짐. 링크드리스트로 연결한 값을 찾으려면 링크드리스트의 맨 앞 데이터부터 검색해야 하기 때문.

참고로 자바에서 HashMap 클래스는 체이닝을 사용해서 해시 충돌을 처리합니다. 다만, 충돌 발생 시 데이터 접근 시간 복잡도가 O(N) 으로 늘어나는 문제가 있으므로 링크드리스트로 연결하는 데이터가 일정 개수가 넘어가면 자동으로 해당 링크드리스트를 이진 탐색 트리로 변환하여 데이터 접근에 O(logN)의 성능이 나오도록 개선합니다.

2. 개방 주소법으로 처리하기(open addressing)

체이닝에서 링크드리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입합니다. 이 방법은 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용합니다.

2-1. 선형 탐사 방식

선형 탐사 방식은 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동합니다. 하지만, 충돌 발생 시 1칸씩 이동하며 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 생깁니다. 이를 클러스터를 형성한다고 합니다. 이런 군집이 생기면 해시값은 겹칠 확률이 더 올라갑니다.

2-2. 이중 해싱 방식
이중 해싱 방식은 말 그대로 해시 함수를 2개 사용합니다. 때에 따라 해시 함수를 N개로 늘리기도 합니다. 두 번째 해시 함수의 역할은 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 합니다.