[F-Lab 모각코 챌린지 4일차] 제네릭, 컬렉션

everydeveloper 2023. 5. 15. 20:46

오늘의 학습 목표

제네릭
- Java Generic (키워드: 타입 파라미터, wildcard, type erasure, 장/단점, etc)
- Java Collection (키워드: Set, Map, List, Synchronized*, Concurrent*, etc)
- Thread Safety (키워드: lock, synchronized, deadlock, ThreadLocal, etc)
- Static, Final (키워드: 사용이유, 장단점, etc)

제네릭

제네릭 코드 간단한 예시

class MyArray<T> {

    T element;

    void setElement(T element) { this.element = element; }

    T getElement() { return element; }

}

위 코드에 대해

간단한 코드 설명이다.

class MyArray<T>

이 줄은 MyArray라는 이름의 클래스를 정의하고 있습니다. <T>는 제네릭 타입을 나타내며, 이 클래스를 사용할 때 실제 데이터 타입으로 대체됩니다. 예를 들어, MyArray<Integer>라고 사용하면, 이 클래스 내의 모든 T는 Integer로 치환됩니다.

T element

이 줄은 제네릭 타입 T의 element라는 이름의 멤버 변수를 선언합니다. 이 변수는 MyArray 클래스의 인스턴스마다 각각 존재하며, 클래스 외부에서는 접근이 불가능한 private 상태일 것으로 보입니다.

void setElement(T element) { this.element = element; }

이 줄은 setElement라는 메소드를 정의하고 있습니다. 이 메소드는 제네릭 타입 T의 매개변수를 받아서, 이를 이 클래스의 element 변수에 저장합니다. 즉, 이 메소드를 통해 element 변수의 값을 변경할 수 있습니다.

T getElement() { return element; }

이 줄은 getElement라는 메소드를 정의하고 있습니다. 이 메소드는 매개변수를 받지 않고, 현재 element 변수의 값을 반환합니다. 이 메소드를 통해 element 변수의 값을 얻을 수 있습니다.

나는 다른 것은 읽어보니 이해가 많이 안 되는 것은 없었는데

<T>부분이 (T)가 아니라 <>인게 많이 궁금하고 이해가 되지 않아서 다른 부분으로 넘어가지지가 않았다.

처음 찾아본 곳에서는 <T>라고 명시 되어 있었긴 했지만 <>인 이유에 대해선 딱히 언급이 없었기 떄문이다.

소괄호()은 주로 메소드의 매개변수를 선언 할 때 사용되는 괄호이고

<> 꺽쇠 괄호는 제네릭 타입을 구분하기 위한 Java 문법이라고 한다.

그리고 여기 안에 들어가는 기호는 타입 변수로 부르며, 실제 타입으로 치환되게 된다.

제네릭의 특징으로는

타입 안정성

코드 재사용성이 있었다.

타입 안정성이라는 말은 안정성이 그냥 타입을 Int a =0; 이런 경우와는 달리

제네릭 타입으로 실제 타입 전에 입력되어야 하는 타입이 명시 되어져 있는 경우에 해당되는 경우인데

이 타입은 Int 타입이나 String 타입만 써야한다고 명시 했을 경우, 이와 다른 타입이 사용되면 에러가 발생된다.

미명시나, 그냥 T,K등으로만 명시되어져 있는 경우에는 안정성이 올라간다고 말할 수 없다.

어떤 경우에도 입력, 대입 되는 타입으로 컴파일 될 것이기 때문이다.

한 제네릭 타입에 2가지 타입이 입력되는 경우도 그냥 제네릭이 아닌 일반 타입 선언과는 안정성에 대해 더 좋다고 말하기는 어려울 것 같다.

애초에 한 int 에 int 타입에 String이 입력되는 건 제네릭이 아니더라고 기본 타입 대입 원리에 어긋나기 때문이다.

코드 재사용성은

한 제네릭에 컴파일이 될 때 그 때 타입이 정해지는 것이므로

컴파일 전에 입력되는 타입이 바뀐다면 이후 타입은 그 타입으로 되는 것이다.

