«جدول هش» در Factor یک آرایهی انجمنی است؛ مجموعهای از جفتهای key/value با زمان جستوجوی O(1). جدول هش بخشی از خانوادهی بزرگتر assocs است.
H{ { "coal" 1 } { "wood" 2 } } .
H{ } یک جدول هش خالی است. جدولهای هش تغییرپذیرند و با افزودن و حذف کلیدها بزرگ و کوچک میشوند؛ اگر میخواهید نسخهی اصلی دستنخورده بماند، اول clone کنید. چاپ یک جدول هش، درایههایش را نشان میدهد، اما ترتیبش به ترتیب درج وابسته نیست: جدول هش ترتیبی ندارد.
at (در assocs) یک مقدار را میخواند و اگر کلید نبود، f را برمیگرداند:
at ( key assoc -- value/f )
key? ( key assoc -- ? )
"coal" H{ { "coal" 1 } { "wood" 2 } } at . ! => 1
"gold" H{ { "coal" 1 } { "wood" 2 } } at . ! => f
set-at اضافه یا بازنویسی میکند؛ delete-at حذف میکند؛ change-at یک قطعهکد را روی مقدار فعلی اجرا میکند. هر سه جدول را در جا تغییر میدهند:
set-at ( value key assoc -- )
delete-at ( key assoc -- )
change-at ( key assoc quot: ( old -- new ) -- )
H{ } clone 5 "coal" pick set-at .
! => H{ { "coal" 5 } }
inc-at، میانبر شمارشinc-at (که در assocs هم هست) به مقدار موجود برای یک کلید ۱ واحد اضافه میکند و اگر کلید نبود، آن را با مقدار ۱ درج میکند. برای شمارش، عالی است:
inc-at ( key assoc -- )
H{ } clone "coal" over inc-at .
! => H{ { "coal" 1 } }
assoc-each روی همهی جفتهای ( key value -- ) حرکت میکند؛ cache مقدار یک کلید را برمیگرداند و اگر کلید نبود، آن را یکبار با قطعهکد دادهشده محاسبه میکند.
assoc-each ( assoc quot: ( key value -- ) -- )
cache ( key assoc quot: ( key -- value ) -- value )
cache الگوی «جستوجو یا ساختن» را در یک واژه خلاصه میکند؛ وقتی از جریانی از کلیدها جدول هش میسازید و نمیخواهید در هر نقطهی فراخوانی حالت نبودن درایه را رسیدگی کنید، به کار میآید.
وقتی ورودی دنبالهای از کلیدهاست و میخواهید جدول هش را برای هر کلید یکبار بهروزرسانی کنید، روی خود دنباله با each پیمایش کنید و از یک قطعهکد سرخشده به شکل '[ _ … ] (از fry) استفاده کنید تا جدول هش را در بدنهی حلقه جای دهید. برای نمونه، حذف فهرستی از کلیدها:
{ "wood" "iron" } H{ { "coal" 5 } { "wood" 3 } { "iron" 2 } } clone
[ '[ _ delete-at ] each ] keep .
! => H{ { "coal" 5 } }
'[ _ delete-at ] جدول هشی را که بالاتر از آن روی پشته است در بر میگیرد، تا در هر تکرار each فقط کلید را بدهد. keep قطعهکد را اجرا میکند و در همان حال جدول هش را برای . نهایی نگه میدارد.
map>assoc (در assocs) یک قطعهکد را روی یک دنباله اعمال میکند و نتایج ( elt -- key value ) را در یک assoc از نوع نمونه گرد میآورد:
map>assoc ( seq quot: ( elt -- key value ) exemplar -- assoc )
{ "wood" } [ dup length ] H{ } map>assoc .
! => H{ { "wood" 4 } }
keys و values (در assocs) فقط کلیدها یا فقط مقدارها را برمیگردانند؛ >alist جفتهای { key value } را برمیگرداند.
keys ( assoc -- keys )
values ( assoc -- values )
>alist ( assoc -- alist )
H{ { "wood" 11 } { "coal" 7 } } keys . ! the keys (order not guaranteed)
H{ { "wood" 11 } { "coal" 7 } } values . ! the matching values
keys و values همترازند: مقدار در یک جایگاه، به کلید در همان جایگاه تعلق دارد.
sort-keys (در sorting) جفتهای { key value } را بهترتیب کلید برمیگرداند:
H{ { "wood" 11 } { "coal" 7 } } sort-keys .
! => { { "coal" 7 } { "wood" 11 } }
>hashtable (در hashtables) وارون >alist است: هر assoc را، که بیشتر وقتها یک alist از جفتهای { key value } است، به جدول هشی با جستوجوی O(1) تبدیل میکند.
>hashtable ( assoc -- hashtable )
{ { "coal" 7 } { "wood" 11 } } >hashtable .
! => H{ { "wood" 11 } { "coal" 7 } } (entry order not guaranteed)
وقتی فهرستی از جفتها را سرهم کردهاید یا تغییر دادهاید و میخواهید دوباره آن را به جدول هش برگردانید تا درایهها را با کلید جستوجو کنید، به کار میآید.
شما مسئول تدارکات کشتی هستید و موجودی انبار آذوقه را مدیریت میکنید. موجودی یک «هشتیبل» است که در آن هر کلید اسم یک قلم کالا و هر مقدار تعداد آن در انبار است.
create-inventory را طوری تعریف کنید که دنبالهای از اسم اقلام را بگیرد و یک هشتیبل برگرداند که هر اسم یکتا را با تعدادش جفت میکند.
{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }
add-items را طوری تعریف کنید که یک موجودی و دنبالهای از اقلام را بگیرد و موجودی تازهای برگرداند که در آن تعداد هر قلمی که در فهرست آمده، افزایش یافته است. موجودی اصلی نباید تغییر کند.
H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }
decrement-items را طوری تعریف کنید که یک موجودی و دنبالهای از اقلام را بگیرد و موجودی تازهای برگرداند که در آن تعداد هر قلمی که در فهرست آمده، یک واحد کاهش یافته است. تعدادها هرگز نباید به زیر صفر برسند و اقلامی که از قبل در موجودی نیستند باید نادیده گرفته شوند (هیچ ورودی منفیای درج نمیشود).
H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }
remove-item را طوری تعریف کنید که یک موجودی و یک قلم را بگیرد و موجودی تازهای برگرداند که آن قلم از آن حذف شده است. اگر آن قلم در موجودی نباشد، یک نسخهی بدون تغییر برگردانید.
H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }
list-inventory را طوری تعریف کنید که یک موجودی را بگیرد و آرایهای از جفتهای { name quantity } برگرداند که فقط اقلامی را شامل میشود که مقدارشان بیشتر از صفر است و این جفتها بر اساس اسم به ترتیب الفبا مرتب شدهاند.
H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }