Dictionary, Comparer, StringComparer

Dictionary

개요

• 딕셔너리는 키(key)와 값(value)의 쌍으로 구성된 컬렉션임.
  • 연관 컬렉션이라고 부르기도 한다.
  • 키 : 탐색용(고유한 ID)
    • C#은 중복된 키를 허용하는 컬렉션이 없다.
• .NET에서는 표준 딕셔너리 인터페이스와 다양한 딕셔너리 클래스를 제공함.

딕셔너리의 주요 특징

• 저장 순서의 정렬 여부
• 위치(인덱스)로 접근 가능 여부
  • 인덱서가 T 형이다.
• 제네릭/비제네릭 지원
• 대규모 데이터에서 검색 속도

주요 딕셔너리 클래스와 성능 특성

클래스 내부 구조 인덱스 접근 메모리(항목당) 임의 삽입 순차 삽입 키 검색

Dictionary<K,V>	해시테이블	불가	22바이트	30ms	30ms	20ms
Hashtable	해시테이블	불가	38바이트	50ms	50ms	30ms
ListDictionary	연결 리스트	불가	36바이트	50,000ms	50,000ms	50,000ms
OrderedDictionary	해시테이블+배열	가능	59바이트	70ms	70ms	40ms
SortedDictionary<K,V>	레드블랙트리	불가	20바이트	130ms	100ms	120ms
SortedList<K,V>	2개 배열	가능	2바이트	3,300ms	30ms	40ms
SortedList	2개 배열	가능	27바이트	4,500ms	100ms	180ms

• 해시테이블 구조 → 정렬이 안된 구조다.
• 보통 Dictionary, SortedDictionary를 주로 사용한다.
  • 선택 기준 : 정렬 된거 안된거다.
  • 정렬 된거 : SortedDictionary / 정렬 안된거 : Dictionary

IDictionary<TKey,TValue> 인터페이스

• 모든 키/값 기반 컬렉션의 표준 프로토콜을 정의함.
• ICollection<T>를 확장하여 키 기반 접근 메서드와 프로퍼티를 추가함.

public interface IDictionary<TKey,TValue> :
    ICollection<KeyValuePair<TKey,TValue>>, IEnumerable
{
    bool ContainsKey(TKey key);
    bool TryGetValue(TKey key, out TValue value);
    void Add(TKey key, TValue value);
    bool Remove(TKey key);
    TValue this[TKey key] { get; set; }  // 메인 인덱서 - 키로 접근
    ICollection<TKey> Keys { get; }      // 키만 반환
    ICollection<TValue> Values { get; }   // 값만 반환
}

• Get은 Key의 값이 없으면 null을 반환하지만, Try는 값이 없으면 false를 반환한다.
• 메인 인덱서의 호출에서 Key가 딕셔너리에 포함이 되어있지 않다면 Add의 작업을 수행하고, 있다면 Value를 교체하는 작업을 한다.

Dictionary<TKey,TValue>와 Hashtable 클래스

• Dictionary는 가장 일반적으로 사용되는 컬렉션 중 하나임.
• 내부적으로 해시테이블 구조를 사용하여 빠른 검색을 지원함.

사용 예제:

var d = new Dictionary<string, int>();

// 항목 추가
d.Add("One", 1);
d["Two"] = 2;     // 키가 없으면 추가
d["Two"] = 22;    // 키가 있으면 업데이트
d["Three"] = 3;

// 값 조회
Console.WriteLine(d["Two"]);              // 출력: 22
Console.WriteLine(d.ContainsKey("One"));  // true (빠른 연산)
Console.WriteLine(d.ContainsValue(3));    // true (느린 연산)

// TryGetValue 사용
int val = 0;
if (!d.TryGetValue("onE", out val))
    Console.WriteLine("No val");  // "No val" (대소문자 구분)

// 세 가지 열거 방법
foreach (KeyValuePair<string, int> kv in d)    // One; 1
    Console.WriteLine(kv.Key + "; " + kv.Value);  // Two; 22
                                                  // Three; 3

