연관 배열

연관 배열 (Associative Arrays)

D 언어의 연관 배열(associative array)은 인덱스가 꼭 정수일 필요가 없고, 빈틈이 있어도 괜찮은 배열 형태예요. 여기서 인덱스를 **키(key)**라고 부르고, 키의 타입을 KeyType이라고 불러요. 이번 글에서는 연관 배열을 선언하는 법부터 키를 넣고 빼고 확인하는 다양한 방법, 그리고 프로퍼티와 연산들을 차근차근 살펴볼게요.

출처: https://dlang.org/spec/hash-map.html

본문

연관 배열은 배열 선언의 [ ] 안에 KeyType을 넣어서 선언해요:

int[string] aa;   // Associative array of ints that are
                  // indexed by string keys.
                  // The KeyType is string.
aa["hello"] = 3;  // set value associated with key "hello" to 3
int value = aa["hello"];  // lookup value from a key
assert(value == 3);

연관 배열의 KeyType과 요소 타입 모두 함수 타입이나 void가 될 수 없어요.

구현 정의(Implementation Defined): 내장 연관 배열은 배열에 삽입된 키의 순서를 보존하지 않아요. 특히 foreach 루프에서 요소가 순회되는 순서는 보통 지정되지 않아요.

Literals (리터럴)

auto aa = [21u: "he", 38: "ho", 2: "hi"];
static assert(is(typeof(aa) == string[uint]));
assert(aa[2] == "hi");

연관 배열 리터럴(Associative Array Literals)을 참고하세요.

Removing Keys (키 제거)

연관 배열에서 특정 키 하나를 없애고 싶으면 remove 함수를 써요:

aa.remove("hello");

remove(key)는 주어진 키가 없으면 아무 일도 하지 않고 false를 돌려줘요. 키가 존재하면 그 키를 AA에서 제거하고 true를 돌려줘요.

모든 키를 한꺼번에 제거하려면 clear 메서드를 쓰면 돼요.

Testing Membership (멤버십 확인)

InExpression은 키가 연관 배열에 있으면 그 값에 대한 포인터를, 없으면 null을 돌려줘요:

int* p;

p = "hello" in aa;
if (p !is null)
{
    *p = 4;  // update value associated with key
    assert(aa["hello"] == 4);
}

정의되지 않은 동작(Undefined Behavior): 반환된 주소가 가리키는 요소의 앞이나 뒤로 포인터를 옮긴 뒤 역참조하는 것은 정의되지 않은 동작이에요.

Using Classes as the KeyType (클래스를 KeyType으로 사용하기)

클래스를 KeyType으로 쓸 수 있어요. 이때 동작은 class Object의 다음 멤버 함수들이 좌우해요:

  • size_t toHash() @trusted nothrow
  • bool opEquals(Object)

opEquals의 매개변수 타입은 정의된 클래스 타입이 아니라 Object라는 점을 주의하세요.

예를 들어:

class Foo
{
    int a, b;

    override size_t toHash() { return a + b; }

    override bool opEquals(Object o)
    {
        Foo foo = cast(Foo) o;
        return foo && a == foo.a && b == foo.b;
    }
}

opEquals의 기본 구현은 비교에 인스턴스의 주소를 사용하고, toHash의 기본 구현은 인스턴스의 주소를 해시해요.

구현 정의: 연관 배열은 동등성 확인에 opCmp를 사용하지 않아요. 다만 실제로 호출되는 opEquals나 opCmp는 런타임에 결정되므로, 컴파일러가 항상 불일치하는 함수를 감지하지는 못해요. 레거시 문제 때문에, 컴파일러는 opCmp는 오버라이드하면서 opEquals는 오버라이드하지 않는 연관 배열 키 타입을 거부할 수 있어요. 이 제한은 향후 버전에서 제거될 수 있어요.

정의되지 않은 동작: opEquals가 true를 반환할 때 toHash는 일관되게 같은 값이어야 해요. 다시 말해 같다고 판정되는 두 객체는 항상 같은 해시 값을 가져야 해요. 그렇지 않으면 정의되지 않은 동작이 발생해요.

모범 사례(Best Practices): toHash와 opEquals 오버라이드에 @safe, @nogc, pure, const, scope 속성을 최대한 사용하세요.

Using Structs or Unions as the KeyType (구조체나 공용체를 KeyType으로 사용하기)

KeyType이 구조체(struct)나 공용체(union) 타입이면, 그 구조체 값의 필드에 기반해 해시와 비교를 계산하는 기본 메커니즘이 사용돼요. 다음 함수들을 구조체 멤버로 제공하면 사용자 정의 메커니즘을 쓸 수 있어요:

size_t toHash() const @safe pure nothrow;
bool opEquals(ref const typeof(this) s) const @safe pure nothrow;

예를 들어:

import std.string;

struct MyString
{
    string str;