같은 원본 소스에 제네릭 타입이 있다고 한다면, 여러 타입별로 컴파일 하면

여러 결과 프로젝트 .class 파일이 존재 하는 것이다.

위 경우에도 한 타입만 입력되거나 선언한다면, 여러 타입으로 된 컴파일 결과는 나오지 않을 것이다.

이것 외에도

타입소거, 제한된 와일드카드, 제네릭 메서드 등이 있다.

타입 소거(Type Erasure): Java의 제네릭은 컴파일 타임에만 존재하고, 런타임에는 제네릭 정보가 사라집니다. 이를 타입 소거라고 합니다. 이는 Java가 하위 버전과의 호환성을 유지하려는 결과물입니다. 이로 인해 런타임에는 제네릭 타입의 실제 정보를 알 수 없게 됩니다.

제한된 와일드카드(Limited Wildcards): 제네릭에서는 와일드카드를 사용하여 더 유연한 타입 매칭을 가능하게 합니다. 예를 들어, List<?>는 모든 타입의 리스트와 호환되며, List<? extends Number>는 Number 클래스나 그 하위 클래스의 인스턴스를 요소로 가지는 리스트와 호환됩니다.

제네릭 메서드(Generic Methods): 제네릭은 클래스 뿐만 아니라 메서드에서도 사용될 수 있습니다. 이를 제네릭 메서드라고 합니다. 제네릭 메서드를 사용하면 메서드 내부에서도 타입 안정성을 보장하면서 다양한 타입에 대응할 수 있습니다.

public class GenericMethodExample {
    public <T> void printArray(T[] array) {
        for(T element : array) {
            System.out.println(element);
        }
    }
}

여기서 T[] array는 제네릭 타입 T의 배열이다.

GTP의 답변:

여기서 T는 제네릭 타입 파라미터로, 실제 타입은 메서드가 호출될 때 결정됩니다. 예를 들어, Integer[]나 String[]같은 특정 타입의 배열을 printArray 메서드에 전달하면, T는 각각 Integer와 String으로 결정되어 해당 타입의 배열을 처리하게 됩니다.

따라서 T[] array는 Integer[] array, String[] array 등 어떤 타입의 배열도 될 수 있습니다. 이것이 제네릭 메서드의 유연성을 보여주는 좋은 예시입니다

나는 어레이니까 한번은 int타입 한번은 String 타입 등 여러가지 타입의 값을 한번에 한 어레이에 저장 할 수 있으면 좋겠다고 생각했고

일반 어레이는 안되는 걸로 알고 있었지만 제네릭은 될련가 말련가 개념이 약간 햇갈렸는데

한 어레이는 한 타입만 되고 컴파일 시에는 다른 타입으로 컴파일이 될 수도 있다고 알게 되었다.

제한된 와일드카드라는 특징에서 더 유연한 타입 매칭을 가능하게 한다고 해서 의미가 잘 이해가 안되었다.

명확해진다고는 하면 이해가 되었겠지만 더 유연하다고 해서 의미가 이해가 안되었다.

좀 더 알아보니, 숫자 타입인 경우

Integer, Double 등 숫자 안에서도 다양한 타입이 존재한다.

타입 범위를 개발자가 미리 정해줌으로써 컴파일 때 타입 안정성을 유지하면서도 다양한 상황에 대응하고 타입을 허용하는 범위가 명확해진다.

그리고 타입소거를 통해 컴파일이 되고 난다면 소스파일에는 제네릭이 있어도 이후에는 실행하는 런타임에는 제네릭이 사용되었는지 알 수 없을 정도로 여러 Java버전에서 동작 할 수 있게 해준다.

쉽게 말하면 제네릭 버전이 나온 JDK 버전 컴파일파일의 내용과 나오기 이전 컴파일파일 내용이 같은 파일이 된다고 이해하면 되는 것 같다. 약간의 차이는 있을 수 있겠지만 나는 같은 파일이 만들어진다고 이해하였다.

일반적 타입 소거 과정이라고 한다.

타입 소거 과정에서 컴파일러는 다음과 같은 처리를 수행합니다:

제네릭 타입을 경계(bound) 또는 Object로 대체합니다. 예를 들어, List<T>는 List가 되며, T는 Object로 대체됩니다. 제네릭 타입에 경계가 지정된 경우(예: T extends Number), 경계가 사용됩니다.
타입 체크와 타입 변환을 삽입합니다. 이를 통해 타입 안정성이 유지됩니다. 예를 들어, List<String>에 대한 add 호출 시, 컴파일러는 해당 요소가 String인지 확인하는 체크를 삽입합니다.
필요한 경우, 타입 관련 정보를 가진 브리지 메서드를 생성합니다. 이는 서브클래스와 슈퍼클래스 간에 메서드 시그니처가 일관성을 유지하도록 돕습니다.

추가적으로 약간 했갈렸던 개념정리

타입 파라미터와 제네릭 타입

제네릭 타입과 타입 파라미터는 제네릭 프로그래밍에서 사용되는 서로 다른 개념입니다.

제네릭 타입은 타입을 파라미터로 가질 수 있는 클래스나 인터페이스를 의미합니다. 예를 들어, List<E>나 Map<K,V>와 같은 클래스들은 제네릭 타입입니다. 이들은 타입 파라미터 E, K, V를 갖습니다.
타입 파라미터는 실제 타입 대신에 코드를 작성하는 곳에서 사용되는, 실제 타입으로 대체될 수 있는 '자리표시자'입니다. 예를 들어, List<E>에서 E는 타입 파라미터입니다.

따라서, 제네릭 타입은 타입 파라미터를 가지며, 타입 파라미터는 제네릭 타입이나 제네릭 메서드에서 사용됩니다. 이 둘은 제네릭 프로그래밍에서 서로 연관되어 있지만, 서로 다른 개념입니다.

장점만 있는 줄 알았는데 단점도 있었다.

복잡성(Complexity): 제네릭을 이해하고 올바르게 사용하는 것은 초기 학습 곡선이 높을 수 있습니다. 특히 와일드카드나 제한된 타입 파라미터 등의 고급 기능은 더욱 복잡할 수 있습니다.
타입 소거(Type Erasure): Java의 제네릭은 타입 소거 방식으로 구현되었습니다. 이는 런타임에 제네릭 타입 정보가 사라지므로, 런타임에 특정 객체가 특정 제네릭 타입인지 판단할 수 없다는 단점이 있습니다.
제한적인 표현력(Limited Expressiveness): Java의 제네릭은 일부 제약 사항을 가지고 있습니다. 예를 들어, static 필드는 제네릭 타입을 가질 수 없습니다. 또한, 배열 생성 시에도 제네릭 타입을 사용할 수 없습니다. 이러한 제약 사항들은 때때로 불편함을 초래할 수 있습니다.

컬렉션(Collection)

컬렉션 인터페이스

List: 순서가 있는 컬렉션으로, 중복된 요소를 허용합니다. 가장 대표적인 구현체로는 ArrayList, LinkedList 등이 있습니다.
Set: 중복된 요소를 허용하지 않는 컬렉션입니다. 순서가 보장되지 않습니다. 가장 대표적인 구현체로는 HashSet, LinkedHashSet, TreeSet 등이 있습니다.
Map: 키-값 쌍을 저장하는 컬렉션입니다. 키는 중복될 수 없지만, 값은 중복될 수 있습니다. 가장 대표적인 구현체로는 HashMap, LinkedHashMap, TreeMap 등이 있습니다.
Queue/Deque: 요소들이 추가되고 제거되는 순서에 따라 관리되는 컬렉션입니다. 일반적으로 FIFO (First-In-First-Out) 방식을 따르지만, Deque(덱)는 양쪽 끝에서 추가 및 제거가 가능한 LIFO(Last-In-First-Out) 방식도 사용할 수 있습니다. 가장 대표적인 구현체로는 LinkedList, PriorityQueue 등이 있습니다.
Stack: LIFO(Last-In-First-Out) 방식으로 요소를 추가하고 제거하는 컬렉션입니다. 가장 최근에 추가된 요소가 가장 먼저 제거됩니다. Java의 Stack 클래스가 있으나, 보통은 Deque 인터페이스의 LinkedList 등을 스택으로 사용합니다.

List 구현체

ArrayList: 가장 일반적으로 사용되는 List 구현체입니다. 내부적으로 배열을 사용하여 요소를 저장하므로, 인덱스를 통한 요소 접근이 빠릅니다. 그러나 요소가 중간에 추가되거나 삭제되는 경우, 배열을 재구성해야 하므로 속도가 느려질 수 있습니다. 또한, 크기를 동적으로 늘리기 위해 더 큰 배열을 생성하고 기존 요소를 복사하는 리사이징 연산이 필요할 수 있습니다.
LinkedList: 이중 연결 리스트를 사용하여 요소를 저장합니다. 각 요소는 이전 요소와 다음 요소에 대한 참조를 가집니다. 이로 인해 요소의 추가 및 삭제가 빠르지만, 인덱스를 통한 접근이 상대적으로 느립니다. 특히 목록의 끝으로 갈수록 접근 시간이 증가합니다.
Vector: ArrayList와 유사하게 동작하지만, 동기화된(synchronized) 메서드를 사용하여 스레드 안전성을 제공합니다. 그러나 이로 인해 ArrayList에 비해 성능이 떨어질 수 있습니다. 현대의 Java 프로그래밍에서는 대부분의 경우 명시적인 동기화 없이도 스레드 안전성을 달성할 수 있으므로, Vector보다는 ArrayList를 선호하는 추세입니다.

Set 구현체

HashSet: 가장 일반적으로 사용되는 Set 구현체입니다. 내부적으로 해시 테이블을 사용하여 요소를 저장하므로, 요소의 추가, 삭제, 검색이 일반적으로 상수 시간에 이루어집니다. 그러나 해시 충돌이 발생하는 경우 이 성능이 보장되지 않습니다. 또한 요소의 순서는 유지되지 않습니다.
LinkedHashSet: HashSet에 연결 리스트가 추가된 형태입니다. 이로 인해 요소의 삽입 순서가 유지됩니다. HashSet에 비해 약간의 오버헤드가 발생하지만, 순서가 중요한 상황에서는 유용하게 사용될 수 있습니다.
TreeSet: 레드-블랙 트리(Red-Black Tree)라는 자가 균형 이진 검색 트리를 사용하여 요소를 저장합니다. 이로 인해 요소가 자동으로 정렬됩니다. 요소의 추가, 삭제, 검색이 로그 시간에 이루어집니다.

Map 구현체

HashMap: 가장 일반적으로 사용되는 Map 구현체입니다. 내부적으로 해시 테이블을 사용하여 키-값 쌍을 저장하므로, 키의 추가, 삭제, 검색이 일반적으로 상수 시간에 이루어집니다. 그러나 해시 충돌이 발생하는 경우 이 성능이 보장되지 않습니다. 또한 키-값 쌍의 순서는 유지되지 않습니다.
LinkedHashMap: HashMap에 연결 리스트가 추가된 형태입니다. 이로 인해 키-값 쌍의 삽입 순서가 유지됩니다. HashMap에 비해 약간의 오버헤드가 발생하지만, 순서가 중요한 상황에서는 유용하게 사용될 수 있습니다.
TreeMap: 레드-블랙 트리(Red-Black Tree)라는 자가 균형 이진 검색 트리를 사용하여 키-값 쌍을 저장합니다. 이로 인해 키가 자동으로 정렬됩니다. 키의 추가, 삭제, 검색이 로그 시간에 이루어집니다.
Hashtable: HashMap과 유사하게 동작하지만, 동기화된(synchronized) 메서드를 사용하여 스레드 안전성을 제공합니다. 그러나 이로 인해 HashMap에 비해 성능이 떨어질 수 있습니다. 현대의 Java 프로그래밍에서는 대부분의 경우 명시적인 동기화 없이도 스레드 안전성을 달성할 수 있으므로, Hashtable보다는 HashMap을 선호하는 추세입니다.

Queue / Deque 인터페이스 구현체

