연관 배열
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
연관 배열은 각 키에 값을 연결하여 데이터를 저장하는 추상 자료형이다. 연관 배열은 삽입, 제거, 조회 연산을 지원하며, 키-값 쌍을 통해 데이터를 관리한다. 구현 방식에 따라 해시 테이블, 균형 이진 탐색 트리 등을 사용하며, 언어에 따라 딕셔너리, 해시, 맵 등의 이름으로 제공된다. 멀티맵과 양방향 맵과 같은 연관 배열의 일반화된 형태도 존재하며, 데이터를 영구적으로 저장하기 위해 직렬화 또는 데이터베이스를 활용하기도 한다.
연관 배열의 주요 연산은 다음과 같다:[6][7][9][25][26]
연관 배열은 파이썬이나 JSON과 같은 프로그래밍 언어에서 쉽게 표현할 수 있다. 예를 들어, 책 제목과 대출자를 연결하는 연관 배열은 다음과 같이 나타낼 수 있다.
2. 연산
예를 들어, 도서관 대출 정보를 연관 배열로 나타낼 수 있다. 책은 키, 대출자는 값이 된다.
```javascript
{
"Pride and Prejudice": "Alice",
"Wuthering Heights": "Alice",
"Great Expectations": "John"
}
```
"Great Expectations"를 조회하면 "John"이 반환된다. John이 책을 반납하면 삭제 연산이, Pat이 책을 빌리면 삽입 연산이 수행되어 연관 배열은 변경된다.
연관 배열은 매핑 수 결정 또는 모든 매핑을 반복하기 위한 반복자 생성과 같은 다른 연산을 포함할 수도 있다. 이러한 연산의 경우, 매핑이 반환되는 순서는 일반적으로 구현에 따라 정의된다.
멀티맵은 단일 키에 여러 값을 연결할 수 있도록 함으로써 연관 배열을 일반화한다.[8] 양방향 맵은 매핑이 양방향으로 작동하는 관련 추상 데이터 형식이다.
2. 1. 속성
연관 배열의 연산은 다음 속성을 만족해야 한다.[9]
여기서 `k`와 `j`는 키, `v`는 값, `D`는 연관 배열이며, `new()`는 비어있는 연관 배열을 새로 생성한다.
순수 연관 배열에서 키-값 간의 참조는 결합(바인딩)이라고 한다. '결합'이라는 용어는 새로운 참조를 만드는 과정에도 사용된다.
3. 구현
```javascript
{
"Pride and Prejudice": "Alice",
"Wuthering Heights": "Alice",
"Great Expectations": "John"
}
```
위 예시에서 "Great Expectations"라는 키로 검색하면 "John"이라는 값을 얻는다.
연관 배열을 구현하는 대표적인 방법은 다음과 같다.
이 외에도 레딕스 트리, 트라이, 주디 배열, 반 엠데 보아스 트리 등 특정 키 유형에 특화된 자료 구조도 활용할 수 있다.
아래 표는 각 구현 방식의 성능을 비교한 것이다.
| 자료 구조 | 검색/제거 (평균) | 검색/제거 (최악) | 삽입 (평균) | 삽입 (최악) | 정렬 여부 |
|---|---|---|---|---|---|
| 해시 테이블 | O(1) | O(n) | O(1) | O(n) | 아니오 |
| 균형 이진 탐색 트리 | O(log n) | O(log n) | O(log n) | O(log n) | 예 |
| 불균형 이진 탐색 트리 | O(log n) | O(n) | O(log n) | O(n) | 예 |
| 연관 리스트 | O(n) | O(n) | O(1) | O(1) | 아니오 |
3. 1. 해시 테이블 구현
해시 테이블은 배열 자료 구조와 각 키를 배열의 개별 "버킷"으로 분리하는 해시 함수를 결합한 것이다. 해시 테이블의 기본 아이디어는 인덱스를 통해 배열의 요소에 접근하는 것이 간단하고 상수 시간 작업이라는 것이다. 따라서 해시 테이블 작업의 평균 오버헤드는 키의 해시 계산과 배열 내의 해당 버킷에 접근하는 것뿐이다. 따라서 해시 테이블은 일반적으로 O(1) 시간에 수행되며, 대안적인 구현보다 뛰어난 성능을 보인다.[6][7][3]해시 테이블은 해시 충돌(해시 함수에 의해 서로 다른 두 개의 키가 배열의 동일한 버킷으로 매핑되는 것)을 처리할 수 있어야 한다. 이 문제에 대한 가장 널리 사용되는 두 가지 접근 방식은 분리 연결법과 개방 주소 지정법이다.[6][7][3][11] 분리 연결법에서 배열은 값 자체를 저장하지 않고, 해시에 일치하는 모든 값을 저장하는 다른 컨테이너(일반적으로 연관 리스트)에 대한 포인터를 저장한다. 반대로 개방 주소 지정법에서는 해시 충돌이 발견되면 테이블은 일반적으로 배열에서 바로 다음 위치를 확인하여 결정론적 방식으로 값을 저장하기 위해 배열에서 빈 공간을 찾는다.
개방 주소 지정법은 테이블이 대부분 비어 있을 때 분리 연결법보다 낮은 캐시 미스 비율을 갖는다. 그러나 테이블이 더 많은 요소로 채워지면 개방 주소 지정법의 성능이 기하급수적으로 저하된다. 또한, 분리 연결법은 항목이 매우 작은 경우(포인터 크기의 4배 미만)를 제외하고 대부분의 경우 메모리를 덜 사용한다.
| 기반 자료 구조 | 검색 또는 제거 | 삽입 | 정렬 여부 | ||
|---|---|---|---|---|---|
| 평균 | 최악의 경우 | 평균 | 최악의 경우 | ||
| 해시 테이블 | O(1) | O(n) | O(1) | O(n) | |
| 균형 이진 탐색 트리 | O(log n) | O(log n) | O(log n) | O(log n) | |
| 불균형 이진 탐색 트리 | O(log n) | O(n) | O(log n) | O(n) | |
| 속성-값 쌍의 순차적 컨테이너 (예: 연관 리스트) | O(n) | O(n) | O(1) | O(1) |
3. 2. 트리 구현
AVL 트리나 레드-블랙 트리와 같은 균형 이진 탐색 트리를 사용하여 연관 배열을 구현하는 것은 흔한 방식이다.[12]해시 테이블과 비교했을 때, 균형 이진 탐색 트리는 장점과 단점을 모두 가진다. 균형 이진 탐색 트리의 최악의 경우 성능은 빅 오 표기법으로 O(log ''n'')의 시간 복잡도를 가지며, 이는 해시 테이블보다 훨씬 뛰어나다. 해시 테이블은 최악의 경우 모든 요소가 단일 버킷을 공유하여 O(''n'') 시간 복잡도를 갖는다. 또한, 모든 이진 탐색 트리와 마찬가지로 균형 이진 탐색 트리는 요소를 정렬된 상태로 유지한다. 따라서 요소를 순회하면 최소에서 최대 순서로 정렬되지만, 해시 테이블을 순회하면 요소가 무작위 순서로 나타날 수 있다. 정렬된 상태이기 때문에 트리 기반 맵은 범위 쿼리(두 경계 사이의 모든 값 찾기)도 만족할 수 있지만, 해시 맵은 정확한 값만 찾을 수 있다. 그러나 해시 테이블은 균형 이진 탐색 트리보다 평균적인 경우 시간 복잡도가 O(1)로 훨씬 뛰어나며, 훌륭한 해시 함수가 사용되면 최악의 경우 성능이 발생할 가능성은 매우 낮다.
분리 연결 방식을 사용하는 해시 테이블의 버킷을 구현하기 위해 균형 이진 탐색 트리를 사용할 수 있다. 이렇게 하면 평균적인 경우 상수 시간 조회는 보장되지만, 최악의 경우 성능은 O(log ''n'')을 보장한다. 그러나 이로 인해 구현이 복잡해지고, 트리 삽입 및 균형을 맞추는 데 소요되는 시간이 연결 목록 또는 유사한 데이터 구조의 모든 요소에 대해 선형 검색을 수행하는 데 필요한 시간보다 더 커서, 더 작은 해시 테이블의 경우 성능이 더욱 저하될 수 있다.[13][14]
4. 언어 지원
많은 프로그래밍 언어에서 연관 배열을 기본 자료형 또는 표준 라이브러리로 제공한다. 일부 언어에서는 표준 시스템에 내장될 뿐만 아니라 특별한 구문을 가지며, 종종 배열과 유사한 첨자를 사용한다.
SNOBOL4에서 1969년에 "table"이라는 이름으로 연관 배열에 대한 내장 구문 지원을 도입하였다. TMG는 문자열 키와 정수 값을 가진 테이블을 제공했다. MUMPS는 다차원 연관 배열을 만들었으며, 선택적으로 영구적으로 유지되는 핵심 데이터 구조였다. SETL은 집합과 맵의 가능한 구현 중 하나로 이를 지원했다. AWK를 시작으로 Rexx, Perl, PHP, Tcl, 자바스크립트, 메이플, 파이썬, 루비, 울프럼 언어, 고, Lua를 포함한 대부분의 현대 스크립트 언어는 연관 배열을 주요 컨테이너 유형으로 지원한다. 더 많은 언어에서 특별한 구문 없이 라이브러리 함수로 사용할 수 있다.
스몰토크, Objective-C, .NET[20], 파이썬, REALbasic, 스위프트, VBA 및 델파이[21]에서는 '딕셔너리'라고 부르고, Perl, 루비 및 Seed7에서는 '해시'라고 부른다. C++, C#, 자바, 고, 클로저, 스칼라, OCaml, Haskell에서는 '맵'이라고 부른다. Common Lisp 및 Windows PowerShell에서는 '해시 테이블'이라고 부른다 (둘 다 일반적으로 이 구현을 사용하기 때문). 메이플과 Lua에서는 '테이블'이라고 부른다. PHP와 R에서는 모든 배열이 연관 배열이 될 수 있지만 키는 정수와 문자열로 제한된다. 자바스크립트(JSON 참조)에서는 모든 객체가 문자열 값의 키를 가진 연관 배열처럼 동작하며, Map 및 WeakMap 타입은 임의의 객체를 키로 사용한다. Lua에서는 모든 데이터 구조의 기본 구성 요소로 사용된다. Visual FoxPro에서는 '컬렉션'이라고 부른다. D 언어 역시 연관 배열을 지원한다.[22]
구체적인 언어별 지원 현황은 다음과 같다.
| 언어 | 지원 현황 |
|---|---|
| AWK | `greetings["en"] = "Hello"; greetings["fr"] = "Bonjour"`와 같은 형식으로 선언하고, `print greetings["fr"]`와 같이 참조한다.[27][28] |
| GNU Bash | `declare -A greetings=(["en"]="Hello" ["fr"]="Bonjour")`와 같은 형식으로 선언하고, `echo ${greetings["fr"]}`와 같이 참조한다.[29] |
| C++ | 표준 라이브러리의 클래스 `std::map`으로 제공된다. 이는 해시가 아닌 이진 트리로 구현된다. 해시를 사용한 `std::unordered_map`도 제공된다. |
| D 언어 | `int[string] b;`가 문자열을 키로, 정수를 값으로 하는 연관 배열 b의 선언이다. |
| ECMAScript(JavaScript) | 모든 Object가 문자열 또는 심볼을 키로 하는 연관 배열로 취급된다. Map과 WeakMap 타입에서는 키를 임의의 객체로 할 수 있다. |
| Go | `map[string]int`가 문자열을 키로, 정수를 값으로 하는 연관 배열의 형식 정의이다. |
| Interactive Data Language | 지원 |
| korn | 지원 |
| Icon | 지원 |
| Java | Java Platform, Standard Edition 표준 패키지의 `java.util.Map`, `java.util.HashMap`, `java.util.TreeMap`, `java.util.LinkedHashMap`, `java.util.Hashtable`로 제공한다. 그 외에 Apache Commons Collections 등에서도 제공한다. |
| LISP | 고전적으로 키와 데이터로 구성된 cons 셀[30]의 리스트, 예를 들어 `(list (cons en "Hello") (cons fr "Bonjour"))`를 연관 배열로 사용했다 (car 부분을 키로, cdr 부분을 데이터로, 또는 그 반대로). 이를 편리하게 다루기 위한 함수 (assoc, rassoc)가 제공된다. Common Lisp에서는 해시 함수를 이용한 연관 배열이 제공되며, make-hash-table 함수로 객체를 생성할 수 있고, gethash 함수와 setf 매크로의 조합으로 키와 값의 쌍을 조작할 수 있다. |
| Lua | `tbl = {en = "Hello", fr = "Bonjour"}`로 선언하고, `print(tbl["idx1"])`와 같이 참조한다.[31] |
| .NET Framework (C#, VB.NET, F#) | `System.Collections.Hashtable`, `System.Collections.Specialized.ListDictionary`, `System.Collections.Specialized.HybridDictionary`, `System.Collections.Generic.Dictionary`로 제공한다 (단, `Dictionary`는 CLR 2.0 이후). |
| PL/SQL | 결합 배열 (Oracle Database 9i 이후) |
| PHP | 배열과 연관 배열의 구별이 없다. |
| Python | 딕셔너리`dict = {"en": "Hello", "fr": "Bonjour"}`로 선언하고, `print(dict["idx1"])`와 같이 참조한다.[32] |
| Perl | `%`로 시작하는 변수가 연관 배열이지만, 개별 요소는 `$hash{$key}`로 참조한다. 동일 언어에서 연관 배열을 (해시 값을 사용하는 구현 방법에 따라) "해시"라고 부르기 시작하면서 "해시"가 연관 배열의 별칭으로 정착되었다. |
| REXX | 지원 |
| Ruby | 내장 클래스 `Hash`로 제공한다. |
| Smalltalk | 지원 |
| SNOBOL | 지원 |
| Swift | 지원 |
| Visual Basic | `Scripting.Dictionary`로 제공한다. |
| Visual Basic for Applications | `Scripting.Dictionary`로 제공한다.[33] |
5. 정렬된 사전
사전의 기본 정의는 순서를 요구하지 않는다. 열거의 고정된 순서를 보장하기 위해 연관 배열의 정렬된 버전이 종종 사용된다. 정렬된 사전에는 두 가지 의미가 있다.[16]
- 열거의 순서는 정렬을 통해 주어진 키 집합에 대해 항상 결정론적이다. 이는 트리 기반 구현의 경우로 C++의 `map` 컨테이너가 대표적이다.
- 열거의 순서는 키에 독립적이며 대신 삽입 순서를 기반으로 한다. 이는 .NET Framework의 "정렬된 사전", 자바의 LinkedHashMap 및 파이썬의 경우이다.[17][18][19]
후자가 더 일반적이다. 이러한 정렬된 사전은 연관 리스트를 사용하거나, 일반 사전에 이중 연결 리스트를 오버레이하거나, 희소(정렬되지 않은) 배열에서 실제 데이터를 밀집된 삽입 순서가 지정된 배열로 이동하여 구현할 수 있다.
6. 영구 저장
연관 배열을 사용하는 많은 프로그램은 해당 데이터를 컴퓨터 파일과 같이 더 영구적인 형태로 저장해야 한다. 이 문제에 대한 일반적인 해결책은 '아카이빙' 또는 '직렬화'로 알려진 개념으로, 파일에 직접 쓸 수 있는 원본 객체의 텍스트 또는 이진 표현을 생성한다. 이는 .Net 또는 Cocoa와 같은 기본 객체 모델에서 가장 일반적으로 구현되며, 내부 데이터를 텍스트로 변환하는 표준 함수를 포함한다. 프로그램은 이러한 메서드를 호출하여 객체 그룹의 완전한 텍스트 표현을 생성할 수 있으며, 이러한 메서드는 거의 항상 기본 연관 배열 클래스에 이미 구현되어 있다.[23]
매우 큰 데이터 세트를 사용하는 프로그램의 경우, 개별 파일 저장은 적합하지 않으며 데이터베이스 관리 시스템(DB)이 필요하다. 일부 DB 시스템은 데이터를 직렬화한 다음 직렬화된 데이터와 키를 저장하여 연관 배열을 기본적으로 저장한다. 그런 다음 키를 사용하여 데이터베이스에서 개별 배열을 로드하거나 저장할 수 있다. 이러한 키-값 저장소는 오랫동안 사용되어 왔으며, 관계형 데이터베이스 (RDB)만큼 오랜 역사를 가지고 있지만, 표준화 부족과 다른 이유로 특정 틈새 역할로 사용이 제한되었다. 대부분 이러한 역할에 RDB가 사용되었지만, 객체를 RDB에 저장하는 것은 복잡할 수 있으며, 이는 객체-관계 임피던스 불일치로 알려진 문제이다.
2010년경부터, 클라우드 컴퓨팅에 적합하고 이를 사용하는 프로그램의 내부 구조와 더 밀접하게 일치하는 고성능 데이터베이스에 대한 필요성이 키-값 저장소 시장의 르네상스를 이끌었다. 이러한 시스템은 연관 배열을 기본 방식으로 저장하고 검색할 수 있으며, 이는 일반적인 웹 관련 워크플로우에서 성능을 크게 향상시킬 수 있다.
참조
[1]
서적
Higher Order Logic Theorem Proving and Its Applications
1995
[2]
서적
Proc. Symposium on Optimal Algorithms
Springer Verlag
1989
[3]
간행물
Introduction to Algorithms
MIT Press and McGraw-Hill
[4]
웹사이트
Dynamic Perfect Hashing: Upper and Lower Bounds
http://www.arl.wustl[...]
Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.
1994
[5]
문서
Goodrich, Tamassia, 2006
[6]
간행물
Data Structures & Algorithms in Java
Wiley
[7]
간행물
Algorithms and Data Structures: The Basic Toolbox
http://people.mpi-in[...]
Springer
[8]
문서
Goodrich, Tamassia, 2006
[9]
웹사이트
dictionary
https://xlinux.nist.[...]
2022-01-26
[10]
웹사이트
When should I use a hash table instead of an association list?
http://www.faqs.org/[...]
lisp-faq/part2
1996-02-20
[11]
간행물
Ext. Abstracts GIS-l 2006
GIS-I
[12]
문서
Trees in STL
http://cs.calvin.edu[...]
Joel Adams and Larry Nyhoff.
[13]
서적
The Art of Computer Programming
Addison-Wesley
[14]
웹사이트
Linear vs Binary Search
https://schani.wordp[...]
2010-04-30
[15]
서적
2015 IEEE 31st International Conference on Data Engineering
IEEE
2015-04
[16]
웹사이트
std::map
https://en.cpprefere[...]
[17]
웹사이트
OrderedDictionary Class (System.Collections.Specialized)
https://docs.microso[...]
[18]
웹사이트
LinkedHashMap
https://docs.oracle.[...]
[19]
웹사이트
collections — Container datatypes — Python 3.9.0a3 documentation
https://docs.python.[...]
[20]
웹사이트
Dictionary
[21]
웹사이트
System.Generics.Collections.TDictionary - RAD Studio API Documentation
http://docwiki.embar[...]
2017-04-18
[22]
웹사이트
Associative Arrays, the D programming language
http://dlang.org/has[...]
Digital Mars
[23]
문서
Archives and Serializations Programming Guide
https://developer.ap[...]
Apple Inc.
2012
[24]
문서
Goodrich, Tamassia, 2006
[25]
간행물
Data Structures & Algorithms in Java
Wiley
[26]
간행물
Algorithms and Data Structures: The Basic Toolbox
Springer
[27]
문서
実際にはBEGINアクションの内部などで行なう必要がある。
[28]
웹사이트
awk
http://pubs.opengrou[...]
IEEE and The Open Group
2018-11-02
[29]
웹사이트
Bash Reference Manual: Arrays
https://www.gnu.org/[...]
LFree Software Foundation, Inc.
2018-11-02
[30]
문서
car, cdrと呼ばれる二つデータが組になった、2-タプルのデータ構造
[31]
웹사이트
Lua 5.3 Reference Manual
https://www.lua.org/[...]
Lua.org, PUC-Rio.
2018-11-02
[32]
웹사이트
5. データ構造 — Python 3.7.1 ドキュメント
https://docs.python.[...]
Python Software Foundation
2018-11-02
[33]
웹사이트
Dictionary オブジェクト
https://docs.microso[...]
2020-01-06
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com