foreach (string s in d.Keys)
    Console.Write(s);            // OneTwoThree
Console.WriteLine();

foreach (int i in d.Values)
    Console.Write(i);            // 1223

• KeyValuePair : 단순한 저장용 구조체

대소문자 구분 없는 문자열 키 사용

var d = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

주의사항

• Dictionary와 Hashtable에서는 중복 키를 허용하지 않음.
• Add() 메서드로 이미 존재하는 키를 추가하면 예외가 발생함.
• 인덱서를 사용하면 키가 없을 경우 추가되고, 있을 경우 업데이트됨.

성능 고려사항

• Big-O 표기법으로 키 검색 시간:
  • O(1): Hashtable, Dictionary, OrderedDictionary
  • O(log n): SortedDictionary와 SortedList
  • O(n): ListDictionary (및 List<T> 같은 비딕셔너리 타입)
  • n은 컬렉션의 항목 수임.

내부 동작 원리

해시 기반 딕셔너리

• Dictionary와 Hashtable은 해시테이블 구조를 사용함.
• 키를 해시코드로 변환한 후 내부 버킷에 저장함.
• 해시 충돌이 발생하면 체이닝으로 해결함.

// 해시코드와 버킷 동작 예제
public class CustomKey
{
    public string Value { get; set; }

    public override int GetHashCode()
    {
        // 간단한 해시 함수 구현
        return Value?.GetHashCode() ?? 0;
    }

    public override bool Equals(object obj)
    {
        if (obj is CustomKey other)
            return Value == other.Value;
        return false;
    }
}

var dict = new Dictionary<CustomKey, string>();
dict.Add(new CustomKey { Value = "test" }, "value");

정렬된 딕셔너리 타입들

SortedDictionary<TKey,TValue>

• SortedDictionary는 자동으로 정렬 상태를 유지하는 컬렉션으로 다음과 같은 특징이 있습니다:
• 레드-블랙 트리 구조를 사용하여 구현됨
• 항상 정렬된 상태를 유지하며 트리의 균형을 맞춤
• 삽입과 검색에 O(log n) 시간이 소요됨
• 임의 순서로 데이터를 자주 삽입/삭제하는 경우에 적합함

기본 사용 예제:

var sorted = new SortedDictionary<string, int>();
sorted.Add("zebra", 1);
sorted.Add("ant", 2);
sorted.Add("bear", 3);

foreach (var pair in sorted)
    Console.WriteLine($"{pair.Key}: {pair.Value}");
// 출력:
// ant: 2
// bear: 3
// zebra: 1

활용 예제: 학생 성적 관리 시스템

public class Student
{
    public string Name { get; set; }
    public double Score { get; set; }
}

// 성적별로 정렬된 학생 목록 관리
var studentScores = new SortedDictionary<double, List<Student>>();

// 학생 추가
void AddStudent(Student student)
{
    if (!studentScores.ContainsKey(student.Score))
        studentScores[student.Score] = new List<Student>();

    studentScores[student.Score].Add(student);
}

// 사용 예
AddStudent(new Student { Name = "Alice", Score = 95.5 });
AddStudent(new Student { Name = "Bob", Score = 89.0 });
AddStudent(new Student { Name = "Charlie", Score = 95.5 });

// 상위 성적부터 학생 출력
foreach (var scoreGroup in studentScores.Reverse())
{
    Console.WriteLine($"Score {scoreGroup.Key}:");
    foreach (var student in scoreGroup.Value)
        Console.WriteLine($"  - {student.Name}");
}

// 출력:
// Score 95.5:
//   - Alice
//   - Charlie
// Score 89.0:
//   - Bob

딕셔너리 선택 가이드

상황에 따른 최적의 딕셔너리 선택:

• 일반적인 키-값 저장
  • Dictionary<TKey,TValue>: 가장 균형 잡힌 성능을 제공함.
