해시 배열 매핑 트리

Hash array mapped trie

해시 어레이 맵트라이[1](HAMT)는 해시 테이블과 어레이 맵트라이의 [1]특성을 조합한 어소시에이션 어레이의 실장입니다.이것은 해시 트리의 보다 일반적인 개념을 개량한 것입니다.

작동

HAMT는 키가 균등하게 분산되어 일정한 키 길이가 유지되도록 하기 위해 키가 최초로 해시되는 배열 맵트라이입니다.

HAMT의 어레이 맵트라이의 일반적인 실장에서는 각 노드는 일정한 수의 N개의 슬롯을 가진 테이블을 포함하며, 각 슬롯에는 제로 포인터 또는 다른 노드에 대한 포인터가 포함되어 있습니다.N은 보통 32입니다.각 노드에 N개의 포인터 공간을 할당하는 것은 비용이 많이 들기 때문에 대신 각 노드에는 N비트 길이의 비트맵이 포함되어 있습니다.여기서 각 비트는 nil 이외의 포인터의 존재를 나타냅니다.그 다음에 비트맵의 1개 수와 같은 길이의 포인터 배열(해밍 가중치)이 이어집니다.

HAMT의 장점

해시 어레이 매핑 트리는 메모리를 훨씬 경제적으로 사용하면서 거의 해시 테이블과 같은 속도를 달성합니다.또한 해시 테이블은 주기적으로 크기를 조정해야 할 수 있으며, 이는 비용이 많이 드는 작업이지만 HAMT는 동적으로 증가합니다.일반적으로 HAMT의 퍼포먼스는 N개의 슬롯이 몇 개 있는 큰 루트테이블에 의해 향상됩니다.일부 HAMT 바리안트에서는 루트가 느릿느릿 성장하여[1] 퍼포먼스에 미치는 영향은 거의 없습니다.

구현 상세

HAMT의 구현에는 숫자의 2진수 표현에서 1의 수를 세는 모집단 카운트 함수의 사용이 포함됩니다.이 작업은 많은 명령 집합 아키텍처에서 사용할 수 있지만 일부 고급 언어에서만 사용할 수 있습니다.모집단 카운트는 일련의 시프트 및 추가 명령을 사용하여 O(1) 시간 내에 소프트웨어에서 구현할 수 있지만, 그렇게 하면 작업이 훨씬 [citation needed]더 느리게 수행될 수 있습니다.

실장

프로그래밍 언어 Clojure,[2] Scala 및 Frege는[3] 네이티브 해시 맵유형에 대해 영속적인 해시 배열 매핑트라이를 사용합니다.Haskell 라이브러리 "unordered-containers"는 영구 맵을 구현하고 데이터 [4]구조를 설정하기 위해 동일한 명령을 사용합니다.또 다른 Haskell 라이브러리 "stm-containers"는 소프트웨어 트랜잭션 [5]메모리의 컨텍스트에서 사용하기 위해 알고리즘을 조정합니다.Clojure 구현을 기반으로 한 Javascript HAMT 라이브러리도 이용할 수 있습니다.Rubinius의[7] Ruby 구현에는 HAMT가 포함되어 있으며 대부분 Ruby로 작성되지만 3개의 프리미티브가 포함되어[8] 있습니다.Erlang의 대형 맵에서는 릴리스 18.[9]0 이후 내부적으로 영속적인HAMT 표현을 사용하고 있습니다.Pony 프로그래밍 언어는 고정 컬렉션 패키지의 [10]해시 맵에 HAMT를 사용합니다.Rust 프로그래밍 언어에 영속적인 수집 유형을 제공하는im 및 im-rc crates는 영속적인 해시 테이블 및 해시 세트에 HAMT를 사용합니다.[11]

Ctrie라고 하는 해시 트리의 동시 잠금 프리[12] 버전은 스레드 세이프 방식의 변경 가능한 구현으로 진행이 보장됩니다.데이터 구조가 올바른[13] 것으로 증명되었습니다.Ctrie 운영은 원자성, 선형성 및 잠금 자유 특성을 가지고 있는 것으로 나타났습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c Phil Bagwell (2000). Ideal Hash Trees (PDF) (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.
  2. ^ "clojure/clojure". GitHub.
  3. ^ "Frege/frege". GitHub.
  4. ^ 요한 티벨, A.unordered-containers
  5. ^ Nikita Volkov, "stm-containers" 라이브러리 발표, 2014년
  6. ^ "mattbierner/hamt". GitHub.
  7. ^ "Ruby source file of Rubinius's HAMT". GitHub.
  8. ^ https://github.com/rubinius/rubinius/blob/master/machine/builtin/system.cpp#L1724-L1802[데드링크]
  9. ^ "Erlang Programming Language".
  10. ^ "horse: Pony is an open-source, actor-model, capabilities-secure, high performance programming language: Ponylang/ponyc". GitHub. 2018-11-26.
  11. ^ "API docs for Rust im-rc crate".
  12. ^ 프로코펙, A.GitHub에서의 동시 해시 시행 구현
  13. ^ Prokopec, A. et al. (2011) Cache-Aware Lock-Free 동시 해시 시도.테크니컬 리포트, 2011.