The Racket Reference阅读笔记。

4.14 Hash Tables

哈希表将键值映射到项值。同一个哈希表内，键值的等同性可用equal?, eqv? 或者 eq?来判断。键值可以是强保留弱保留（采用弱封箱），甚至是暂保留。哈希表也可以是可更改的，或者非更改的。可更改以及非更改的的哈希表都支持高效的常态时间内的访问和更新。但是非更改的哈希表上的操作需要更长的操作时间。

非更改的哈希表的效率在O(logN)

基于equal?的哈希表，其哈希功用作用在字符串，子对，连对，串列，预制或者透明结构时，操作时间跟量值成正比。对于复合数据类型，比如连对或者串列，对其子项进行递归哈希的深度是有限的。对于非连结子对，对于car和cdr的哈希操作被看作是更深一层的哈希；但是对于连结子对，对于cdr的哈希的深度与当前连对一致。

一个哈希表可以用作一个二值序列。哈希表的键值和项值共同构成序列的元素。如果遍历此序列的过程中，从中添加或者删除了元素，那么可能导致失败，从而抛出异常exn:fail:contract，也有可能导致跳过某未遍历的项，或者重复某已遍历的项。参考：in-hash、in-hash-keys、in-hash-values、in-hash-pairs。

两个哈希表equal?判定成功需要它们具有相同的变更性，每个项等同，键值同为强、弱或者暂保留。空哈希表在euqal?判定成功的时候，eq?的判定也会成功。

可更改的哈希表可以使用hash-ref, hash-set!以及hash-remove!来多线程并发操作，其底层实现有系统信号量，所以不会有访问冲突问题，但是下面一些点需要考量

  • 如果线程在应用hash-ref, hash-ref-key, hash-set!, hash-remove!, hash-ref!, hash-update!或者hash-clear!的时候终结，以及哈希表的对比使用的是equal?或者eqv?，那么在此哈希表上当前以及未来的操作将会无限期阻塞
  • hash-map, hash-for-each以及hash-clear!并未使用信号量来保护，所以会受其他线程对此哈希表的操作的影响
  • hash-update!以及hash-ref!功用使用的信号量有别于hash-ref以及hash-set!所使用的信号量，所以更新操作并不是真正原子的
  • 如果把可变更哈希表本身作为键值插入另外一个哈希表可能会有意想不到的麻烦，比如计算哈希表的哈希码需要获取作为键值的哈希表的信号量，从何和其他操作发生冲突。

对于键值变更的考虑

  • 在一个使用equal?来做对比的哈希表中，如果一个键值被更改了（作为键值的字符串被string-set!更改了），那么哈希表的行为，特别是插入和查找操作上，会变得不可预测。

字面显示或者打印出来的哈希表有三种开头#hash，#hasheqv，或者#hasheq。

相关操作：

  • (hash? v)
  • (hash-equal? hash)，是否采用equal?
  • (hash-eqv? hash)
  • (hash-eq? hash)
  • (hash-strong? hash)，是否采用强键值
  • (hash-weak? hash)
  • (hash-ephemeron? hash)
  • (hash key val ... ...)，创建非变更的哈希表
  • (hasheq key val ... ...)
  • (hasheqv key val ... ...)
  • (make-hash [assocs])，创建可变更的哈希表
  • (make-hasheqv [assocs])
  • (make-hasheq [assocs])
  • (make-weak-hash [assocs])，创建弱键值的可变更哈希表
  • (make-weak-hasheqv [assocs])
  • (make-weak-hasheq [assocs])
  • (make-ephemeron-hash [assocs])，创建暂键值的可变更哈希表
  • (make-ephemeron-hasheqv [assocs])
  • (make-ephemeron-hasheq [assocs])
  • (make-immutable-hash [assocs])，同(hash)
  • (make-immutable-hasheqv [assocs])
  • (make-immutable-hasheq [assocs])
  • (hash-set! hash key v)，将键值key映射到项值v，覆盖存项
  • (hash-set*! hash key v ... ...)
  • (hash-set hash key v)，扩展一个非变更哈希表
  • (hash-set* hash key v ... ...)
  • (hash-ref hash key [failure-result])，从哈希表中提取项值
  • (hash-ref-key hash key [failure-result])，从哈希表中提取键值
  • (hash-ref! hash key to-set) ，找不到便设置
  • (hash-has-key? hash key)，键值存在判定
  • (hash-update! hash key updater ...)，hash-ref以及hash-set!的复合操作，用于更新既存项，用于可变更哈希
  • (hash-update hash key updater ...)，hash-ref以及hash-set的复合操作，用于非变更哈希
  • (hash-remove! hash key)，删除某存项
  • (hash-remove hash key)
  • (hash-clear! hash)，清除全部存项
  • (hash-clear hash)
  • (hash-copy-clear hash) ，派生出空的新哈希表
  • (hash-map hash proc [try-order?])，以非特定顺序遍历哈希表
  • (hash-keys hash)，返回键值连对
  • (hash-values hash)，返回所有项值
  • (hash->list hash)
  • (hash-keys-subset? hash1 hash2)，结果为真值，如果hash1的键值集合是hash2键值集合的子集
  • (hash-for-each hash proc [try-order?])
  • (hash-count hash)，返回存项数目
  • (hash-empty? hash)
  • (hash-iterate-first hash)，如果哈希表非空，则返回初遇项；否则返回#f。具体那个项会成为初遇项则没有明确定义
  • (hash-iterate-next hash pos)，给出pos对应存项的下一个存项。
  • (hash-iterate-key hash pos)
  • (hash-iterate-key hash pos bad-index-v)
  • (hash-iterate-value hash pos)
  • (hash-iterate-value hash pos bad-index-v)
  • (hash-iterate-pair hash pos)
  • (hash-iterate-pair hash pos bad-index-v)
  • (hash-iterate-key+value hash pos)
  • (hash-iterate-key+value hash pos bad-index-v)
  • (hash-copy hash)拷贝一个可变更哈希表

4.14.1 Additional Hash Table Functions

需要求访(require racket/hash)。

  • hash-union，计算非变更哈希表的并集
  • hash-union!，计算可变更哈希表的并集
  • hash-intersect，计算非变更哈希表的交集

（本篇完）