    size_t toHash() const @safe pure nothrow
    {
        size_t hash;
        foreach (char c; str)
            hash = (hash * 9) + c;
        return hash;
    }

    bool opEquals(ref const MyString s) const @safe pure nothrow
    {
        return std.string.cmp(this.str, s.str) == 0;
    }
}

함수들은 @safe 대신 @trusted를 써도 돼요.

구현 정의: 연관 배열은 동등성 확인에 opCmp를 사용하지 않아요. 이런 이유와 레거시 이유로, 연관 배열 키는 특수화된 opCmp를 정의하면서 특수화된 opEquals는 생략하는 것이 허용되지 않아요. 이 제한은 향후 버전의 D에서 제거될 수 있어요.

정의되지 않은 동작: opEquals가 true를 반환할 때 toHash는 일관되게 같은 값이어야 해요. 다시 말해 같다고 판정되는 두 구조체는 항상 같은 해시 값을 가져야 해요. 그렇지 않으면 정의되지 않은 동작이 발생해요.

모범 사례: toHash와 opEquals 오버라이드에 @nogc 속성을 최대한 사용하세요.

Construction or Assignment on Setting AA Entries (AA 항목 설정 시 생성 또는 대입)

AA 인덱싱 접근이 대입 연산자의 왼쪽에 오면, 키에 연결된 AA 항목을 설정하는 용도로 특별히 처리돼요.

string[int] aa;
string s;

//s = aa[1];        // throws RangeError in runtime
aa[1] = "hello";    // handled for setting AA entry
s = aa[1];          // succeeds to lookup
assert(s == "hello");

대입되는 값의 타입이 AA 요소 타입과 동등하면:

  1. 인덱스 키가 AA에 아직 없으면 새 AA 항목이 할당되고, 대입된 값으로 초기화돼요.
  2. 인덱스 키가 이미 AA에 있으면, 설정은 일반 대입을 실행해요.
struct S
{
    int val;
    void opAssign(S rhs) { this.val = rhs.val * 2; }
}
S[int] aa;
aa[1] = S(10);  // first setting initializes the entry aa[1]
assert(aa[1].val == 10);
aa[1] = S(10);  // second setting invokes normal assignment, and
                // operator-overloading rewrites it to member opAssign function.
assert(aa[1].val == 20);

대입되는 값의 타입이 AA 요소 타입과 동등하지 않으면, 그 표현식은 일반 인덱싱 접근으로 연산자 오버로딩을 호출하게 돼요:

struct S
{
    int val;
    void opAssign(int v) { this.val = v * 2; }
}
S[int] aa;
aa[1] = 10;     // is rewritten to: aa[1].opAssign(10), and
                // throws RangeError before opAssign is called

하지만 AA 요소 타입이 대입되는 값으로부터 암시적 생성자 호출을 지원하는 구조체라면, AA 항목을 설정할 때 암시적 생성(implicit construction)이 사용돼요:

struct S
{
    int val;
    this(int v) { this.val = v; }
    void opAssign(int v) { this.val = v * 2; }
}
S s = 1;    // OK, rewritten to: S s = S(1);
s = 1;      // OK, rewritten to: s.opAssign(1);

S[int] aa;
aa[1] = 10; // first setting is rewritten to: aa[1] = S(10);
assert(aa[1].val == 10);
aa[1] = 10; // second setting is rewritten to: aa[1].opAssign(10);
assert(aa[1].val == 20);

이 설계는 std.bigint.BigInt 같은 값 의미론(value-semantics)을 가진 일부 구조체에서 메모리를 효율적으로 재사용하기 위한 거예요.

import std.bigint;
BigInt[string] aa;
aa["a"] = 10;   // construct BigInt(10) and move it in AA
aa["a"] = 20;   // call aa["a"].opAssign(20)

Inserting if not present (없으면 삽입하기)

AA에 접근할 때 키에 대응하는 값이 반드시 있어야 한다면, 없을 경우 값을 생성해 삽입해야 해요. require 함수는 지연(lazy) 인자를 통해 새 값을 생성하는 수단을 제공해요. lazy 인자는 키가 없을 때에만 평가돼요. require 연산은 여러 번 키를 조회할 필요를 피하게 해줘요.

class C{}
C[string] aa;

auto a = aa.require("a", new C);   // lookup "a", construct if not present

값이 생성됐는지 이미 존재했는지를 알고 싶을 때도 있어요. require 함수는 값이 생성됐는지 알려주는 bool 매개변수를 제공하지는 않지만, 대신 함수나 델리게이트를 통한 생성을 허용해요. 그래서 아래처럼 어떤 메커니즘이든 자유롭게 쓸 수 있어요.

class C{}
C[string] aa;

bool constructed;
auto a = aa.require("a", { constructed=true; return new C;}());
assert(constructed == true);

C newc;
auto b = aa.require("b", { newc = new C; return newc;}());
assert(b is newc);

Advanced updating (고급 갱신)

보통 연관 배열의 값을 갱신하는 것은 대입문 하나로 간단하게 끝나요.

int[string] aa;

aa["a"] = 3;  // set value associated with key "a" to 3

때로는 값이 이미 존재하는지, 아니면 새로 생성해야 하는지에 따라 다른 작업을 해야 할 때가 있어요. update 함수는 creator로 새 값을 생성하고 updater로 기존 값을 갱신하는 수단을 제공해요. update 연산은 여러 번 키를 조회할 필요를 피하게 해줘요.

int[string] aa;

// create
aa.update("key",
    () => 1,
    (int) {} // not executed
    );
assert(aa["key"] == 1);

// update value by ref
aa.update("key",
    () => 0, // not executed
    (ref int v) {
        v += 1;
    });
assert(aa["key"] == 2);

자세한 내용은 update를 참고하세요.

Runtime Initialization of Immutable AAs (불변 AA의 런타임 초기화)

불변(immutable) 연관 배열이 바람직한 경우가 많지만, 초기화를 런타임에 해야 할 때도 있어요. 이는 생성자(스코프에 따라 정적 생성자), 버퍼 연관 배열, 그리고 assumeUnique로 달성할 수 있어요:

immutable long[string] aa;

shared static this()
{
    import std.exception : assumeUnique;
    import std.conv : to;

    long[string] temp; // mutable buffer
    foreach (i; 0 .. 10)
    {
        temp[to!string(i)] = i;
    }
    temp.rehash; // for faster lookups

    aa = assumeUnique(temp);
}

void main()
{
    assert(aa["1"] == 1);
    assert(aa["5"] == 5);
    assert(aa["9"] == 9);
}

Construction and Reference Semantics (생성과 참조 의미론)

연관 배열은 기본적으로 null이고, 첫 번째 키/값 쌍을 대입할 때 생성돼요. 하지만 한번 생성되면 연관 배열은 참조 의미론(reference semantics)을 가져서, 한 배열을 다른 배열에 대입해도 데이터가 복사되지 않아요. 같은 배열에 대한 여러 참조를 만들려고 할 때 이 점이 특히 중요해요.

int[int] aa;             // defaults to null
int[int] aa2 = aa;       // copies the null reference

assert(aa is null);
aa[1] = 1;
assert(aa2.length == 0); // aa2 still is null
aa2 = aa;
aa2[2] = 2;
assert(aa[2] == 2);      // now both refer to the same instance

NewExpression을 쓰면 키를 삽입할 때가 아니라 즉시 연관 배열 인스턴스를 생성할 수 있어요.

int[string] a = new int[string];
auto b = a; // a and b point to the same AA instance

assert(b !is null);
a["1"] = 1;
assert(b["1"] == 1);

Properties and Operations (속성과 연산)

이름 설명
sizeof 연관 배열에 대한 참조의 크기. 32비트 빌드에서는 4, 64비트 빌드에서는 8이에요.
length 연관 배열에 있는 값의 개수. 동적 배열과 달리 읽기 전용이에요.
dup 연관 배열이 null이면 null을 반환하고, 그렇지 않으면 연관 배열의 키와 값의 복사본을 가진 새로 할당된 연관 배열을 반환해요.
rehash 조회가 더 효율적이도록 연관 배열을 제자리에서 재조직해요. 예를 들어 프로그램이 심볼 테이블을 전부 올린 뒤 빠른 조회가 필요해질 때 rehash를 호출하면 효과적이에요. 재조직된 배열에 대한 참조를 반환해요.
clear 연관 배열에서 모든 키와 값을 제거해요. 기존 저장소를 재사용할 수 있도록 제거 후에도 배열을 재해시하지 않아요. 이는 같은 인스턴스에 대한 모든 참조에 영향을 주며, 현재 참조만 null로 설정하는 destroy(aa)와는 동등하지 않아요.

참고: 내장 empty 속성은 없어요. Phobos는 std.range.primitives에 empty 구현을 제공해요.

Iteration Operations (순회 연산)

연산 설명
keys 연관 배열의 키 복사본을 담은 새로 할당된 동적 배열을 반환해요. 순서는 values()와 일치하지만 그 외에는 지정되지 않아요.
values 연관 배열의 값 복사본을 담은 새로 할당된 동적 배열을 반환해요. 순서는 keys()와 일치하지만 그 외에는 지정되지 않아요.
byKey 키를 참조로 나열하는 전방 범위(forward range)를 반환해요. 순서는 byValue()와 일치하지만 그 외에는 지정되지 않아요. 버그: 키가 변경 가능(mutable)하게 제공되지만, 변경하는 것은 정의되지 않은 동작이에요.
byValue 값을 참조로 나열하는 전방 범위를 반환해요. 순서는 byKey()와 일치하지만 그 외에는 지정되지 않아요.
byKeyValue key와 value 속성을 제공하는 불투명 객체들을 나열하는 전방 범위를 반환해요. 이 속성들은 결과를 참조로 반환해요. 요소의 순서는 지정되지 않아요. 버그: 키가 변경 가능하게 제공되지만, 변경하는 것은 정의되지 않은 동작이에요.