• 정렬된 데이터가 필요한 경우
  • SortedDictionary<TKey,TValue>: 동적 데이터에 적합함.
  • SortedList<TKey,TValue>: 데이터가 거의 변경되지 않을 때 적합함.
• 메모리가 제한적인 경우
  • SortedList<TKey,TValue>: 가장 적은 메모리를 사용함.
• 위치 기반 접근이 필요한 경우
  • OrderedDictionary 또는 SortedList: 인덱스로 접근 가능함.
• 아주 작은 컬렉션(10개 미만)
  • ListDictionary: 오버헤드가 적음.

모범 사례와 주의사항

• 딕셔너리 크기를 미리 알 수 있다면 생성자에서 용량을 지정하여 재할당을 방지함.

var dict = new Dictionary<string, int>(1000); // 초기 용량 지정

• 커스텀 키 타입을 사용할 때는 GetHashCode와 Equals를 올바르게 구현해야 함.
  • 커스텀 키 타입 : 내가 만든 클래스를 키 타입으로 사용하는것이다.
• 스레드 안전성이 필요한 경우 ConcurrentDictionary를 사용함.
• 키가 null이 될 수 있는 경우 이를 명시적으로 처리해야 함.
  • 키에 참조형이 오는 경우다.

커스터마이징 가능한 컬렉션과 프록시

커스터마이징 가능한 컬렉션의 개념

기본 개념

• System.Collections.ObjectModel 네임스페이스에서 제공됨
• 프록시(Proxy) 또는 래퍼(Wrapper)로 동작하며 IList<T> 또는 IDictionary<,>를 구현함
• 각 Add, Remove, Clear 작업은 가상 메서드를 통해 라우팅됨

필요성

• 아이템 추가/제거 시 이벤트 발생이 필요한 경우
• 추가/제거된 아이템으로 인한 속성 업데이트가 필요한 경우
• 비즈니스 규칙을 위반하는 추가/제거 작업 감지가 필요한 경우
• Windows Forms의 컨트롤 컬렉션과 같이 공개적으로 노출되는 컬렉션을 구현할 때 사용됨

Collection<T> 클래스

기본 특징

• List<T>의 커스터마이징 가능한 래퍼로 동작함
• IList<T>와 IList를 구현함
• 기존 IList<T>를 생성자에 전달하여 프록시로 사용 가능함

주요 메서드와 속성

public class Collection<T> : IList<T>, ICollection<T>, IEnumerable<T>
{
    // 컬렉션의 모든 항목을 제거할 때 호출됨
    protected virtual void ClearItems();

    // 지정된 인덱스에 항목을 삽입할 때 호출됨
    protected virtual void InsertItem(int index, T item);

    // 지정된 인덱스의 항목을 제거할 때 호출됨
    protected virtual void RemoveItem(int index);

    // 지정된 인덱스의 항목을 설정할 때 호출됨
    protected virtual void SetItem(int index, T item);

    // 내부 리스트에 직접 접근할 때 사용됨
    protected IList<T> Items { get; }
}

기본 사용 예제

// 사용 예시
Zoo zoo = new Zoo();
zoo.Animals.Add(new Animal("Kangaroo", 10));
zoo.Animals.Add(new Animal("Mr Sea Lion", 20));
foreach (Animal a in zoo.Animals)
    Console.WriteLine(a.Name);

// Animal 클래스 정의
public class Animal
{
    public string Name;
    public int Popularity;
    public Animal(string name, int popularity)
    {
        Name = name;
        Popularity = popularity;
    }
}

// AnimalCollection 클래스 정의
public class AnimalCollection : Collection<Animal>
{
    // `Collection<T>`는 이미 완전한 기능을 갖춘 Animal 리스트임
    // 추가 코드가 필요하지 않음
}

// Zoo 클래스에서 AnimalCollection 사용
public class Zoo
{
    public readonly AnimalCollection Animals = new AnimalCollection();
}

