해시 테이블(Hash Tables)

해시 테이블(줄여서 hash)은 각 키(key)를 하나의 값(value)에 대응시키는 자료 구조예요. 키 비교 방식과 키 보유 방식, 가변성 여부에 따라 여러 종류가 있습니다.

출처: Racket Reference

본문

해시 테이블에 대한 소개는 The Racket Guide의 Hash Tables에서 다룹니다.

해시 테이블(또는 간단히 hash)은 각 키를 하나의 값에 대응시킵니다. 주어진 해시 테이블에서 키들은 equal?, equal-always?, eqv?, 또는 eq?로 동등하며, 키들은 강하게(strongly), 약하게(weakly, Weak Boxes 참고), 또는 ephemeron처럼 유지됩니다. 해시 테이블은 또한 가변(mutable) 또는 불변(immutable)입니다. 불변 해시 테이블은 가변 해시 테이블과 마찬가지로 사실상 상수 시간의 접근과 갱신을 지원합니다. 불변 연산의 상수는 보통 더 크지만, 불변 해시 테이블의 함수형 특성은 특정 알고리즘에서 이점이 될 수 있습니다. 해시 테이블이 불변인지 확인하려면 immutable?을 사용하세요.

불변 해시 테이블은 실제로 O(log N)의 접근과 갱신을 제공합니다. N이 주소 공간에 의해 제한되어 log N이 30 또는 62(플랫폼에 따라) 미만으로 제한되므로, log N은 합리적으로 상수로 취급할 수 있습니다.

equal? 기반 해싱에서 문자열, 쌍, 리스트, 벡터, prefab 또는 투명한(transparent) 구조체 등에 대한 내장 해시 함수는 값의 크기에 비례하는 시간이 걸립니다. 리스트나 벡터 같은 복합 데이터 구조의 해시 코드는 컨테이너의 각 항목을 해싱하는 데 의존하지만, 그러한 재귀 해싱의 깊이는 (순환 데이터의 잠재적 문제를 피하기 위해) 제한됩니다. 비-리스트 쌍의 경우 car와 cdr 해싱 둘 다 더 깊은 해시로 취급되지만, 리스트의 cdr는 리스트와 같은 해싱 깊이로 취급됩니다.

해시 테이블은 두 값을 가진 시퀀스(Sequences 참고)로 사용될 수 있습니다. 해시 테이블의 키와 값이 시퀀스의 요소 역할을 합니다(즉, 각 요소는 키와 그 연관 값입니다). 반복 중에 가변 해시 테이블에서 매핑이 추가되거나 제거되면, 반복 단계가 exn:fail:contract으로 실패하거나, 반복이 키와 값을 건너뛰거나 중복할 수 있습니다. in-hash, in-hash-keys, in-hash-values, in-hash-pairs도 함께 보세요.

두 해시 테이블은 같은 가변성을 갖고, 같은 키 비교 프로시저(equal?, equal-always?, eqv?, 또는 eq?)를 사용하며, 둘 다 키를 강하게, 약하게, 또는 ephemeron처럼 보유해야만 equal?일 수 있습니다. 빈 불변 해시 테이블은 equal?일 때 eq?입니다.

package base의 7.2.0.9 버전에서 변경: 빈 불변 해시 테이블이 equal?일 때 eq?가 되도록 만들었습니다.

동시 수정(concurrent modification)에 관한 주의 사항: 가변 해시 테이블은 여러 스레드가 hash-ref, hash-set!, hash-remove!로 동시에 조작할 수 있고, 연산은 필요에 따라 테이블-특화 세마포어로 보호됩니다. 그러나 몇 가지 주의 사항이 적용됩니다:

스레드가 equal?, equal-always?, eqv? 키 비교를 사용하는 해시 테이블에 hash-ref, hash-ref-key, hash-set!, hash-remove!, hash-ref!, hash-update!, hash-clear!를 적용하는 동안 종료되면, 그 해시 테이블에 대한 모든 현재 및 미래 연산이 무기한 차단될 수 있습니다.
hash-map, hash-for-each, hash-clear! 프로시저는 (순회가 필요할 때, hash-clear!의 경우) 순회 전체를 지키기 위해 테이블의 세마포어를 사용하지 않습니다. 한 스레드가 해시 테이블을 변경하면, 같은 해시 테이블을 순회하는 중인 다른 스레드가 보는 키와 값에 영향을 줄 수 있습니다.
hash-update!와 hash-ref! 함수는 기능의 hash-ref 부분과 hash-set! 부분에 대해 테이블의 세마포어를 독립적으로 사용합니다. 즉, 갱신 전체는 "원자적"이지 않습니다.
가변 해시 테이블을 그 자체의 키로 추가하는 것은 키가 변형되고 있다는 이유(아래 주의 사항 참고)로 문제일 뿐만 아니라, 일종의 해시 테이블 동시 사용이기도 합니다: 해시 테이블의 해시 코드를 계산하려면 테이블의 세마포어를 기다려야 할 수 있는데, 그 세마포어는 해시 테이블을 수정하기 위해 이미 보유되어 있으므로, 해시 테이블 추가는 무기한 차단될 수 있습니다.

가변 키(mutable keys)에 관한 주의 사항: equal? 기반 해시 테이블에서 키가 변형되면(예: 키 문자열이 string-set!으로 수정되면), 해시 테이블의 삽입과 조회 연산의 동작이 예측할 수 없게 됩니다.

리터럴 또는 인쇄된 해시 테이블은 #hash, #hashalw, #hasheqv, 또는 #hasheq로 시작합니다. 해시 테이블 읽기에 대한 정보는 Reading Hash Tables, 해시 테이블 출력에 대한 정보는 Printing Hash Tables를 참고하세요.

`hash?`

procedure

(hash? v) → boolean?
  v : any/c

v가 해시 테이블이면 #t, 그 외에는 #f를 반환합니다.

immutable-hash?와 mutable-hash?도 함께 보세요.

`hash-equal?`

procedure

(hash-equal? ht) → boolean?
  ht : hash?

