燈塔航海日誌

雜湊集合是可變的無序集合，每個值最多只儲存一次。查找、插入和刪除的平均時間複雜度都是 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，而不是雜湊集合。

為什麼這很重要

雜湊集合和雜湊表在圖形走訪上是天生的搭檔：雜湊表把每個節點對應到它的相鄰節點，雜湊集合則記錄哪些節點已經走訪過，讓搜尋不會打轉或重複做白工。走訪本身則是一個佇列加上這兩個結構，在你向外掃描的過程中就地修改。