확장된 기능 예제

public class Animal
{
    public string Name;
    public int Popularity;
    public Zoo Zoo { get; internal set; } // Zoo 참조 추가

    public Animal(string name, int popularity)
    {
        Name = name;
        Popularity = popularity;
    }
}

public class AnimalCollection : Collection<Animal>
{
    Zoo zoo;
    public AnimalCollection(Zoo zoo) { this.zoo = zoo; }

    // 항목이 추가될 때 Zoo 참조 설정
    protected override void InsertItem(int index, Animal item)
    {
        base.InsertItem(index, item);
        item.Zoo = zoo;
    }

    // 항목이 설정될 때 Zoo 참조 설정
    protected override void SetItem(int index, Animal item)
    {
        base.SetItem(index, item);
        item.Zoo = zoo;
    }

    // 항목이 제거될 때 Zoo 참조 제거
    protected override void RemoveItem(int index)
    {
        this[index].Zoo = null;
        base.RemoveItem(index);
    }

    // 모든 항목이 제거될 때 Zoo 참조 제거
    protected override void ClearItems()
    {
        foreach (Animal a in this)
            a.Zoo = null;
        base.ClearItems();
    }
}

public class Zoo
{
    public readonly AnimalCollection Animals;
    public Zoo() { Animals = new AnimalCollection(this); }
}

KeyedCollection<TKey,TItem> 클래스

기본 특징

• Collection<TItem>을 상속받음
• 키를 통한 접근과 리스트 형태의 접근을 모두 지원함
• 내부 아이템에서 키를 추출하여 사용함
• OrderedDictionary와 유사하지만 키/값 쌍 개념이 없음

주요 메서드와 속성

public abstract class KeyedCollection<TKey,TItem> : Collection<TItem>
{
    // 아이템에서 키를 추출하는 추상 메서드
    protected abstract TKey GetKeyForItem(TItem item);

    // 아이템의 키가 변경될 때 호출하는 메서드
    protected void ChangeItemKey(TItem item, TKey newKey);

    // 키를 통한 접근을 위한 인덱서
    public TItem this[TKey key] { get; }

    // 내부 사전에 접근하기 위한 속성
    protected IDictionary<TKey,TItem> Dictionary { get; }
}

확장된 사용 예제

// 사용 예시
Zoo zoo = new Zoo();
zoo.Animals.Add(new Animal("Kangaroo", 10));
zoo.Animals.Add(new Animal("Mr Sea Lion", 20));

// 인덱스로 접근
Console.WriteLine(zoo.Animals[0].Popularity); // 10

// 키(이름)으로 접근
Console.WriteLine(zoo.Animals["Mr Sea Lion"].Popularity); // 20

// 이름 변경 시 자동으로 키가 업데이트됨
zoo.Animals["Kangaroo"].Name = "Mr Roo";
Console.WriteLine(zoo.Animals["Mr Roo"].Popularity); // 10

public class Animal
{
    string name;
    public string Name
    {
        get { return name; }
        set
        {
            if (Zoo != null)
                Zoo.Animals.NotifyNameChange(this, value);
            name = value;
        }
    }
    public int Popularity;
    public Zoo Zoo { get; internal set; }

    public Animal(string name, int popularity)
    {
        Name = name;
        Popularity = popularity;
    }
}

public class AnimalCollection : KeyedCollection<string,Animal>
{
    Zoo zoo;
    public AnimalCollection(Zoo zoo) { this.zoo = zoo; }

    // 이름 변경 시 키 업데이트
    internal void NotifyNameChange(Animal a, string newName)
    {
        this.ChangeItemKey(a, newName);
    }

    // 동물의 이름을 키로 사용
    protected override string GetKeyForItem(Animal item)
    {
        return item.Name;
    }

    // Collection<T>의 가상 메서드들도 구현
    protected override void InsertItem(int index, Animal item)
    {
        base.InsertItem(index, item);
        item.Zoo = zoo;
    }

