연관 배열

Associative array
"Dictionary(데이터 구조)"는 여기서 리디렉션됩니다.데이터 사전과 혼동하지 마십시오.
"Associative container"는 여기서 리디렉션됩니다.C++ 프로그래밍 언어의 표준 라이브러리에서 순서 있는 연관 배열의 구현에 대해서는 관련 컨테이너를 참조하십시오.
「맵(컴퓨터 과학)」은, 여기서 리다이렉트 됩니다.고차 함수는 지도(고차 함수)를 참조하십시오.

컴퓨터 과학에서, 연관 배열, 지도, 기호 테이블 또는 사전은 가능한 각 키가 컬렉션에 한 번에 나타나도록 (키, 값) 쌍의 컬렉션을 저장하는 추상 데이터 유형입니다.수학적인 용어로, 연관 배열은 유한한 [1]영역을 가진 함수이다.'조회', '제거' 및 '삽입' 작업을 지원합니다.

사전 문제는 연관 [2]배열을 구현하는 효율적인 데이터 구조를 설계하는 전형적인 문제입니다.사전 문제에 대한 두 가지 주요 해결책은 해시 테이블과 검색 [3][4][5][6]트리입니다.경우에 따라서는 직접 주소 지정된 배열, 이진 검색 트리 또는 기타 보다 특수한 구조를 사용하여 문제를 해결할 수도 있습니다.

많은 프로그래밍 언어에는 원시 데이터 유형으로 연관 배열이 포함되어 있으며, 다른 많은 언어에서는 소프트웨어 라이브러리에서 사용할 수 있습니다.컨텐츠 주소 지정 가능 메모리는 관련 어레이에 대한 하드웨어 수준의 직접 지원의 한 형태입니다.

연상 배열은 메모화 및 데코레이터 [7]패턴과 같은 기본 프로그래밍 패턴을 포함한 많은 애플리케이션을 가진다.

이 이름은 수학에서 알려진 연관 속성에서 유래하지 않습니다.오히려 우리가 가치를 키와 연관짓는다는 사실에서 비롯됩니다.관련 프로세서와 혼동해서는 안 됩니다.

운용

연상 배열에서 키와 값 사이의 연관성은 종종 "매핑"으로 알려져 있으며, 동일한 단어 매핑은 새로운 연관성을 작성하는 프로세스를 참조하기 위해 사용될 수도 있다.

일반적으로 연관 배열에 대해 정의되는 작업은 다음과 같습니다.[3][4][8]

  • 삽입 또는 입력: 새( y e pair를 컬렉션에 추가하여 키를 새 값에 매핑합니다.기존 매핑을 덮어씁니다.이 작업의 인수는 키와 값입니다.
  • 삭제 또는 삭제 컬렉션에서 ( , e) \ , )쌍을 삭제하고 지정된 키를 해당 값에서 매핑 해제합니다.이 작업에 대한 인수가 핵심입니다.
  • 검색, 검색 또는 가져오기: 지정된 키에 바인딩된 값(있는 경우)을 찾습니다.이 조작에 대한 인수가 키이며 이 값은 조작에서 반환됩니다.값을 찾을 수 없는 경우 일부 관련 어레이 구현에서 예외가 발생하는 반면 다른 구현에서는 기본값(0, null, 특정 값이 생성자에게 전달됨 등)이 반환됩니다.

또한 관련 배열은 매핑 수를 결정하거나 모든 매핑을 루프하는 반복기 구성 등의 다른 작업을 포함할 수도 있습니다.통상, 이러한 조작에서는, 매핑이 반환되는 순서가 실장 정의되는 경우가 있습니다.

멀티맵은 하나의 [9]키에 여러 값을 관련짓는 것을 허용함으로써 관련 배열을 일반화한다.양방향 맵은 매핑이 양방향으로 동작하는 관련 추상 데이터 유형입니다.각 값은 하나의 키와 관련지어져야 하며, 두 번째 룩업 조작은 값을 인수로 사용하여 해당 값과 관련된 키를 검색합니다.

특성.

연관 배열의 작업은 다음과 같은 다양한 [8]속성을 충족해야 합니다.

  • lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)
  • lookup(k, new()) = fail,어디에fail예외 또는 기본값입니다.
  • remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))
  • remove(k, new()) = new()

어디에k그리고.j키입니다.v값입니다.D어소시에이트 어레이입니다.new()는 비어 있는 새로운 관련 배열을 만듭니다.

예

도서관에서 대출한 집합을 데이터 구조로 표현한다고 가정합니다.도서관에 있는 각 책은 한 번에 한 명의 도서관 후원자만 대출할 수 있습니다.그러나 한 명의 후원자는 여러 권의 책을 대출할 수 있다.따라서 어떤 책이 대출되는지에 대한 정보는 어떤 고객을 대표할 수 있는가 하면, 책이 열쇠이고, 그 고객이 가치이다.Python 또는 JSON의 표기법을 사용하면 데이터 구조는 다음과 같습니다.

{     '오만과 편견": 앨리스,     '폭풍의 언덕': 앨리스,     "대단한 기대": "존' }

"Great Expections" 키에 대한 조회 작업은 "John"을 반환합니다.John이 책을 반납하면 삭제 작업이 발생하고 Pat이 책을 체크아웃하면 삽입 작업이 발생하여 다른 상태가 됩니다.

{     '오만과 편견": 앨리스,     카라마조프 형제: 팻,     '폭풍의 언덕': 앨리스 }

실행

매핑 수가 매우 적은 사전의 경우 매핑의 링크 목록인 연결 목록을 사용하여 사전을 구현하는 것이 좋습니다.이 실장에서는, 기본적인 딕셔너리 조작의 실행 시간은 매핑의 합계수에서 선형으로 되어 있습니다만, 실장이 용이하고, 실행 시간의 상수 요인이 [3][10]작아집니다.

키가 좁은 범위로 제한되었을 때 사용할 수 있는 또 다른 매우 간단한 구현 기술은 어레이에 직접 주소를 지정하는 것입니다.특정 키 k의 값은 어레이 셀 A[k]에 저장되거나 k의 매핑이 없을 경우 셀은 매핑의 부재를 나타내는 특별한 센티넬 값을 저장합니다.이 기술은 간단할 뿐만 아니라 속도가 빠릅니다. 각 사전 작업은 일정한 시간이 소요됩니다.단, 이 구조의 공간 요건은 키 공간 전체의 크기이기 때문에 키 공간이 [5]작지 않으면 실용적이지 않습니다.

사전을 구현하는 두 가지 주요 방법은 해시 테이블 또는 검색 [3][4][5][6]트리입니다.

해시 테이블 구현

주요 기사:해시 테이블
이 그래프는 대형 해시 테이블(캐시 크기를 훨씬 초과)에서 요소를 검색하는 데 필요한 CPU 캐시 손실의 평균 수를 체인 및 선형 검색과 비교합니다.선형 프로빙은 참조 인접성이 우수하기 때문에 성능이 향상되지만 테이블이 가득 찰수록 성능이 크게 저하됩니다.

어소시에이티브 어레이의 가장 빈번하게 사용되는 범용 실장은 해시 테이블과 함께 각 키를 어레이의 개별 "버킷"으로 구분하는 해시 함수와 결합된 어레이입니다.해시 테이블의 기본 개념은 인덱스를 통해 배열의 요소에 액세스하는 것이 단순하고 일정한 시간 작업이라는 것입니다.따라서 해시 테이블에 대한 작업의 평균 오버헤드는 키 해시의 계산과 어레이 내의 대응하는 버킷에 대한 액세스만 조합한 것입니다.따라서 해시 테이블은 일반적으로 O(1) 시간 내에 수행되며 대부분의 경우 대체 테이블보다 성능이 우수합니다.

해시 테이블은 충돌을 처리할 수 있어야 합니다. 해시 함수가 두 개의 다른 키를 배열의 동일한 버킷에 매핑하는 경우입니다.이 문제에 대한 가장 일반적인 접근방식은 개별 체인과 [3][4][5][11]오픈어드레싱입니다별도의 체인으로 배열은 값 자체를 저장하지 않고 해시에 일치하는 모든 값을 저장하는 다른 컨테이너(일반적으로 연결 목록)에 대한 포인터를 저장합니다.한편, 오픈 어드레싱에서는 해시 콜리전이 발견되면 테이블은 어레이 내의 빈 지점을 찾아 결정론적 방법으로 값을 저장합니다.보통 어레이 내의 다음 직전의 위치를 조사합니다.

오픈 어드레싱은 테이블이 대부분 비어 있을 때 별도의 체인에 비해 캐시 누락 비율이 낮습니다.그러나 테이블이 더 많은 요소로 채워질수록 오픈 어드레싱의 성능은 기하급수적으로 저하됩니다.또한 엔트리가 매우 작지 않은 한(포인터의 4배 미만) 개별 체인은 대부분의 경우 더 적은 메모리를 사용합니다.

트리 실장

주요 기사:검색 트리

자체 밸런싱 바이너리 검색 트리

또 다른 일반적인 접근법은 AVL 트리나 빨간색-검은색 [12]트리 등의 자가 밸런싱 바이너리 검색 트리를 사용하여 연관 배열을 구현하는 것입니다.

해시 테이블과 비교하여 이러한 구조는 장점과 단점을 모두 가지고 있습니다.셀프밸런싱 바이너리 검색 트리의 최악의 퍼포먼스는 O(log n)의 빅 O 표기로 시간이 복잡하여 해시 테이블보다 훨씬 우수합니다.이는 모든 요소가 단일 버킷을 공유하기 때문에 O(n) 시간이 복잡해지는 해시 테이블과는 대조적입니다.또한 모든 바이너리 검색 트리와 마찬가지로 셀프밸런싱 바이너리 검색 트리는 요소를 순서대로 유지합니다.따라서 요소를 통과하는 것은 최소에서 가장 큰 패턴을 따르지만 해시 테이블을 통과하는 것은 요소가 무작위로 보일 수 있습니다.단, 해시 테이블은 O(1)의 자기 밸런싱 바이너리 검색 트리보다 평균 케이스의 시간 복잡도가 훨씬 높고, 양호한 해시 함수를 사용할 경우 최악의 퍼포먼스는 거의 발생하지 않습니다.

자가 밸런싱 바이너리 검색 트리를 사용하여 별도의 체인을 사용하는 해시 테이블의 버킷을 구현할 수 있습니다.이것에 의해, 평균적인 케이스의 계속적인 룩업이 가능하게 됩니다만, 최악의 케이스의 퍼포먼스 O(log n)는 보증됩니다.그러나 이로 인해 구현이 더욱 복잡해지고 작은 해시 테이블에서는 성능이 더욱 저하될 수 있습니다.이 경우 트리를 삽입하고 균형을 맞추는 데 소요되는 시간이 링크된 목록 또는 유사한 데이터 [13][14]구조의 모든 요소에 대해 선형 검색을 수행하는 데 필요한 시간보다 길어집니다.

기타 트리

어소시에이티브 어레이는 불균형 바이너리 검색 트리 또는 기수 트리, 트라이, Judy 어레이, 또는 van Emde Boas 트리 등의 특정 유형의 키에 특화된 데이터 구조에도 저장될 수 있습니다.단, 해시 테이블과 비교한 이들 구현 방법의 기능은 다양합니다.예를 들어 Judy 트리는 다음과 같이 동작하도록 지시되어 있습니다.해시 테이블보다 효율성이 적은 반면 신중하게 선택된 해시 테이블은 일반적으로 적응형 기수 트리에 비해 효율성이 향상되고 처리할 [15]수 있는 데이터 유형에 더 큰 제한이 있을 수 있습니다.이러한 대체 구조의 장점은 쿼리 자체가 매핑 세트에 존재하지 않을 때 쿼리된 키에 가장 가까운 매핑을 찾는 등 관련 배열의 기본보다 더 많은 작업을 처리할 수 있다는 것입니다.

비교

기본 데이터 구조 조회 또는 삭제 삽입 주문된
평균 최악의 경우 평균 최악의 경우
해시 테이블 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) 아니요.