LinkedList: Queue와 Deque 인터페이스를 모두 구현하는 가장 흔한 클래스입니다. 이중 연결 리스트를 기반으로 하며, 리스트의 앞 또는 뒤에서 요소를 추가하거나 제거하는 데 효율적입니다.
ArrayDeque: Deque 인터페이스를 구현하는 클래스로, 고정된 크기의 배열을 사용하여 요소를 저장합니다. 배열의 앞과 뒤에서 요소를 추가하거나 제거하는 연산이 상수 시간에 이루어집니다. 그러나 크기를 동적으로 늘리는 연산이 필요할 수 있습니다.
PriorityQueue: Queue 인터페이스를 구현하는 클래스로, 요소를 우선순위에 따라 정렬합니다. 이 클래스는 힙(Heap)이라는 자료구조를 사용하여 요소를 저장하며, 우선순위에 따라 요소를 추가하거나 제거하는 데 효율적입니다.
ConcurrentLinkedQueue와 ConcurrentLinkedDeque: Queue와 Deque 인터페이스를 각각 구현하는 클래스로, 다중 스레드 환경에서 안전하게 사용할 수 있습니다.

정리 / 생각한 것들

리스트(List)는 읽고 쓰는 속도는 빠르고 배열 길이는 생성할 때 정하므로,저장되는 데이터 갯수를 추가적으로 늘리거나 줄일 수는 없다.

배열(Array)의 특징은 그 반대인 경우로 저장되는 데이터 갯수를 늘이거나 줄일 수 있어서 그 점에 관해선 편리하다고 할 수 있다.

어레이 리스트는 위 2개를 함께 적용한 자료구조로 그로므로 특징도 2가지의 장점이 나타난다. 읽고 쓰는 속도는 리스트와 배열의 사이며 저장길이는 자동으로 변경된다.

얼핏 생각하면 어레이 리스트만 있으면 될 것 같기도 한데 여기 3가지를 환경/경우에 따라 적절하게 취사 선택하는 것이 개발자의 역량이나 몫이라고 할 수 있겠다.

배열, 리스트, 어레이리스트는 또한 멀티스레드 환경의 비안정성이라는 특징을 보여주고 있는데, 설명을 보면

멀티스레드 환경에서는 여러 스레드가 동시에 데이터에 접근하려고 시도할 수 있습니다. 이렇게 동시에 접근하려고 할 때, 데이터의 일관성이나 정확성이 손상될 수 있는 상태를 '비안정성' 혹은 'Race Condition'이라고 합니다. 예를 들어, 두 스레드가 동시에 같은 데이터를 수정하려고 하면 어떤 수정이 먼저 적용되어야 하는지 결정할 수 없게 되는 상황이 발생할 수 있습니다.

이를 해결하기 위해 '동기화'라는 개념을 사용합니다. 동기화는 한 번에 하나의 스레드만이 특정 코드를 실행하도록 보장함으로써 데이터의 일관성을 유지하는 방법입니다.

나는 스레드의 동시성 문제가 발생 할 수 있다고 해서

쓰레드와 관련되어 있으니 쓰레드를 조절할 줄 알았는데 그건 아니고 코드 레벨 수준에서 동시성 안정성을 구현하였다고 한다.

synchronizedList 보다는 java.util.concurrent을 더 추천하는 편이고 세부 구현은 매우 복잡하다고 해서 딱히 더 알아보지는 않았지만

세그먼트라는 개념을 도입해서 해결하는 것으로 알고 있다. 세그먼트로 여러 스레드가 동시에 데이터를 읽거나 쓸 수 있도록 해준다고 한다.

세그먼트는 맵을 여러 구획을 나눈 것을 말하며 각 세그먼트는 잠겨있거나 안잠겨있는 상태다. 안잠겨 있는 상태면 읽거나 쓸 수 있다고 한다. 다른 스레드가 다른 스레드가 이용중인 곳과 같은 곳이나 같은 세그먼트는 잠겨있기 때문에 당연히 사용이 불가능하고 반면 다른 세그먼트는 안 잠겨 있다면 사용 할 수 있겠다. 세그먼트는 그런 원리 인 것으로 보인다.

HashSet은

HashSet은 내부적으로 HashMap을 사용하여 요소를 저장합니다. 즉, 각 요소는 해시 함수에 의해 계산된 위치에 저장됩니다. 이 해시 함수는 요소의 해시코드를 계산하여 그 결과를 사용하여 요소를 저장할 위치를 결정합니다. 이 때문에 HashSet에 저장된 요소들은 입력된 순서와는 관계없이 특정 위치에 저장됩니다.

해시 함수의 목적은 객체를 고유하게 식별할 수 있는 정수 값(해시코드)을 생성하는 것입니다. 두 객체가 같다면(즉, equals 메서드가 true를 반환한다면) 두 객체의 해시코드도 같아야 합니다.

이런 메커니즘을 통해 HashSet은 아래와 같은 특징을 가집니다:

순서 보장 안함: HashSet은 해시 함수에 의해 계산된 위치에 요소를 저장하므로, 입력 순서와는 무관하게 요소가 저장됩니다. 따라서, 순회 순서는 예측할 수 없습니다.
중복 요소 불가능: 같은 요소(즉, equals 메서드가 true를 반환하는 요소)를 HashSet에 두 번 추가하려고 하면, 두 번째 추가는 무시됩니다. 이는 해시 함수가 같은 요소에 대해 같은 해시코드를 반환하므로, 두 번째 추가 시도가 같은 위치에 저장되려 하기 때문입니다.
시간 복잡도: 해시 함수에 의해 계산된 위치에 요소를 저장하므로, 요소의 삽입 및 조회는 일반적으로 상수 시간인 O(1)에 가능합니다. 이는 해시 충돌이 일어나지 않는 경우에 해당하며, 충돌이 발생하면 성능이 저하될 수 있습니다.

그러나 실제로는 해시 충돌이 발생할 수 있고, 이 경우 연결 리스트에 노드가 추가되어 조회 시간이 늘어날 수 있습니다. 이를 해결하기 위해 Java 8부터는 특정 임계값 이상의 노드가 있는 버킷에서는 연결 리스트 대신 레드-블랙 트리를 사용하도록 변경되었는데, 이렇게 하면 최악의 경우 조회 시간이 O(log n)이 됩니다.

해시 맵 이 해시 테이블 자료구조를 이용한다고 해서 다시 알아봤다.

해시 테이블은 효율적인 검색을 위한 자료구조로서, 키를 값에 매핑하는 구조를 가지고 있습니다. 이는 배열이 인덱스를 통해 값을 빠르게 찾는 원리를 확장한 것이라고 볼 수 있습니다. 그러나 배열과는 달리, 해시 테이블은 키가 반드시 정수일 필요가 없습니다.

해시 테이블의 작동 원리는 다음과 같습니다:

해시 함수: 해시 테이블은 키를 배열 인덱스로 변환하는 해시 함수를 사용합니다. 이 함수는 일관성을 가져야 합니다. 즉, 동일한 키를 입력하면 항상 같은 해시 값을 반환해야 합니다. 또한, 서로 다른 키는 가능한 한 서로 다른 해시 값을 반환해야 하지만, 이는 항상 보장되지는 않습니다.
해시 충돌: 두 개 이상의 키가 동일한 해시 값을 가지는 경우, 이를 해시 충돌이라고 합니다. 이런 경우, 해시 테이블은 이 충돌을 관리하는 메커니즘을 가지고 있어야 합니다. 가장 일반적인 방법은 체이닝과 오픈 어드레싱입니다. 체이닝은 같은 버킷에 여러 키-값 쌍을 저장하는 것이고, 오픈 어드레싱은 충돌 발생 시 다른 버킷에 데이터를 저장하는 방식입니다.
버킷: 해시 테이블은 '버킷'이라는 배열을 사용하여 키-값 쌍을 저장합니다. 해시 함수는 키를 이 버킷의 인덱스로 변환합니다. 이렇게 하면 키를 사용하여 값에 빠르게 액세스할 수 있습니다.

해시 테이블의 장점은 키를 이용한 데이터의 검색, 삽입, 삭제가 평균적으로 상수 시간에 가능하다는 점입니다. 그러나 해시 테이블은 메모리를 많이 사용하며, 해시 함수의 선택과 충돌 관리 전략에 따라 성능이 크게 달라질 수 있습니다. 이러한 이유로, 적절한 해시 함수의 선택과 충돌 관리 방식은 해시 테이블 구현에 있어 중요한 요소입니다.