    protected override void SetItem(int index, Animal item)
    {
        base.SetItem(index, item);
        item.Zoo = zoo;
    }

    protected override void RemoveItem(int index)
    {
        this[index].Zoo = null;
        base.RemoveItem(index);
    }

    protected override void ClearItems()
    {
        foreach (Animal a in this)
            a.Zoo = null;
        base.ClearItems();
    }
}

public class Zoo
{
    public readonly AnimalCollection Animals;
    public Zoo() { Animals = new AnimalCollection(this); }
}

주요 메서드

ReadOnlyCollection<T> 클래스

기본 특징

• 컬렉션의 읽기 전용 뷰를 제공하는 래퍼임
• 내부적으로는 수정 가능하지만 외부에서는 읽기만 가능함
• 입력 컬렉션의 복사본을 만들지 않고 참조를 유지함

사용 예제

// 사용 예시
Test t = new Test();
Console.WriteLine(t.Names.Count); // 0
t.AddInternally();
Console.WriteLine(t.Names.Count); // 1
// t.Names.Add("test"); // 컴파일 에러
// ((IList<string>)t.Names).Add("test"); // 실행시 예외 발생

// 입력 컬렉션 변경이 ReadOnlyCollection에 반영됨
t.AddInternally();
Console.WriteLine(t.Names.Count); // 2

public class Test
{
    List<string> names = new List<string>();
    public ReadOnlyCollection<string> Names { get; private set; }

    public Test()
    {
        Names = new ReadOnlyCollection<string>(names);
    }

    public void AddInternally()
    {
        names.Add("test");
    }
}

• List<string> names = new List<string>(); public ReadOnlyCollection<string> Names { get; private set; } 이렇게 2개로 외부에서는 읽기만 하게끔 만드는것이 대표적인 사용방법이다.

동등성과 순서 비교 플러그인

개요

필요성

• 컬렉션에서 요소의 동등성과 순서를 비교하는 기능이 필요함
• Dictionary나 Hashtable은 키의 해시코드와 동등성 비교가 필요함
• SortedDictionary나 SortedList는 키의 순서 비교가 필요함
• 기본 비교 동작을 수정해야 하는 경우가 있음:
  • 대소문자 구분 없이 문자열 비교
  • 객체의 특정 속성만으로 비교
  • 문화권에 따른 문자열 정렬

플러그인 프로토콜의 장점

• 기존 타입의 코드 수정 없이 새로운 비교 동작 추가 가능
• 상황에 따라 다른 비교 방식 적용 가능
• 비교 불가능한 타입에도 비교 기능 추가 가능

동등성 비교 플러그인

IEqualityComparer와 IEqualityComparer<T>

• 동등성과 해시코드 비교를 위한 인터페이스임
• Dictionary와 Hashtable에서 사용됨
• 제네릭 버전을 사용하면 박싱/언박싱 오버헤드를 피할 수 있음
• Equals와 GetHashCode는 Obejct 클래스에도 있다.
  • 다른 클래스에서 재정의 되어있다면 재정의 된 함수가 호출된다.

public interface IEqualityComparer<T>
{
    bool Equals(T x, T y);            // 두 객체의 동등성 비교
    int GetHashCode(T obj);           // 해시 테이블에서 사용할 해시코드 생성
}

public interface IEqualityComparer    // 비제네릭 버전
{
    bool Equals(object x, object y);
    int GetHashCode(object obj);
}

EqualityComparer<T>.Default

• 타입의 기본 동등성 비교기를 제공함
• IEquatable<T> 구현 여부를 확인하고 최적의 비교 방법을 선택함
• 제네릭 메서드에서 유용하게 사용됨:
• EqualityComparer<T>.Default는 박싱 언박싱을 위해 Equals를 오류 없이 사용하기 위해 사용한다.

static bool Foo<T>(T x, T y)
{
    return EqualityComparer<T>.Default.Equals(x, y);
}