정렬된 사전

사전의 기본 정의는 명령을 요구하지 않습니다.열거의 고정 순서를 보장하기 위해 연결된 배열의 정렬된 버전이 자주 사용됩니다.정렬된 사전에는 다음 두 가지 의미가 있습니다.

  • 열거 순서는 항상 정렬을 통해 특정 키 집합에 대해 결정됩니다.이는 트리 기반 구현의 경우로, 대표적인 것이 다음과 같습니다.<map>C++[16] 컨테이너
  • 열거 순서는 키에 의존하지 않고 삽입 순서에 따라 결정됩니다.이것은 의 "순서 있는 딕셔너리"의 경우입니다.NET Framework 및 [17][18]Python.

정렬된 사전의 후자는 더 흔히 볼 수 있습니다.연결 목록을 사용하거나 일반 사전 위에 이중으로 연결된 목록을 겹쳐서 구현할 수 있습니다.버전 3.6 이전 CPython에서 사용한 후자의 접근방식은 다른 [19]구현의 복잡성을 잠재적으로 개선할 수 있다는 장점이 있다.CPython 3.6+는 해시 테이블을 k-v 쌍의 삽입 순서 배열과 [20]인덱스의 스파스 배열("해시 테이블")로 분할하여 정렬된 사전을 만듭니다.

언어 지원

주요 기사:프로그래밍 언어 비교(매핑)

연관 배열은 모든 프로그래밍 언어로 패키지로 구현할 수 있으며 많은 언어 시스템이 표준 라이브러리의 일부로 제공합니다.일부 언어에서는 표준 시스템에 내장되어 있을 뿐만 아니라 어레이와 같은 첨자를 사용하는 특수한 구문을 가지고 있습니다.

어소시에이션 어레이에 대한 내장 구문 지원은 1969년 SNOBOL4에 의해 "table"이라는 이름으로 도입되었습니다.TMG는 문자열 키와 정수 값을 가진 테이블을 제공했습니다.MUMP는 다차원 연상 어레이를 핵심 데이터 구조로 만들었습니다.SETL은 세트 및 맵의 가능한 구현 중 하나로 이들을 지원했습니다.AWK부터 시작하여 Rexx, Perl, PHP, Tcl, JavaScript, Maple, Python, Ruby, Wolfram Language, Go, Lua를 포함한 대부분의 최신 스크립트 언어는 주요 컨테이너 유형으로 연관 배열을 지원합니다.많은 언어에서 특별한 구문 없이 라이브러리 함수로 사용할 수 있습니다.

Smalltalk, Objective-C에서.NET,[21] Python, REALbasic, Swift, VBA 및 Delphi에서는[22] 그것들은 사전이라고 불립니다.Perl, Ruby 및 Seed7에서는 해시라고 불립니다.C++, Java, Go, Clojure, Scala, OCaml, Haskell에서는 맵(C+++), 미순서입니다.MapCommon Lisp 및 Windows PowerShell에서는 해시 테이블(일반적으로 둘 다 이 구현을 사용하므로)이라고 합니다.Maple 및 Lua에서는 테이블이라고 부릅니다.PHP에서는 키가 정수와 문자열로 제한되는 것을 제외하고 모든 배열이 연관될 수 있습니다.JavaScript(JSON도 참조)에서는 모든 객체가 문자열 값 키를 가진 연관 배열로 동작하며 Map 및 WeakMap 유형은 임의의 객체를 키로 사용합니다.Lua에서는 모든 데이터 구조의 기본 구성 요소로 사용됩니다.Visual Fox Pro에서는 Collections라고 부릅니다.D언어에는 연관 [23]배열도 지원됩니다.

영속적 스토리지

주요 기사:키-값 저장소

어소시에이션 어레이를 사용하는 많은 프로그램에서는, 어느 시점에서는, 그 데이터를 컴퓨터 파일과 같이 보다 영속적인 형태로 보존할 필요가 있습니다.이 문제에 대한 일반적인 해결책은 아카이브 또는 시리얼라이제이션이라고 하는 일반적인 개념입니다.이것에 의해, 파일에 직접 쓸 수 있는 원래의 오브젝트의 텍스트 또는 바이너리 표현을 생성할 수 있습니다.이는 와 같은 기본 객체모델에서 가장 일반적으로 구현됩니다.Net 또는 Cocoa 내부 데이터를 텍스트 형식으로 변환하는 표준 기능을 포함합니다.이 프로그램은 이러한 메서드를 호출하여 오브젝트 그룹의 완전한 텍스트 표현을 만들 수 있습니다.이 메서드는 거의 항상 기본 연관 배열 [24]클래스에서 구현되어 있습니다.

매우 큰 데이터 세트를 사용하는 프로그램에서는 이러한 종류의 개별 파일 스토리지가 적절하지 않으며 데이터베이스 관리 시스템(DB)이 필요합니다.일부 DB 시스템은 데이터를 직렬화한 다음 직렬화된 데이터와 키를 저장하여 연관 배열을 기본적으로 저장합니다.그런 다음 키를 사용하여 개별 어레이를 데이터베이스에서 로드하거나 저장할 수 있습니다.이러한 주요 가치 저장소는 오랜 세월 동안 사용되어 왔으며 더 일반적인 관계형 데이터베이스(RDB)만큼 오랜 역사를 가지고 있지만, 표준화 부족으로 인해 특정 틈새 역할에 대한 사용이 제한되었습니다.오브젝트를 RDB에 저장하는 것은 복잡할 수 있지만 객체-관계 임피던스 미스매치라고 불리는 문제가 발생할 수 있지만 대부분의 경우 대부분의 경우 이러한 역할에 RDB가 사용되었습니다.

2010년 이후 클라우드 컴퓨팅에 적합한 고성능 데이터베이스의 필요성과 이를 사용하는 프로그램의 내부 구조에 보다 밀접하게 일치함에 따라 키-밸류 스토어 시장은 다시 활기를 띠게 되었습니다.이러한 시스템은 관련 어레이를 네이티브 방식으로 저장 및 검색할 수 있으므로 일반적인 웹 관련 워크플로우에서 성능을 크게 향상시킬 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Collins, Graham; Syme, Donald (1995). "A theory of finite maps". Higher Order Logic Theorem Proving and Its Applications. Lecture Notes in Computer Science. 971: 122–137. doi:10.1007/3-540-60275-5_61. ISBN 978-3-540-60275-0.
  2. ^ Andersson, Arne (1989). "Optimal Bounds on the Dictionary Problem". Proc. Symposium on Optimal Algorithms. Lecture Notes in Computer Science. Springer Verlag. 401: 106–114. doi:10.1007/3-540-51859-2_10. ISBN 978-3-540-51859-4.
  3. ^ a b c d e Goodrich, Michael T.; Tamassia, Roberto (2006), "9.1 The Map Abstract Data Type", Data Structures & Algorithms in Java (4th ed.), Wiley, pp. 368–371
  4. ^ a b c d Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 81–98
  5. ^ a b c d 를 클릭합니다Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "11 Hash Tables", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 221–252, ISBN 0-262-03293-7.
  6. ^ a b Dietzfelbinger, M., Carlin, A., Melhorn, K., Meyer auf der Heide, F., R. H. 및 Tarjan, 1994."Dynamic Perfect Hashing: Upper and Lower Bounds" Wayback Machine에 2016-03-04 아카이브되었습니다.SIAM J. Comput. 23, 4(1994년 8월), 738-761.http://portal.acm.org/citation.cfm?id=182370 doi:10.1137/S0097539791194094
  7. ^ Goodrich & Tamassia (2006), 597-599페이지.
  8. ^ a b Black, Paul E.; Stewart, Rob (2 November 2020). "dictionary". Dictionary of Algorithms and Data Structures. Retrieved 26 January 2022.
  9. ^ 굿리치 &, Tamassia(2006년),를 대신하여 서명함. 389–397.
  10. ^ "When should I use a hash table instead of an association list?". lisp-faq/part2. 1996-02-20.
  11. ^ Klammer, F.;Mazzolini, L.(2006년),"연합 지도에 대해하는 길잡이들입니다", 외부의.학 초록 GIS-l 2006년, GIS-I,를 대신하여 서명함. 71–74.
  12. ^ 조엘 애덤스와 래리 Nyhoff."잠수함 이동 항로에 있는 나무들".이렇게 말했지"그 표준 템플릿 라이브러리...일부 용기의 set&lt을 말한다.T>, map<, T1, T2>, 멀티셋<T>, multimap<, T1, T2>, 템플릿, 일반적으로 자동 평형 2진 탐색 트리의 특별한 종류는 red–black tree."을 이용해 지어진다.
  13. ^ Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 0-201-89685-0.
  14. ^ Probst, Mark (2010-04-30). "Linear vs Binary Search". Retrieved 2016-11-20.
  15. ^ Alvarez, Victor; Richter, Stefan; Chen, Xiao; Dittrich, Jens (April 2015). "A comparison of adaptive radix trees and hash tables". 2015 IEEE 31st International Conference on Data Engineering. Seoul, South Korea: IEEE: 1227–1238. doi:10.1109/ICDE.2015.7113370. ISBN 978-1-4799-7964-6. S2CID 17170456.
  16. ^ "std::map". en.cppreference.com.
  17. ^ "OrderedDictionary Class (System.Collections.Specialized)". MS Docs.
  18. ^ "collections — Container datatypes — Python 3.9.0a3 documentation". docs.python.org.
  19. ^ Dimitris Fasarakis Hilliard. "dictionary - How does Python's OrderedDict remember elements inserted?". Stack Overflow.
  20. ^ Dimitris Fasarakis Hilliard. "Are dictionaries ordered in Python 3.6+?". Stack Overflow.
  21. ^ "Dictionary<TKey, TValue> Class". MSDN.
  22. ^ "System.Generics.Collections.TDictionary - RAD Studio API Documentation". docwiki.embarcadero.com. Retrieved 2017-04-18.
  23. ^ "Associative Arrays, the D programming language". Digital Mars.
  24. ^ "공문서 및 Serializations 프로그래밍 가이드"애플 2012년.

외부 링크

위키 낱말 사전, 자유 사전에 연상 배열을 찾아보라.