ht가 키를 equal?로 비교하면 #t, eq?, eqv?, equal-always?로 비교하면 #f를 반환합니다.

`hash-equal-always?`

procedure

(hash-equal-always? ht) → boolean?
  ht : hash?

ht가 키를 equal-always?로 비교하면 #t, eq?, eqv?, equal?로 비교하면 #f를 반환합니다.

package base의 8.5.0.3 버전에서 추가되었습니다.

`hash-eqv?`

procedure

(hash-eqv? ht) → boolean?
  ht : hash?

ht가 키를 eqv?로 비교하면 #t, equal?, equal-always?, eq?로 비교하면 #f를 반환합니다.

`hash-eq?`

procedure

(hash-eq? ht) → boolean?
  ht : hash?

ht가 키를 eq?로 비교하면 #t, equal?, equal-always?, eqv?로 비교하면 #f를 반환합니다.

`hash-strong?`

procedure

(hash-strong? ht) → boolean?
  ht : hash?

ht가 키를 강하게 보유하면 #t, 약하게 또는 ephemeron처럼 보유하면 #f를 반환합니다.

package base의 8.0.0.10 버전에서 추가되었습니다.

`hash-weak?`

procedure

(hash-weak? ht) → boolean?
  ht : hash?

ht가 키를 약하게 보유하면 #t, 강하게 또는 ephemeron처럼 보유하면 #f를 반환합니다.

`hash-ephemeron?`

procedure

(hash-ephemeron? ht) → boolean?
  ht : hash?

ht가 키를 ephemeron처럼 보유하면 #t, 키를 강하게 또는 단순히 약하게 보유하면 #f를 반환합니다.

package base의 8.0.0.10 버전에서 추가되었습니다.

`hash`, `hashalw`, `hasheq`, `hasheqv`

procedure

(hash key val ... ...) → (and/c hash? hash-equal? immutable? hash-strong?)
  key : any/c
  val : any/c

(hashalw key val ... ...) → (and/c hash? hash-equal-always? immutable? hash-strong?)
  key : any/c
  val : any/c

(hasheq key val ... ...) → (and/c hash? hash-eq? immutable? hash-strong?)
  key : any/c
  val : any/c

(hasheqv key val ... ...) → (and/c hash? hash-eqv? immutable? hash-strong?)
  key : any/c
  val : any/c

각각 주어진 key가 그 다음 val에 매핑된 불변 해시 테이블을 만듭니다. 각 key는 val을 가져야 하므로, hash에 대한 인자의 총 개수는 짝수여야 합니다.

hash 프로시저는 키를 equal?로 비교하는 테이블을 만들고, hashalw는 키를 equal-always?로 비교하는 테이블을 만들며, hasheq 프로시저는 키를 eq?로 비교하는 테이블을, hasheqv 프로시저는 키를 eqv?로 비교하는 테이블을 만듭니다.

key에서 val로의 매핑은 인자 목록에 나타나는 순서대로 테이블에 추가되므로, 나중 매핑이 키가 같으면 앞의 매핑을 숨길 수 있습니다.

package base의 8.5.0.3 버전에서 변경: hashalw가 추가되었습니다.

`make-hash`, `make-hashalw`, `make-hasheqv`, `make-hasheq`

procedure

(make-hash [assocs]) → (and/c hash? hash-equal? (not/c immutable?) hash-strong?)
  assocs : (listof pair?) = null

(make-hashalw [assocs]) → (and/c hash? hash-equal-always? (not/c immutable?) hash-strong?)
  assocs : (listof pair?) = null

(make-hasheqv [assocs]) → (and/c hash? hash-eqv? (not/c immutable?) hash-strong?)
  assocs : (listof pair?) = null

(make-hasheq [assocs]) → (and/c hash? hash-eq? (not/c immutable?) hash-strong?)
  assocs : (listof pair?) = null

키를 강하게 보유하는 가변 해시 테이블을 만듭니다.

make-hash 프로시저는 키를 equal?로 비교하는 테이블을 만들고, make-hasheq 프로시저는 키를 eq?로 비교하는 테이블을 만들며, make-hasheqv 프로시저는 키를 eqv?로 비교하는 테이블을, make-hashalw는 키를 equal-always?로 비교하는 테이블을 만듭니다.

테이블은 assocs의 내용으로 초기화됩니다. assocs의 각 요소에서 car는 키이고, cdr는 해당 값입니다. 매핑은 assocs에 나타나는 순서대로 테이블에 추가되므로, 나중 매핑이 앞의 매핑을 숨길 수 있습니다.

make-custom-hash도 함께 보세요.

예시:

> (make-hash)
'#hash()

> (make-hash '([0 . 1] [42 . "meaning of life"] [2 . 3]))
'#hash((0 . 1) (2 . 3) (42 . "meaning of life"))

> (make-hash '([0 . 1] [1 . 2] [0 . 3]))
'#hash((0 . 3) (1 . 2))

> (make-hash (list (cons 0 1) (cons 'apple 'orange) (cons #t #f)))
'#hash((#t . #f) (0 . 1) (apple . orange))

> (make-hash '((0 1) (1 2) (2 3)))
'#hash((0 . (1)) (1 . (2)) (2 . (3)))

> (make-hash (list (cons + -)))
'#hash((#<procedure:+> . #<procedure:->))

package base의 8.5.0.3 버전에서 변경: make-hashalw가 추가되었습니다.

`make-weak-hash`, `make-weak-hashalw`, `make-weak-hasheqv`, `make-weak-hasheq`

procedure

(make-weak-hash [assocs]) → (and/c hash? hash-equal? (not/c immutable?) hash-weak?)
  assocs : (listof pair?) = null

(make-weak-hashalw [assocs]) → (and/c hash? hash-equal-always? (not/c immutable?) hash-weak?)
  assocs : (listof pair?) = null

(make-weak-hasheqv [assocs]) → (and/c hash? hash-eqv? (not/c immutable?) hash-weak?)
  assocs : (listof pair?) = null

(make-weak-hasheq [assocs]) → (and/c hash? hash-eq? (not/c immutable?) hash-weak?)
  assocs : (listof pair?) = null

make-hash, make-hasheq, make-hasheqv, make-hashalw와 같지만, 키를 약하게 보유하는 가변 해시 테이블을 만듭니다.

약한 해시 테이블의 값은 정상적으로 유지된다는 점을 주의하세요. 테이블의 값이 그 키를 다시 참조하면, 테이블은 그 값을 따라서 키를 유지하게 됩니다. 키가 달리 접근 불가능해져도 매핑은 테이블에서 절대 제거되지 않습니다. 그 문제를 피하려면 make-ephemeron-hash, make-ephemeron-hashalw, make-ephemeron-hasheqv, make-ephemeron-hasheq가 만드는 ephemeron 해시 테이블을 사용하세요. 키를 참조하지 않는 값에 대해서는 약한 해시 테이블 대신 ephemeron 해시 테이블을 사용하는 데 약간의 추가 비용이 있지만, 애매하면 ephemeron 해시 테이블을 선호하세요.

package base의 8.5.0.3 버전에서 변경: make-weak-hashalw가 추가되었습니다.

`make-ephemeron-hash`, `make-ephemeron-hashalw`, `make-ephemeron-hasheqv`, `make-ephemeron-hasheq`

procedure

(make-ephemeron-hash [assocs]) → (and/c hash? hash-equal? (not/c immutable?) hash-ephemeron?)
  assocs : (listof pair?) = null

(make-ephemeron-hashalw [assocs]) → (and/c hash? hash-equal-always? (not/c immutable?) hash-ephemeron?)
  assocs : (listof pair?) = null

(make-ephemeron-hasheqv [assocs]) → (and/c hash? hash-eqv? (not/c immutable?) hash-ephemeron?)
  assocs : (listof pair?) = null

(make-ephemeron-hasheq [assocs]) → (and/c hash? hash-eq? (not/c immutable?) hash-ephemeron?)
  assocs : (listof pair?) = null

make-hash, make-hasheq, make-hasheqv, make-hashalw와 같지만, 키-값 조합을 ephemeron과 같은 방식으로 보유하는 가변 해시 테이블을 만듭니다.

ephemeron 해시 테이블을 사용하는 것은 약한 해시 테이블을 사용하고 각 키를 키와 값을 짝지은 ephemeron에 매핑하는 것과 같습니다. ephemeron 해시 테이블의 장점은 값이 hash-ref 같은 함수의 결과에서 ephemeron-value로 추출될 필요가 없다는 것입니다. ephemeron 해시 테이블은 또한 명시적인 ephemeron 값이 있는 약한 해시 테이블보다 더 간결하게 표현될 수 있습니다.

package base의 8.0.0.10 버전에서 추가되었습니다. 8.5.0.3 버전에서 변경: make-ephemeron-hashalw가 추가되었습니다.

`make-immutable-hash`, `make-immutable-hashalw`, `make-immutable-hasheqv`, `make-immutable-hasheq`

procedure

(make-immutable-hash [assocs]) → (and/c hash? hash-equal? immutable? hash-strong?)
  assocs : (listof pair?) = null

(make-immutable-hashalw [assocs]) → (and/c hash? hash-equal-always? immutable? hash-strong?)
  assocs : (listof pair?) = null

(make-immutable-hasheqv [assocs]) → (and/c hash? hash-eqv? immutable? hash-strong?)
  assocs : (listof pair?) = null

(make-immutable-hasheq [assocs]) → (and/c hash? hash-eq? immutable? hash-strong?)
  assocs : (listof pair?) = null

hash, hashalw, hasheq, hasheqv와 같지만, 키-값 매핑을 make-hash, make-hashalw, make-hasheq, make-hasheqv처럼 연관 리스트(association-list) 형태로 받습니다.

package base의 8.5.0.3 버전에서 변경: make-immutable-hashalw가 추가되었습니다.

`hash-set!`

procedure

(hash-set! ht key v) → void?
  ht : (and/c hash? (not/c immutable?))
  key : any/c
  v : any/c

ht에서 key를 v에 매핑하고, key에 대한 기존 매핑을 덮어씁니다.

위의 동시 수정 주의 사항과 가변 키 주의 사항도 함께 보세요.

`hash-set*!`

procedure

(hash-set*! ht key v ... ...) → void?
  ht : (and/c hash? (not/c immutable?))
  key : any/c
  v : any/c

ht에서 각 key를 각 v에 매핑하고, 각 key에 대한 기존 매핑을 덮어씁니다. 매핑은 왼쪽부터 추가되므로 나중 매핑이 앞의 매핑을 덮어씁니다.

위의 동시 수정 주의 사항과 가변 키 주의 사항도 함께 보세요.

`hash-set`

procedure

(hash-set ht key v) → (and/c hash? immutable?)
  ht : (and/c hash? immutable?)
  key : any/c
  v : any/c

ht를 함수적으로 확장해 key를 v에 매핑하고, key에 대한 기존 매핑을 덮어쓰며, 확장된 해시 테이블을 반환합니다.

위의 가변 키 주의 사항도 함께 보세요.

`hash-set*`

procedure

(hash-set* ht key v ... ...) → (and/c hash? immutable?)
  ht : (and/c hash? immutable?)
  key : any/c
  v : any/c

ht를 함수적으로 확장해 각 key를 v에 매핑하고, 각 key에 대한 기존 매핑을 덮어쓰며, 확장된 해시 테이블을 반환합니다. 매핑은 왼쪽부터 추가되므로 나중 매핑이 앞의 매핑을 덮어씁니다.

위의 가변 키 주의 사항도 함께 보세요.

`hash-ref`

procedure

(hash-ref ht key [failure-result]) → any
  ht : hash?
  key : any/c
  failure-result : failure-result/c
                 = (lambda () (raise (make-exn:fail:contract ....)))

ht에서 key의 값을 반환합니다. key에 대한 값을 찾지 못하면 failure-result가 결과를 결정합니다:

failure-result가 프로시저이면 (꼬리 호출을 통해) 인자 없이 호출되어 결과를 만들어냅니다.
그 외에는 failure-result가 결과로 반환됩니다.

예시:

> (hash-ref (hash) "hi")
hash-ref: no value found for key
  key: "hi"

> (hash-ref (hash) "hi" 5)
5

> (hash-ref (hash) "hi" (lambda () "flab"))
"flab"

> (hash-ref (hash "hi" "bye") "hi")
"bye"

> (hash-ref (hash "hi" "bye") "no")
hash-ref: no value found for key
  key: "no"

위의 동시 수정 주의 사항과 가변 키 주의 사항도 함께 보세요.

`hash-ref-key`

procedure

(hash-ref-key ht key [failure-result]) → any
  ht : hash?
  key : any/c
  failure-result : failure-result/c
                 = (lambda () (raise (make-exn:fail:contract ....)))

ht의 키 비교 함수에 따라 key와 동등한, ht가 보유한 키를 반환합니다. 키를 찾지 못하면 failure-result가 hash-ref에서처럼 결과를 결정하는 데 사용됩니다.

ht가 impersonator가 아니면 반환된 키는 (찾았다고 가정하고) ht가 실제로 보유한 것과 eq?-동등합니다:

예시:

> (define original-key "hello")
> (define key-copy (string-copy original-key))
> (equal? original-key key-copy)
#t

> (eq? original-key key-copy)
#f

> (define table (make-hash))
> (hash-set! table original-key 'value)
> (eq? (hash-ref-key table "hello") original-key)
#t

> (eq? (hash-ref-key table "hello") key-copy)
#f

가변 해시가 eq?-동등하지 않지만 해시의 키 비교 프로시저에 따르면 동등한 키로 여러 번 갱신되면, 해시는 첫 번째 것을 보유합니다:

예시:

> (define original-key "hello")
> (define key-copy (string-copy original-key))
> (define table (make-hash))
> (hash-set! table original-key 'one)
> (hash-set! table key-copy 'two)
> (eq? (hash-ref-key table "hello") original-key)
#t

> (eq? (hash-ref-key table "hello") key-copy)
#f

반대로, 불변 해시는 그것을 갱신하는 데 가장 최근에 사용된 키를 보유합니다:

예시:

> (define original-key "hello")
> (define key-copy (string-copy original-key))
> (define table0 (hash))
> (define table1 (hash-set table0 original-key 'one))
> (define table2 (hash-set table1 key-copy 'two))
> (eq? (hash-ref-key table2 "hello") original-key)
#f

> (eq? (hash-ref-key table2 "hello") key-copy)
#t

ht가 impersonator이면 반환된 키는 impersonate-hash의 문서에 설명된 대로 결정됩니다.

위의 동시 수정 주의 사항과 가변 키 주의 사항도 함께 보세요.

package base의 7.4.0.3 버전에서 추가되었습니다.

`hash-ref!`

procedure

(hash-ref! ht key to-set) → any
  ht : hash?
  key : any/c
  to-set : failure-result/c

ht에서 key의 값을 반환합니다. key에 대한 값을 찾지 못하면 to-set이 hash-ref에서처럼 결과를 결정하고(즉, 값을 계산하는 thunk이거나 평범한 값이거나), 이 결과가 key에 대해 ht에 저장됩니다. (to-set이 thunk이면 꼬리 위치에서 호출되지 않는다는 점에 유의하세요.)

위의 동시 수정 주의 사항과 가변 키 주의 사항도 함께 보세요.

`hash-has-key?`

procedure

(hash-has-key? ht key) → boolean?
  ht : hash?
  key : any/c

ht가 주어진 key에 대한 값을 포함하면 #t, 그 외에는 #f를 반환합니다.

`hash-update!`

procedure

(hash-update! ht key updater [failure-result]) → void?
  ht : (and/c hash? (not/c immutable?))
  key : any/c
  updater : (any/c . -> . any/c)
  failure-result : failure-result/c
                 = (lambda () (raise (make-exn:fail:contract ....)))

updater를 값에 적용해 ht에서 key가 매핑한 값을 갱신합니다. updater가 반환하는 값이 key의 새 매핑이 되어 ht의 원래 값을 덮어씁니다.

예시:

(define h (make-hash))
(hash-set! h 'a 5)
> (hash-update! h 'a add1)
> h
'#hash((a . 6))

선택적 failure-result 인자는 key에 대한 매핑이 아직 없을 때 hash-ref에서와 같은 방식으로 사용됩니다.

예시:

(define h (make-hash))
> (hash-update! h 'b add1)
hash-update!: no value found for key: 'b

> (hash-update! h 'b add1 0)
> h
'#hash((b . 1))

위의 동시 수정 주의 사항과 가변 키 주의 사항도 함께 보세요.

`hash-update`

procedure

(hash-update ht key updater [failure-result]) → (and/c hash? immutable?)
  ht : (and/c hash? immutable?)
  key : any/c
  updater : (any/c . -> . any/c)
  failure-result : failure-result/c
                 = (lambda () (raise (make-exn:fail:contract ....)))

updater를 값에 적용하고 새 해시 테이블을 반환해 ht에서 key가 매핑한 값을 함수적으로 갱신합니다. updater가 반환하는 값이 반환된 해시 테이블의 key에 대한 새 매핑이 됩니다.

예시:

(define h (hash 'a 5))
> (hash-update h 'a add1)
'#hash((a . 6))

선택적 failure-result 인자는 key에 대한 매핑이 아직 없을 때 hash-ref에서와 같은 방식으로 사용됩니다.

예시:

(define h (hash))
> (hash-update h 'b add1)
hash-update: no value found for key: 'b

> (hash-update h 'b add1 0)
'#hash((b . 1))

위의 가변 키 주의 사항도 함께 보세요.

`hash-remove!`

procedure

(hash-remove! ht key) → void?
  ht : (and/c hash? (not/c immutable?))
  key : any/c

ht에서 key에 대한 기존 매핑을 제거합니다.

위의 동시 수정 주의 사항과 가변 키 주의 사항도 함께 보세요.

`hash-remove`

procedure

(hash-remove ht key) → (and/c hash? immutable?)
  ht : (and/c hash? immutable?)
  key : any/c

ht에서 key에 대한 기존 매핑을 함수적으로 제거합니다. key가 ht에 없으면 ht(즉 ht와 eq?인 결과)를 반환합니다.

위의 가변 키 주의 사항도 함께 보세요.

`hash-clear!`

procedure

(hash-clear! ht) → void?
  ht : (and/c hash? (not/c immutable?))

ht에서 모든 매핑을 제거합니다.

ht가 impersonator가 아니면 모든 매핑이 상수 시간에 제거됩니다. ht가 impersonator이면 각 키가 hash-remove!를 사용해 하나씩 제거됩니다.

위의 동시 수정 주의 사항과 가변 키 주의 사항도 함께 보세요.

`hash-clear`

procedure

(hash-clear ht) → (and/c hash? immutable?)
  ht : (and/c hash? immutable?)

ht에서 모든 매핑을 함수적으로 제거합니다.

ht가 chaperone이 아니면 비우는 것은 새 해시 테이블을 만드는 것과 동등하고, 연산은 상수 시간에 수행됩니다. ht가 chaperone이면 각 키가 hash-remove를 사용해 하나씩 제거됩니다.

`hash-copy-clear`

procedure

(hash-copy-clear ht [#:kind kind]) → hash?
  ht : hash?
  kind : (or/c #f 'immutable 'mutable 'weak 'ephemeron) = #f

ht와 같은 키 비교 프로시저를 가진 빈 해시 테이블을 만들어냅니다. 주어진 kind로, 또는 주어진 ht와 같은 kind로 만듭니다.

kind가 제공되지 않거나 #f이면 주어진 ht와 같은 kind와 가변성의 해시 테이블을 만들어냅니다. kind가 'immutable, 'mutable, 'weak, 'ephemeron이면 각각 불변이거나, 키를 강하게 보유한 가변이거나, 키를 약하게 보유한 가변이거나, 키를 ephemeron으로 보유한 가변 테이블을 만들어냅니다.

package base의 8.5.0.2 버전에서 변경: kind 인자가 추가되었습니다.

`hash-map`

procedure

(hash-map ht proc [try-order?]) → (listof any/c)
  ht : hash?
  proc : (any/c any/c . -> . any/c)
  try-order? : any/c = #f

프로시저 proc을 ht의 각 요소에 지정되지 않은 순서로 적용하고, 결과를 리스트로 축적합니다. 프로시저 proc은 매번 키와 그 값으로 호출되고, 프로시저의 개별 결과는 결과 리스트에 순서대로 나타납니다.

hash-map 또는 hash-for-each 순회가 진행되는 동안 해시 테이블이 (proc을 통해서든 다른 스레드에 의해서든) 새 키로 확장되면, 임의의 키-값 쌍이 순회에서 떨어지거나 중복될 수 있습니다. 키 매핑은 (어느 스레드에 의해서든) 부작용 없이 삭제되거나 재매핑될 수 있습니다. 그 변경은 키를 이미 본 경우에는 순회에 영향을 주지 않고, 그 외에는 순회가 삭제된 키를 건너뛰거나 재매핑된 키의 새 값을 사용합니다.

위의 동시 수정 주의 사항도 함께 보세요.

try-order?가 참이면 proc에 전달되는 키와 값의 순서는 특정 상황에서 정규화됩니다—모든 키가 다음 중 하나일 때와 다음 순서로(앞의 불릿이 뒤보다 먼저):

불리언 — #f가 #t보다 먼저 정렬
문자 — char<?로 정렬
실수 — <로 정렬
심볼 — 인터닝되지 않은 심볼, 읽을 수 없는 심볼, 인터닝된 심볼 순으로 먼저, 그 다음 symbol<?로 정렬
키워드 — keyword<?로 정렬
문자열 — string<?로 정렬
바이트 문자열 — bytes<?로 정렬
null
#<void>
eof

package base의 6.3 버전에서 변경: try-order? 인자가 추가되었습니다. 7.1.0.7 버전에서 변경: try-order?에 대한 보장이 추가되었습니다.

예시:

> (hash-map (make-hash '([0 . 1] [1 . 2] [2 . 3])) (λ (k v) k))
'(0 1 2)

> (hash-map (make-hash '([0 . 1] [1 . 2] [2 . 3])) (λ (k v) v))
'(1 2 3)

`hash-map/copy`

procedure

(hash-map/copy ht proc [#:kind kind]) → hash?
  ht : hash?
  proc : (any/c any/c . -> . (values any/c any/c))
  kind : (or/c #f 'immutable 'mutable 'weak 'ephemeron) = #f

프로시저 proc을 ht의 각 요소에 지정되지 않은 순서로 적용하고, 결과를 ht와 같은 키 비교 프로시저를 가진 새 해시에 축적합니다. 주어진 kind로, 또는 주어진 ht와 같은 kind로 만듭니다.

예시:

> (hash-map/copy #hash((a . "apple") (b . "banana"))
                 (lambda (k v) (values k (string-upcase v))))
'#hash((a . "APPLE") (b . "BANANA"))

> (define frozen-capital
    (hash-map/copy (make-hash '((a . "apple") (b . "banana")))
                   (lambda (k v) (values k (string-upcase v)))
                   #:kind 'immutable))
> frozen-capital
'#hash((a . "APPLE") (b . "BANANA"))

> (immutable? frozen-capital)
#t

package base의 8.5.0.2 버전에서 추가되었습니다.

`hash-keys`

procedure

(hash-keys ht [try-order?]) → (listof any/c)
  ht : hash?
  try-order? : any/c = #f

지정되지 않은 순서로 ht의 키 리스트를 반환합니다.

try-order?가 참이면 키의 순서는 특정 상황에서 정규화됩니다. try-order?와 hash-keys 동안 ht를 수정하는 것에 대한 정보는 hash-map을 참고하세요.

위의 동시 수정 주의 사항도 함께 보세요.

package base의 8.3.0.11 버전에서 변경: try-order? 인자가 추가되었습니다.

`hash-values`

procedure

(hash-values ht [try-order?]) → (listof any/c)
  ht : hash?
  try-order? : any/c = #f

지정되지 않은 순서로 ht의 값 리스트를 반환합니다.

try-order?가 참이면 값의 순서는 연관된 키의 순서에 기반해 특정 상황에서 정규화됩니다. try-order?와 hash-values 동안 ht를 수정하는 것에 대한 정보는 hash-map을 참고하세요.

위의 동시 수정 주의 사항도 함께 보세요.

package base의 8.3.0.11 버전에서 변경: try-order? 인자가 추가되었습니다.

`hash->list`

procedure

(hash->list ht [try-order?]) → (listof (cons/c any/c any/c))
  ht : hash?
  try-order? : any/c = #f

지정되지 않은 순서로 ht의 키-값 쌍 리스트를 반환합니다.

try-order?가 참이면 키와 값의 순서는 특정 상황에서 정규화됩니다. try-order?와 hash->list 동안 ht를 수정하는 것에 대한 정보는 hash-map을 참고하세요.

위의 동시 수정 주의 사항도 함께 보세요.

package base의 8.3.0.11 버전에서 변경: try-order? 인자가 추가되었습니다.

`hash-keys-subset?`

procedure

(hash-keys-subset? ht1 ht2) → boolean?
  ht1 : hash?
  ht2 : hash?

ht1의 키가 ht2의 키의 부분집합이거나 같으면 #t를 반환합니다. 두 해시 테이블은 반드시 같은 키 비교 함수(equal?, equal-always?, eqv?, 또는 eq?)를 사용해야 하며, 그렇지 않으면 exn:fail:contract 예외가 발생합니다.

불변 해시 테이블에 hash-keys-subset?를 사용하는 것은 각 키가 ht2에 있는지 확인하기 위해 ht1의 키를 반복하는 것보다 훨씬 빠를 수 있습니다.

package base의 6.5.0.8 버전에서 추가되었습니다.

`hash-for-each`

procedure

(hash-for-each ht proc [try-order?]) → void?
  ht : hash?
  proc : (any/c any/c . -> . any)
  try-order? : any/c = #f

proc을 ht의 각 요소에 (proc의 부작용을 위해) 지정되지 않은 순서로 적용합니다. 프로시저 proc은 매번 키와 그 값으로 호출됩니다.

try-order?와 proc 안에서 ht를 수정하는 것에 대한 정보는 hash-map을 참고하세요.

위의 동시 수정 주의 사항도 함께 보세요.

package base의 6.3 버전에서 변경: try-order? 인자가 추가되었습니다. 7.1.0.7 버전에서 변경: try-order?에 대한 보장이 추가되었습니다.

`hash-count`

procedure

(hash-count ht) → exact-nonnegative-integer?
  ht : hash?

ht가 매핑한 키의 개수를 반환합니다.

Racket의 CS 구현체에서 결과는 항상 상수 시간에 원자적으로 계산됩니다. Racket의 BC 구현체에서 결과는 ht가 키를 약하게 또는 ephemeron처럼 보유하지 않을 때만 상수 시간에 원자적으로 계산되고, 그 외에는 키를 세기 위해 순회가 필요합니다.

`hash-empty?`

procedure

(hash-empty? ht) → boolean?
  ht : hash?

(zero? (hash-count ht))와 동등합니다.

`hash-iterate-first`

procedure

(hash-iterate-first ht) → (or/c #f exact-nonnegative-integer?)
  ht : hash?

ht가 요소를 포함하지 않으면 #f, 그 외에는 해시 테이블의 첫 번째 요소에 대한 인덱스인 정수를 반환합니다. "first"는 테이블 요소의 미지정된 순서를 말하며, 인덱스 값은 반드시 연속된 정수일 필요는 없습니다.

가변 ht에 대해, 이 인덱스는 ht에 항목이 추가되거나 제거되지 않는 한 첫 번째 항목을 가리킴이 보장됩니다. 더 일반적으로, 인덱스는 hash-iterate-first나 hash-iterate-next에서 나온 경우에만, 그리고 해시 테이블이 수정되지 않는 동안에만 주어진 해시 테이블에 대한 유효한 해시 인덱스임이 보장됩니다. 키를 약하게 보유하거나 ephemeron처럼 보유하는 해시 테이블의 경우, 가비지 컬렉터(Garbage Collection 참고)가 키가 도달 불가능함을 발견하면 해시 테이블이 암묵적으로 수정될 수 있습니다.

`hash-iterate-next`

procedure

(hash-iterate-next ht pos) → (or/c #f exact-nonnegative-integer?)
  ht : hash?
  pos : exact-nonnegative-integer?

ht에서 pos가 가리키는 요소 다음 요소에 대한 인덱스인 정수(반드시 pos보다 1 큰 것은 아님)를 반환하거나, pos가 ht의 마지막 요소를 가리키면 #f를 반환합니다.

pos가 ht의 유효한 해시 인덱스가 아니면 결과는 #f이거나 유효한 다음 인덱스일 수 있습니다. 후자의 결과는 해시 테이블이 키 제거에 의해서만 수정된 경우 보장됩니다.

package base의 7.0.0.10 버전에서 변경: exn:fail:contract를 발생시키는 대신 #f를 반환해 잘못된 인덱스를 처리합니다.

`hash-iterate-key`

procedure

(hash-iterate-key ht pos) → any/c
  ht : hash?
  pos : exact-nonnegative-integer?

(hash-iterate-key ht pos bad-index-v) → any/c
  ht : hash?
  pos : exact-nonnegative-integer?
  bad-index-v : any/c

인덱스 pos에서 ht의 요소에 대한 키를 반환합니다.

pos가 ht의 유효한 해시 인덱스가 아니면 결과는 제공되면 bad-index-v, 그 외에는 exn:fail:contract 예외가 발생합니다.

package base의 7.0.0.10 버전에서 변경: 선택적 bad-index-v 인자가 추가되었습니다.

`hash-iterate-value`

procedure

(hash-iterate-value ht pos) → any/c
  ht : hash?
  pos : exact-nonnegative-integer?

(hash-iterate-value ht pos bad-index-v) → any/c
  ht : hash?
  pos : exact-nonnegative-integer?
  bad-index-v : any/c

인덱스 pos에서 ht의 요소에 대한 값을 반환합니다.

pos가 ht의 유효한 해시 인덱스가 아니면 결과는 제공되면 bad-index-v, 그 외에는 exn:fail:contract 예외가 발생합니다.

package base의 7.0.0.10 버전에서 변경: 선택적 bad-index-v 인자가 추가되었습니다.

`hash-iterate-pair`

procedure

(hash-iterate-pair ht pos) → (cons/c any/c any/c)
  ht : hash?
  pos : exact-nonnegative-integer?

(hash-iterate-pair ht pos bad-index-v) → (cons/c any/c any/c)
  ht : hash?
  pos : exact-nonnegative-integer?
  bad-index-v : any/c

인덱스 pos에서 ht의 요소에 대한 키와 값을 담은 쌍을 반환합니다.

pos가 ht의 유효한 해시 인덱스가 아니면 결과는 제공되면 (cons bad-index-v bad-index-v), 그 외에는 exn:fail:contract 예외가 발생합니다.

package base의 6.4.0.5 버전에서 추가되었습니다. 7.0.0.10 버전에서 변경: 선택적 bad-index-v 인자가 추가되었습니다.

`hash-iterate-key+value`

procedure

(hash-iterate-key+value ht pos) → any/c any/c
  ht : hash?
  pos : exact-nonnegative-integer?

(hash-iterate-key+value ht pos bad-index-v) → any/c any/c
  ht : hash?
  pos : exact-nonnegative-integer?
  bad-index-v : any/c

인덱스 pos에서 ht의 요소에 대한 키와 값을 반환합니다.

pos가 ht의 유효한 해시 인덱스가 아니면 결과는 제공되면 (values bad-index-v bad-index-v), 그 외에는 exn:fail:contract 예외가 발생합니다.

package base의 6.4.0.5 버전에서 추가되었습니다. 7.0.0.10 버전에서 변경: 선택적 bad-index-v 인자가 추가되었습니다.

`hash-copy`

procedure

(hash-copy ht) → (and/c hash? (not/c immutable?))
  ht : hash?

ht와 같은 매핑, 같은 키 비교 모드, 같은 키 보유 강도를 가진 가변 해시 테이블을 반환합니다.

추가 해시 테이블 함수(Additional Hash Table Functions)

(require racket/hash)    ; package: base

이 절에서 문서화하는 바인딩은 racket/base나 racket이 아니라 racket/hash 라이브러리가 제공합니다.

`hash-union`

procedure

(hash-union ht0 ht ...
  [#:combine combine #:combine/key combine/key])
 → (and/c hash? immutable?)
  ht0 : (and/c hash? immutable?)
  ht : hash?
  combine : (-> any/c any/c any/c) = (lambda _ (error 'hash-union ....))
  combine/key : (-> any/c any/c any/c any/c) = (lambda (k a b) (combine a b))

함수적 갱신으로 ht0과 각 해시 테이블 ht의 합집합을 계산하고, 각 ht의 각 요소를 차례로 ht0에 추가합니다. 각 키 k와 값 v에 대해, k에서 어떤 값 v0로의 매핑이 이미 있으면 그것은 k에서 (combine/key k v0 v)로의 매핑으로 대체됩니다.

예시:

> (hash-union (make-immutable-hash '([1 . one]))
              (make-immutable-hash '([2 . two]))
              (make-immutable-hash '([3 . three])))
'#hash((1 . one) (2 . two) (3 . three))

> (hash-union (make-immutable-hash '([1 one uno] [2 two dos]))
              (make-immutable-hash '([1 eins un] [2 zwei deux]))
              #:combine/key (lambda (k v1 v2) (append v1 v2)))
'#hash((1 . (one uno eins un)) (2 . (two dos zwei deux)))

`hash-union!`

procedure

(hash-union! ht0 ht ...
  [#:combine combine #:combine/key combine/key]) → void?
  ht0 : (and/c hash? (not/c immutable?))
  ht : hash?
  combine : (-> any/c any/c any/c) = (lambda _ (error 'hash-union ....))
  combine/key : (-> any/c any/c any/c any/c) = (lambda (k a b) (combine a b))

가변 갱신으로 ht0과 각 해시 테이블 ht의 합집합을 계산하고, 각 ht의 각 요소를 차례로 ht0에 추가합니다. 각 키 k와 값 v에 대해, k에서 어떤 값 v0로의 매핑이 이미 있으면 그것은 k에서 (combine/key k v0 v)로의 매핑으로 대체됩니다.

예시:

> (define h (make-hash))
> h
'#hash()

> (hash-union! h (make-immutable-hash '([1 one uno] [2 two dos])))
> h
'#hash((1 . (one uno)) (2 . (two dos)))

> (hash-union! h
               (make-immutable-hash '([1 eins un] [2 zwei deux]))
               #:combine/key (lambda (k v1 v2) (append v1 v2)))
> h
'#hash((1 . (one uno eins un)) (2 . (two dos zwei deux)))

`hash-intersect`

procedure

(hash-intersect ht0 ht ...
  [#:combine combine #:combine/key combine/key])
 → (and/c hash? immutable?)
  ht0 : (and/c hash? immutable?)
  ht : hash?
  combine : (-> any/c any/c any/c) = (lambda _ (error 'hash-intersect ...))
  combine/key : (-> any/c any/c any/c any/c) = (lambda (k a b) (combine a b))

ht0과 모든 해시 테이블 ht의 교집합인 해시 테이블을 구성합니다. 결과 해시 테이블에서 키 k는 각 해시 테이블에서 k가 매핑된 값들의 조합에 매핑됩니다. 최종 값은 각 해시 테이블에 나타나는 값들을 (combine/key k v vi)를 적용해 단계적으로 조합해 계산됩니다. 여기서 vi는 i번째 해시 테이블 ht에서 k가 매핑된 값이고, v는 이전 단계들의 값 축적입니다. 첫 번째 인자의 비교 술어(eq?, eqv?, equal-always?, equal?)가 결과의 것을 결정합니다.

예시:

> (hash-intersect (make-immutable-hash '((a . 1) (b . 2) (c . 3)))
                  (make-immutable-hash '((a . 4) (b . 5)))
                  #:combine +)
'#hash((a . 5) (b . 7))

> (hash-intersect (make-immutable-hash '((a . 1) (b . 2) (c . 3)))
                  (make-immutable-hash '((a . 4) (b . 5)))
                  #:combine/key
                  (lambda (k v1 v2) (if (eq? k 'a) (+ v1 v2) (- v1 v2))))
'#hash((a . 5) (b . -3))

package base의 7.9.0.1 버전에서 추가되었습니다.

`hash-filter`

procedure

(hash-filter ht pred) → hash?
  ht : hash?
  pred : (-> any/c any/c boolean?)

키와 값 둘 다에 적용되는 술어 pred에 기반해 hash? ht를 필터링합니다. 이 함수는 입력 ht에서 술어 pred가 키와 값에 동시 적용될 때 참을 반환하는 키-값 쌍만 포함하는 새 해시 테이블을 구성합니다. 출력 해시 테이블은 입력 해시 테이블 ht의 가변성과 키 비교 술어(예: eqv?, equal-always?, equal?)를 유지해, 원래 해시의 구조적·작동적 속성이 출력에서 보존되도록 합니다.

예시:

> (hash-filter (for/hash ([num '(1 2 3 4 5)]) (values num (* num 2)))
               (λ (k v) (and (< k 3) (even? v))))
'#hash((1 . 2) (2 . 4))

> (hash-filter (make-hash) (λ (k v) (< k 3)))
'#hash()

> (hash-filter (make-hasheq '([#f . "false"] [#t . "true"]))
               (λ (k v) (and (eq? k #t) (string=? v "true"))))
'#hasheq((#t . "true"))

> (hash-filter (hash (list 1 2) 'pair (vector 3 4) 'vector)
               (λ (k v) (and (list? k) (symbol? v))))
'#hash(((1 2) . pair))

> (hash-filter (hash "one" 1 2 "two" "three" 3)
               (λ (k v) (and (not (number? k)) (number? v) (> v 1))))
'#hash(("three" . 3))

package base의 8.13.0.4 버전에서 추가되었습니다.

`hash-filter-keys`

procedure

(hash-filter-keys ht pred) → hash?
  ht : hash?
  pred : procedure?

그 키에 적용되는 술어 pred에 기반해 hash? ht를 필터링합니다. 이 함수는 입력 ht에서 술어 pred가 키에 적용될 때 참을 반환하는 키-값 쌍만 포함하는 새 해시 테이블을 구성합니다. hash-filter-values와 유사하게, 출력 해시 테이블은 입력 해시 테이블의 가변성과 키 비교자를 유지해, 원래 해시의 구조적·작동적 속성이 유지되도록 합니다.

예시:

> (hash-filter-keys (for/hash ([num '(1 2 3 4 5)]) (values num 0)) (λ (k) (< k 3)))
'#hash((1 . 0) (2 . 0))

> (hash-filter-keys (make-hash) (λ (k) (< k 3)))
'#hash()

> (hash-filter-keys (make-hasheq '([#f . "false"] [#t . "true"])) (λ (k) (eq? k #t)))
'#hasheq((#t . "true"))

> (hash-filter-keys (hash (list 1 2) 'pair (vector 3 4) 'vector) list?)
'#hash(((1 2) . pair))

> (hash-filter-keys (hash "one" 1 2 "two" "three" 3) (lambda (k) (number? k)))
'#hash((2 . "two"))

> (hash-filter-keys (hash 'apple "fruit" 'carrot "vegetable" "banana" "fruit")
                    (lambda (k) (symbol? k)))
'#hash((apple . "fruit") (carrot . "vegetable"))

package base의 8.12.0.9 버전에서 추가되었습니다.

`hash-filter-values`

procedure

(hash-filter-values ht pred) → hash?
  ht : hash?
  pred : procedure?

그 값에 적용되는 술어 pred에 기반해 hash? ht를 필터링합니다. 이 함수는 술어 pred가 ht의 값에 적용될 때 참을 반환하는 키-값 쌍만 포함하는 새 해시 테이블을 반환합니다. 결과 해시 테이블은 입력 해시 테이블 ht의 가변성과 키 비교 술어(예: eq?, eqv?, equal-always?, equal?)를 유지합니다.

예시:

> (hash-filter-values (for/hash ([num '(1 2 3 4 5)]) (values num num)) (λ (v) (< v 3)))
'#hash((1 . 1) (2 . 2))

> (hash-filter-values (make-hash) (λ (v) (< v 3)))
'#hash()

> (hash-filter-values (make-hasheqv '([1 . "one"] [2 . "two"])) (λ (v) (eqv? v "two")))
'#hasheqv((2 . "two"))

> (hash-filter-values (hash 'one "1" 'two 2 'three "3") (lambda (v) (string? v)))
'#hash((one . "1") (three . "3"))

> (hash-filter-values (hash 'list (list 1 2 3) 'vector #(4 5 6) 'string "hello")
                      (lambda (v) (vector? v)))
'#hash((vector . #(4 5 6)))

> (hash-filter-values (hash 'nested-hash (hash 'a 1 'b 2) 'nested-list (list 'x 'y 'z))
                      (lambda (v) (hash? v)))
'#hash((nested-hash . #hash((a . 1) (b . 2))))

package base의 8.12.0.9 버전에서 추가되었습니다.

해시 테이블(Hash Tables)