ReferenceEqualityComparer.Instance (.NET 5+)

• 항상 참조 동등성을 적용하는 비교기를 제공함
• 값 타입의 경우 Equals 메서드는 항상 false를 반환함

EqualityComparer 사용 예제

• Customer 클래스에서 이름으로 동등성 비교:

// 고객 정보를 담는 클래스
public class Customer
{
    public string LastName;
    public string FirstName;
    public Customer(string last, string first)
    {
        LastName = last;
        FirstName = first;
    }
}

// 이름 기준으로 고객을 비교하는 비교기
public class LastFirstEqComparer : EqualityComparer<Customer>
{
    // 성과 이름이 모두 같으면 동일한 것으로 판단
    public override bool Equals(Customer x, Customer y)
        => x.LastName == y.LastName && x.FirstName == y.FirstName;

    // 성과 이름을 조합하여 해시코드 생성
    public override int GetHashCode(Customer obj)
        => (obj.LastName + ";" + obj.FirstName).GetHashCode();
}

// 사용 예시
Customer c1 = new Customer("Bloggs", "Joe");
Customer c2 = new Customer("Bloggs", "Joe");

// 기본 비교 - 참조 동등성 사용 - Object의 Equals가 호출된다.
Console.WriteLine(c1 == c2);           // False
Console.WriteLine(c1.Equals(c2));      // False

var d = new Dictionary<Customer, string>();
d[c1] = "Joe";
Console.WriteLine(d.ContainsKey(c2));  // False

// 커스텀 비교기 사용 - 값 동등성 사용
var eqComparer = new LastFirstEqComparer();
var d2 = new Dictionary<Customer, string>(eqComparer);
d2[c1] = "Joe";
Console.WriteLine(d2.ContainsKey(c2)); // True

순서 비교 플러그인

IComparer와 IComparer<T>

• 요소 간의 순서를 비교하기 위한 인터페이스임
• 정렬된 컬렉션에서 사용됨
• Array.Sort() 등의 정렬 메서드에서도 사용됨

public interface IComparer<T>
{
    int Compare(T x, T y);  // x가 y보다 작으면 음수
                           // x가 y와 같으면 0
                           // x가 y보다 크면 양수 반환
}

public interface IComparer
{
    int Compare(object x, object y);
}

Comparer<T> 추상 클래스

• IComparer와 IComparer<T>를 모두 구현함
• 비교기 구현을 단순화함
• Default 속성으로 기본 비교기 제공

Comparer 사용 예제

• 우선순위로 정렬하는 예제:

// 소원을 나타내는 클래스
class Wish
{
    public string Name;     // 소원 내용
    public int Priority;    // 우선순위

    public Wish(string name, int priority)
    {
        Name = name;
        Priority = priority;
    }
}

// 우선순위로 소원을 비교하는 비교기
class PriorityComparer : Comparer<Wish>
{
    public override int Compare(Wish x, Wish y)
    {
        // null 처리는 항상 먼저 해주는 것이 안전함
        if (object.Equals(x, y)) return 0;
        if (x == null) return -1;
        if (y == null) return 1;

        // 우선순위 비교
        return x.Priority.CompareTo(y.Priority);
    }
}

// 사용 예시
var wishList = new List<Wish>();
wishList.Add(new Wish("Peace", 2));
wishList.Add(new Wish("Wealth", 3));
wishList.Add(new Wish("Love", 2));
wishList.Add(new Wish("3 more wishes", 1));

// 우선순위로 정렬
wishList.Sort(new PriorityComparer());
foreach (Wish w in wishList)
    Console.Write(w.Name + " | ");
// 출력: 3 more wishes | Love | Peace | Wealth |

특수 비교기

StringComparer