다시 용어를 좀 더 알아보니

체이닝과 오픈 어드레싱은 해시 충돌 해결 방법이다.

체이닝(Chaining): 체이닝은 동일한 해시 값에 대한 항목들을 연결 리스트로 관리하는 방법입니다. 이 방법을 사용하면, 해시 함수가 동일한 값을 반환하는 다른 키들이 있다 해도 각 키-값 쌍은 리스트의 다른 노드에 저장되므로 충돌 문제를 피할 수 있습니다.

체이닝의 장점은 구현이 비교적 간단하다는 것입니다. 또한, 해시 테이블의 크기를 동적으로 조절하는 것이 가능합니다. 하지만 단점으로는 메모리 오버헤드가 생길 수 있으며, 해시 테이블의 특정 버킷이 너무 많은 항목을 가지게 되면 그 버킷에서의 검색 성능이 저하될 수 있습니다.

오픈 어드레싱(Open Addressing): 오픈 어드레싱은 모든 키-값 쌍을 해시 테이블의 버킷에 직접 저장하는 방법입니다. 이때, 하나의 버킷에 이미 키-값 쌍이 저장되어 있고, 다른 키-값 쌍을 저장하려 할 때 해시 충돌이 발생하면, 다른 버킷으로 이동하여 빈 버킷을 찾는 방식으로 충돌을 해결합니다.

오픈 어드레싱의 장점은 추가적인 메모리를 필요로 하지 않는다는 것입니다. 하지만, 단점으로는 해시 테이블의 로드 팩터(load factor, 테이블에 저장된 항목 수 / 테이블의 버킷 수)가 높아질수록 충돌이 자주 발생하며, 이로 인해 성능이 저하될 수 있습니다. 또한 오픈 어드레싱은 해시 테이블의 크기를 동적으로 조절하는 것이 어렵습니다.

두 방식 모두 장단점이 있으므로, 상황에 따라 적절한 방식을 선택하는 것이 중요합니다.

해시 함수

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 해시 테이블에서는 키 값을 이 해시 함수에 넣어서 그 결과값(해시값)을 사용해 키와 연관된 값을 저장하거나 검색하는 데 사용합니다.

해시 함수의 중요성

분포: 좋은 해시 함수는 입력 데이터를 해시 테이블의 전체 버킷에 고르게 분포시키는 특성을 가져야 합니다. 이는 모든 버킷을 효과적으로 사용하며 해시 충돌의 가능성을 최소화하는데 중요합니다.
속도: 해시 함수는 빠르게 실행되어야 합니다. 키를 해시값으로 변환하는 시간이 오래 걸리면 해시 테이블의 전체 성능에 영향을 미칩니다.
결정성: 동일한 입력에 대해 해시 함수는 항상 동일한 출력을 반환해야 합니다. 그렇지 않으면 키를 사용해 값을 검색하는 것이 불가능해집니다.

해시 충돌

해시 충돌이란 서로 다른 두 개의 키가 동일한 해시값을 가지는 경우를 말합니다. 이는 해시 함수의 결과 공간이 제한되어 있기 때문에 불가피하게 발생하는 현상입니다. 충돌은 해시 테이블의 성능을 저하시키며, 해결하지 않으면 데이터의 정확성을 손상시킬 수 있습니다.

해시 함수는 해시 충돌을 최대한 적절하게 일으키지 않는 것이 좋다.

해시 충돌은 해시 코드가 중복되면 발생하는데

해시 코드가 중복되지 않게 복잡한 해시함수 알고리즘을 사용하면

처리 속도가 느려서 해시 테이블이 속도가 느려지게 되고

해시 코드가 중복이 빈번하게 일어나도 해시 충돌 해피 기법을 이용하는 경우에도 이에 따른 단점이 발생할 수 있다.

따라서 데이터량 등 적절한 환경과 조건에 맞는 해시 함수 쓰는 것이 중요한 것 같다.