keys()와 values(), 그리고 byKey(), byValue(), byKeyValue()가 반환하는 키와 값의 순서는 지정되지 않지만, 연관 배열이 재조직되지 않는 동안에는 일관성이 보장돼요. 예를 들어 호출 사이에 키를 추가하거나 제거하지 않았다면요. 기존 키에 새 값을 연결하는 것은 연관 배열을 재조직하지 않아요. 연관 배열을 재조직하면 byKey(), byValue(), byKeyValue()가 반환한 입력 범위들은 무효화돼요.

모범 사례:

  • keys()와 values()를 호출하면 할당이 발생해요(연관 배열이 null이거나 비어 있지 않다면). 키나 값의 독립된 복사본이 필요할 때만 사용하고, 그렇지 않으면 byKey()와 byValue()를 고려하세요.
  • 연관 배열은 값 순회와 키-값 순회를 위해 foreach를 직접 지원해요. 불필요한 복사본을 피하려면 필요할 때 키와 값 변수에 ref를 사용하세요. 키만 순회하려면 키-값 순회를 쓰고 값을 무시하면 돼요. 범위 알고리즘처럼 더 정교한 경우에는 byKey(), byValue(), byKeyValue()를 사용하세요.

Key Lookup Operations (키 조회 연산)

연산 설명
Value get(Key key, lazy Value defVal) 키가 존재하면 해당 값을 반환하고, 그렇지 않으면 defVal을 평가해 반환하되 키와 연결하지는 않아요.
ref Value require(Key key, lazy Value value) 키가 존재하면 해당 값을 참조로 반환하고, 그렇지 않으면 value를 평가해 연관 배열에서 키와 연결한 뒤 새로 저장된 값을 참조로 반환해요.
void update(Key key, Creator creator, Updater updater) 키가 존재하면 해당 값으로 updater를 호출하고, 반환 값이 있으면 그 값을 키와 연결해요. 키를 찾지 못하면 creator를 호출하고 결과를 키와 연결해요.

update 연산은 지정된 대로 호출 가능한(인보크 가능한) 어떤 creator와 updater와도 동작해요. updater는 인자를 참조로 바인딩하면 값을 제자리에서 수정할 수 있어요.

모범 사례: void를 반환하고 ref 매개변수를 가진 updater는 불필요한 복사본을 피해요.

Examples (예제)

Associative Array Example: word count (연관 배열 예제: 단어 수 세기)

too many cooks too many ingredients

import std.algorithm;
import std.stdio;

void main()
{
    ulong[string] dictionary;
    ulong wordCount, lineCount, charCount;

    foreach (line; stdin.byLine(KeepTerminator.yes))
    {
        charCount += line.length;
        foreach (word; splitter(line))
        {
            wordCount += 1;
            if (auto count = word in dictionary)
                *count += 1;
            else
                dictionary[word.idup] = 1;
        }

        lineCount += 1;
    }

    writeln("   lines   words   bytes");
    writefln("%8s%8s%8s", lineCount, wordCount, charCount);

    const char[37] hr = '-';

    writeln(hr);
    foreach (word; sort(dictionary.keys))
    {
        writefln("%3s %s", dictionary[word], word);
    }
}

전체 버전은 wc를 참고하세요.

Associative Array Example: counting pairs (연관 배열 예제: 쌍 세기)

연관 배열은 foreach 문을 사용해 키/값 방식으로 순회할 수 있어요. 예로, 문자열에서 길이 2인 모든 부분 문자열(일명 2-mer)의 등장 횟수를 세어 볼게요:

import std.range : slide;
import std.stdio : writefln;
import std.utf : byCodeUnit; // avoids UTF-8 auto-decoding

int[string] aa;

// The string `arr` has a limited alphabet: {A, C, G, T}
// Thus, for better performance, iteration can be done _without_ decoding
auto arr = "AGATAGA".byCodeUnit;

// iterate over all pairs in the string and count each pair
// ('A', 'G'), ('G', 'A'), ('A', 'T'), ...
foreach (window; arr.slide(2))
    aa[window.source]++; // source unwraps the code unit range

// iterate over all key/value pairs of the Associative Array
foreach (key, value; aa)
{
    writefln("key: %s, value: %d", key, value);
}

> rdmd count.d
key: AT, value: 1
key: GA, value: 2
key: TA, value: 1
key: AG, value: 2

더 알아보기 (Learn more)