• 문자열 비교를 위한 특별한 클래스임
• 문화권과 대소문자 구분 옵션 제공
• 다음 정적 속성들을 통해 인스턴스를 얻을 수 있음:
  • CurrentCulture: 현재 문화권 기준 비교
  • CurrentCultureIgnoreCase: 현재 문화권, 대소문자 무시
  • InvariantCulture: 문화권 독립적 비교
  • InvariantCultureIgnoreCase: 문화권 독립적, 대소문자 무시
  • Ordinal: 순수 문자 코드 비교
  • OrdinalIgnoreCase: 순수 문자 코드, 대소문자 무시

// 대소문자 구분 없는 딕셔너리
var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

// 호주 영어 규칙으로 정렬
string[] names = { "Tom", "HARRY", "sheila" };
CultureInfo ci = new CultureInfo("en-AU");
Array.Sort<string>(names, StringComparer.Create(ci, false));

// 성 비교기 예제 - 문화권 인식
class SurnameComparer : Comparer<string>
{
    StringComparer strCmp;

    public SurnameComparer(CultureInfo ci)
    {
        // 문화권 특화된 문자열 비교기 생성
        strCmp = StringComparer.Create(ci, false);
    }

    string Normalize(string s)
    {
        s = s.Trim();
        // Mc로 시작하는 성을 Mac으로 정규화
        if (s.ToUpper().StartsWith("MC"))
            s = "MAC" + s.Substring(2);
        return s;
    }

    public override int Compare(string x, string y)
    {
        return strCmp.Compare(Normalize(x), Normalize(y));
    }
}

IStructuralEquatable과 IStructuralComparable

• 구조적 비교를 위한 인터페이스임
• 배열과 같은 복합 타입의 내용 비교에 사용됨
• 각 요소의 비교에 지정된 비교기를 사용함

// 배열의 구조적 동등성 비교
int[] a1 = { 1, 2, 3 };
int[] a2 = { 1, 2, 3 };
IStructuralEquatable se1 = a1;

Console.WriteLine(a1.Equals(a2));  // False (참조 비교)
Console.WriteLine(se1.Equals(a2, EqualityComparer<int>.Default));  // True (구조적 비교)

// 문자열 배열의 대소문자 구분 없는 비교
string[] arr1 = "the quick brown fox".Split();
string[] arr2 = "THE QUICK BROWN FOX".Split();
IStructuralEquatable se2 = arr1;
bool isTrue = se2.Equals(arr2, StringComparer.InvariantCultureIgnoreCase);  // True

성능 고려사항

• 제네릭 비교기를 사용하면 박싱/언박싱 오버헤드를 피할 수 있음
• EqualityComparer<T>.Default는 IEquatable<T> 구현을 활용하여 최적화됨
• 구조적 비교는 요소별 비교가 필요하므로 일반 비교보다 느릴 수 있음
• StringComparer의 Ordinal 비교가 문화권 인식 비교보다 빠름

우선순위 큐

• 큐 : 집어넣은 순서로 나온다.
• 우선순위 큐 : 우선수누이를 같이 넣어서 우선순위가 높은 순서대로 나온다.
  • 넣거나 빼는 동작이 큐와 다르다.
  • 값이랑 짝지은것이 키의 우선순위대로 나오게 된다.
• 기본적인 구현은 성능 무관하게 구현할 수 있다.
  • 전체 순회
• 성능을 고려하면 어렵다.
  • Comparer로 비교해야한다.

이진트리 자료구조

• 연결 리스트 구조로 구현할 수 있다.
• 멤버로 Value, LNext, RNext, Previous가 있어야한다.
• 가로 한줄을 ‘레벨’이락 부른다.

포화 이진트리

• 좌우 빈 노드 없이 전부 연결어있는 구조다.
• 순서는 좌 → 우 순서로 채워져야한다.

최소 힙 트리

• 루트 노드가 최솟값이 되어야하고, 자식 노드의 값이 루트노드의 값보다 커야한다.
• 루트 노드를 제거한다면?
  • 자식 노드 중 가장 마지막 노드를 루트노드로 만들고 좌우 비교해서 하나씩 교체한다.
    • 더이상 비교가 안될때까지