灯塔日志

哈希集合是一种可变的、无序的集合，每个值最多只存储一次。查找、插入和删除的平均复杂度都是 O(1)。它们位于hash-sets中，并实现了sets的协议。

哈希集合字面量

HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }

HS{ }是空字面量。和其他 Factor 字面量一样，它是一个共享对象：源代码中每一处对HS{ }的引用都指向同一个集合。每次调用HS{ } clone都会得到一份全新的独立副本。

从序列构建

>hash-set ( seq -- set )    ! build a fresh set from a sequence

当你已经把值放在一个序列里时，>hash-set会一步把它们转换过来，并去掉所有重复项。

USING: hash-sets prettyprint ;

{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }

添加与删除

adjoin     ( elt set -- )    ! insert in place; no-op if already present
adjoin-all ( seq set -- )    ! insert every element of seq in place
delete     ( elt set -- )    ! remove in place; no-op if absent

这三个操作都会就地修改集合，都不会在栈上返回任何东西。

USING: hash-sets kernel sets ;

HS{ } clone
"NS-1024" over adjoin
"WB-203"  over adjoin
"NS-1024" over adjoin    ! duplicate — no effect
.                        ! => HS{ "NS-1024" "WB-203" }

adjoin-all是批量形式：它会把一个序列中的每个元素都加入集合，遇到重复项就跳过，就像adjoin一次加入一个元素时那样。

USING: hash-sets kernel sets ;

HS{ "NS-1024" } clone
{ "WB-203" "NS-1024" "QR-7" } over adjoin-all
.                        ! => HS{ "QR-7" "NS-1024" "WB-203" }  (order not guaranteed)

查询集合

in?         ( elt set -- ? )   ! is elt in the set?
null?       ( set -- ? )       ! is the set empty?
cardinality ( set -- n )       ! number of elements
members     ( set -- seq )     ! enumerate as a sequence

in?是集合协议的成员测试。它和member?（来自sequences）不同，后者会对序列做一次线性扫描。对哈希集合来说，in?是一次哈希查找，平均复杂度 O(1)，这正是使用哈希集合的意义所在。

null?报告集合是否没有任何元素，这是直接询问“这个集合是空的吗？”的方式，而不用把cardinality和零作比较。

: my-log ( -- set ) HS{ "NS-1024" "WB-203" } ;

"NS-1024" my-log in? .   ! => t
"X-99"    my-log in? .   ! => f
my-log null? .           ! => f
HS{ } clone null? .      ! => t
my-log cardinality .     ! => 2

合并集合

union     ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff      ( set1 set2 -- set )
set-like  ( set exemplar -- set' )

union是“来自两者中任意一个的所有元素”；intersect是“同时存在于两者中的元素”；diff是“在set1中但不在set2中的元素”。每个操作都返回一个新集合，不会修改输入。

set-like会把set强制转换为exemplar的类型。union/intersect/diff的默认实现会用它让结果的类型与接收者一致：<my-set> <hash-set> union返回的是my-set，而不是哈希集合。

为什么这很重要

哈希集合很适合和哈希表搭配来做图遍历：哈希表把每个节点映射到它的邻居，哈希集合则记录哪些节点已经访问过，这样搜索就不会绕圈，也不会重复做无用功。于是遍历就是一个队列加上这两个结构，在你向外扫描的过程中就地修改。