Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/unix/volume26/db-1.6/part08

Text File | 1993-07-05 | 80.3 KB | 6,128 lines

Newsgroups: comp.sources.unix
From: [e-mail] (Keith Bostic)
Subject: v26i287: db-1.6 - A New Hashing Package for UNIX(tm) (updates dbm/ndbm), Part08/09
Sender: [e-mail]
Approved: [e-mail]

Submitted-By: [e-mail] (Keith Bostic)
Posting-Number: Volume 26, Issue 287
Archive-Name: db-1.6/part08

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 8 (of 9)."
# Contents:  doc/hash.ps.02
# Wrapped by [e-mail] on Mon Jul  5 15:27:30 1993
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'doc/hash.ps.02' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'doc/hash.ps.02'\"
else
echo shar: Extracting \"'doc/hash.ps.02'\" \(74476 characters\)
sed "s/^X//" >'doc/hash.ps.02' <<'END_OF_FILE'
X%%Page: 7 7
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X720 258(Seltzer)N
X977(&)X
X1064(Yigit)X
X3278(A)X
X3356(New)X
X3528(Hashing)X
X3831(Package)X
X4136(for)X
X4259(UNIX)X
X1 f
X720 538(cannot)N
X955(be)X
X1052(present)X
X1305(in)X
X1388(the)X
X1507(buffer)X
X1724(pool)X
X1886(if)X
X1955(its)X
X2050(primary)X
X2324(page)X
X720 626(is)N
X804(not)X
X937(present.)X
X1240(This)X
X1413(does)X
X1591(not)X
X1724(impact)X
X1972(performance)X
X2409(or)X
X720 714(functionality,)N
X1209(because)X
X1524(an)X
X1660(over\257ow)X
X2005(page)X
X2217(will)X
X2400(be)X
X720 802(accessed)N
X1048(only)X
X1236(after)X
X1430(its)X
X1550(predecessor)X
X1975(page)X
X2172(has)X
X2324(been)X
X720 890(accessed.)N
X1068(Figure)X
X1303(4)X
X1369(depicts)X
X1622(the)X
X1746(data)X
X1905(structures)X
X2242(used)X
X2414(to)X
X720 978(manage)N
X990(the)X
X1108(buffer)X
X1325(pool.)X
X892 1092(The)N
X1040(in-memory)X
X1419(bucket)X
X1656(array)X
X1845(contains)X
X2134(pointers)X
X2414(to)X
X720 1180(buffer)N
X975(header)X
X1248(structures)X
X1617(which)X
X1870(represent)X
X2222(primary)X
X720 1268(pages.)N
X968(Buffer)X
X1203(headers)X
X1474(contain)X
X1735(modi\256ed)X
X2043(bits,)X
X2202(the)X
X2324(page)X
X720 1356(address)N
X995(of)X
X1096(the)X
X1228(buffer,)X
X1479(a)X
X1548(pointer)X
X1808(to)X
X1903(the)X
X2034(actual)X
X2259(buffer,)X
X720 1444(and)N
X875(a)X
X950(pointer)X
X1216(to)X
X1317(the)X
X1454(buffer)X
X1690(header)X
X1944(for)X
X2077(an)X
X2191(over\257ow)X
X720 1532(page)N
X901(if)X
X979(it)X
X1052(exists,)X
X1283(in)X
X1374(addition)X
X1665(to)X
X1756(the)X
X1883(LRU)X
X2072(links.)X
X2296(If)X
X2378(the)X
X720 1620(buffer)N
X950(corresponding)X
X1442(to)X
X1537(a)X
X1606(particular)X
X1947(bucket)X
X2194(is)X
X2280(not)X
X2414(in)X
X720 1708(memory,)N
X1048(its)X
X1164(pointer)X
X1432(is)X
X1526(NULL.)X
X1801(In)X
X1909(effect,)X
X2154(pages)X
X2377(are)X
X720 1796(linked)N
X950(in)X
X1042(three)X
X1233(ways.)X
X1468(Using)X
X1689(the)X
X1817(buffer)X
X2043(headers,)X
X2338(they)X
X720 1884(are)N
X851(linked)X
X1083(physically)X
X1444(through)X
X1725(the)X
X1854(LRU)X
X2045(links)X
X2231(and)X
X2378(the)X
X720 1972(over\257ow)N
X1036(links.)X
X1241(Using)X
X1462(the)X
X1590(pages)X
X1803(themselves,)X
X2209(they)X
X2377(are)X
X720 2060(linked)N
X943(logically)X
X1246(through)X
X1518(the)X
X1639(over\257ow)X
X1946(addresses)X
X2276(on)X
X2378(the)X
X720 2148(page.)N
X948(Since)X
X1162(over\257ow)X
X1482(pages)X
X1700(are)X
X1834(accessed)X
X2151(only)X
X2328(after)X
X720 2236(their)N
X904(predecessor)X
X1321(pages,)X
X1560(they)X
X1734(are)X
X1869(removed)X
X2186(from)X
X2378(the)X
X720 2324(buffer)N
X937(pool)X
X1099(when)X
X1293(their)X
X1460(primary)X
X1734(is)X
X1807(removed.)X
X10 f
X720 2412 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X1 Dt
X2309 3177 MXY
X24 15 Dl
X-8 -15 Dl
X8 -15 Dl
X-24 15 Dl
X52 0 Dl
X789 3160 MXY
X-35 0 Dl
X0 -156 Dl
X1607 0 Dl
X0 173 Dl
X789 3091 MXY
X-24 -15 Dl
X9 15 Dl
X-9 15 Dl
X24 -15 Dl
X-69 0 Dl
X2309 3125 MXY
X104 0 Dl
X0 -155 Dl
X-1693 0 Dl
X0 121 Dl
X927 3160 MXY
X24 15 Dl
X-9 -15 Dl
X9 -15 Dl
X-24 15 Dl
X553 0 Dl
X1618 3177 MXY
X8 27 Dl
X4 -17 Dl
X16 -6 Dl
X-28 -4 Dl
X138 121 Dl
X1895 3315 MXY
X28 3 Dl
X-15 -9 Dl
X1 -18 Dl
X-14 24 Dl
X276 -138 Dl
X3108 MY
X-28 -3 Dl
X15 10 Dl
X-1 17 Dl
X14 -24 Dl
X-276 138 Dl
X1756 3229 MXY
X-8 -27 Dl
X-3 17 Dl
X-16 6 Dl
X27 4 Dl
X-138 -121 Dl
X1480 MX
X-24 -15 Dl
X9 15 Dl
X-9 15 Dl
X24 -15 Dl
X-553 0 Dl
X3 f
X5 s
X1083 3073(LRU)N
X1178(chain)X
X4 Ds
X1402 3851 MXY
X 1402 3851 lineto
X 1471 3851 lineto
X 1471 3920 lineto
X 1402 3920 lineto
X 1402 3851 lineto
Xclosepath 19 1402 3851 1471 3920 Dp
X1445 3747(Over\257ow)N
X1613(Address)X
X1549 3609 MXY
X0 69 Dl
X1756 MX
X-23 -15 Dl
X8 15 Dl
X-8 15 Dl
X23 -15 Dl
X-207 0 Dl
X-1 Ds
X3 Dt
X1756 3419 MXY
X-6 -28 Dl
X-4 17 Dl
X-17 5 Dl
X27 6 Dl
X-138 -138 Dl
X2240 3471 MXY
X15 -24 Dl
X-15 9 Dl
X-15 -9 Dl
X15 24 Dl
X0 -138 Dl
X1826 3609 MXY
X15 -24 Dl
X-15 9 Dl
X-16 -9 Dl
X16 24 Dl
X0 -138 Dl
X1549 MX
X15 -24 Dl
X-15 9 Dl
X-15 -9 Dl
X15 24 Dl
X0 -138 Dl
X858 3471 MXY
X15 -24 Dl
X-15 9 Dl
X-15 -9 Dl
X15 24 Dl
X0 -138 Dl
X2240 3056 MXY
X15 -24 Dl
X-15 9 Dl
X-15 -9 Dl
X15 24 Dl
X0 -138 Dl
X1549 3056 MXY
X15 -24 Dl
X-15 9 Dl
X-15 -9 Dl
X15 24 Dl
X0 -138 Dl
X858 3056 MXY
X15 -24 Dl
X-15 9 Dl
X-15 -9 Dl
X15 24 Dl
X0 -138 Dl
X1 Dt
X2171 3471 MXY
X 2171 3471 lineto
X 2448 3471 lineto
X 2448 3609 lineto
X 2171 3609 lineto
X 2171 3471 lineto
Xclosepath 19 2171 3471 2448 3609 Dp
X1756 3609 MXY
X 1756 3609 lineto
X 2033 3609 lineto
X 2033 3747 lineto
X 1756 3747 lineto
X 1756 3609 lineto
Xclosepath 3 1756 3609 2033 3747 Dp
X1480 3471 MXY
X 1480 3471 lineto
X 1756 3471 lineto
X 1756 3609 lineto
X 1480 3609 lineto
X 1480 3471 lineto
Xclosepath 19 1480 3471 1756 3609 Dp
X789 MX
X 789 3471 lineto
X 1065 3471 lineto
X 1065 3609 lineto
X 789 3609 lineto
X 789 3471 lineto
Xclosepath 19 789 3471 1065 3609 Dp
X962 3903(Buffer)N
X1083(Header)X
X849 3851 MXY
X 849 3851 lineto
X 918 3851 lineto
X 918 3920 lineto
X 849 3920 lineto
X 849 3851 lineto
Xclosepath 14 849 3851 918 3920 Dp
X1756 3194 MXY
X 1756 3194 lineto
X 1895 3194 lineto
X 1895 3471 lineto
X 1756 3471 lineto
X 1756 3194 lineto
Xclosepath 14 1756 3194 1895 3471 Dp
X2171 3056 MXY
X 2171 3056 lineto
X 2309 3056 lineto
X 2309 3333 lineto
X 2171 3333 lineto
X 2171 3056 lineto
Xclosepath 14 2171 3056 2309 3333 Dp
X1480 MX
X 1480 3056 lineto
X 1618 3056 lineto
X 1618 3333 lineto
X 1480 3333 lineto
X 1480 3056 lineto
Xclosepath 14 1480 3056 1618 3333 Dp
X789 MX
X 789 3056 lineto
X 927 3056 lineto
X 927 3333 lineto
X 789 3333 lineto
X 789 3056 lineto
Xclosepath 14 789 3056 927 3333 Dp
X2780 MY
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X927 MX
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X1065 MX
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X1203 MX
X0 138 Dl
X139 0 Dl
X0 -138 Dl
X-139 0 Dl
X1342 MX
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X1480 MX
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X1618 MX
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X1756 MX
X0 138 Dl
X139 0 Dl
X0 -138 Dl
X-139 0 Dl
X1895 MX
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X2033 MX
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X2171 MX
X0 138 Dl
X138 0 Dl
X0 -138 Dl
X-138 0 Dl
X2309 MX
X0 138 Dl
X139 0 Dl
X0 -138 Dl
X-139 0 Dl
X13 s
X1048 2720(In)N
X1173(Memory)X
X1580(Bucket)X
X1918(Array)X
X867 3584(B0)N
X1558(B5)X
X2223(B10)X
X1788 3722(O1/1)N
X5 s
X1515 3903(Primay)N
X1651(Buffer)X
X4 Ds
X1990 3851 MXY
X 1990 3851 lineto
X 2059 3851 lineto
X 2059 3920 lineto
X 1990 3920 lineto
X 1990 3851 lineto
Xclosepath 3 1990 3851 2059 3920 Dp
X2102 3903(Over\257ow)N
X2270(Buffer)X
X3 Dt
X-1 Ds
X8 s
X720 4184(Figure)N
X922(4:)X
X1 f
X996(Three)X
X1164(primary)X
X1386(pages)X
X1551(\(B0,)X
X1683(B5,)X
X1794(B10\))X
X1942(are)X
X2039(accessed)X
X2281(directly)X
X720 4272(from)N
X862(the)X
X958(bucket)X
X1146(array.)X
X1326(The)X
X1443(one)X
X1553(over\257ow)X
X1798(page)X
X1935(\(O1/1\))X
X2122(is)X
X2182(linked)X
X2359(phy-)X
X720 4360(sically)N
X915(from)X
X1067(its)X
X1155(primary)X
X1384(page's)X
X1577(buffer)X
X1759(header)X
X1955(as)X
X2035(well)X
X2172(as)X
X2252(logically)X
X720 4448(from)N
X860(its)X
X937(predecessor)X
X1253(page)X
X1389(buffer)X
X1560(\(B5\).)X
X10 s
X10 f
X720 4624 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X3 f
X1191 4954(Table)N
X1406(Parameterization)X
X1 f
X892 5086(When)N
X1107(a)X
X1166(hash)X
X1336(table)X
X1515(is)X
X1590(created,)X
X1865(the)X
X1985(bucket)X
X2221(size,)X
X2388(\256ll)X
X720 5174(factor,)N
X953(initial)X
X1164(number)X
X1434(of)X
X1526(elements,)X
X1856(number)X
X2125(of)X
X2216(bytes)X
X2409(of)X
X720 5262(main)N
X919(memory)X
X1225(used)X
X1411(for)X
X1543(caching,)X
X1851(and)X
X2005(a)X
X2079(user-de\256ned)X
X720 5350(hash)N
X892(function)X
X1184(may)X
X1347(be)X
X1448(speci\256ed.)X
X1797(The)X
X1946(bucket)X
X2184(size)X
X2333(\(and)X
X720 5438(page)N
X906(size)X
X1064(for)X
X1191(over\257ow)X
X1509(pages\))X
X1752(defaults)X
X2039(to)X
X2134(256)X
X2287(bytes.)X
X720 5526(For)N
X858(tables)X
X1072(with)X
X1241(large)X
X1429(data)X
X1590(items,)X
X1810(it)X
X1881(may)X
X2046(be)X
X2149(preferable)X
X720 5614(to)N
X803(increase)X
X1088(the)X
X1207(page)X
X1380(size,)X
X1545(and,)X
X1701(conversely,)X
X2089(applications)X
X720 5702(storing)N
X1002(small)X
X1235(items)X
X1467(exclusively)X
X1891(in)X
X2012(memory)X
X2338(may)X
X2706 538(bene\256t)N
X2966(from)X
X3164(a)X
X3242(smaller)X
X3520(bucket)X
X3776(size.)X
X3983(A)X
X4082(bucket)X
X4337(size)X
X2706 626(smaller)N
X2962(than)X
X3120(64)X
X3220(bytes)X
X3409(is)X
X3482(not)X
X3604(recommended.)X
X2878 740(The)N
X3031(\256ll)X
X3147(factor)X
X3363(indicates)X
X3676(a)X
X3740(desired)X
X4000(density)X
X4258(within)X
X2706 828(the)N
X2833(hash)X
X3009(table.)X
X3234(It)X
X3312(is)X
X3394(an)X
X3499(approximation)X
X3995(of)X
X4091(the)X
X4217(number)X
X2706 916(of)N
X2815(keys)X
X3004(allowed)X
X3300(to)X
X3404(accumulate)X
X3811(in)X
X3914(any)X
X4071(one)X
X4228(bucket,)X
X2706 1004(determining)N
X3119(when)X
X3319(the)X
X3442(hash)X
X3614(table)X
X3795(grows.)X
X4056(Its)X
X4161(default)X
X4409(is)X
X2706 1092(eight.)N
X2953(If)X
X3054(the)X
X3199(user)X
X3380(knows)X
X3636(the)X
X3781(average)X
X4079(size)X
X4251(of)X
X4364(the)X
X2706 1180(key/data)N
X3008(pairs)X
X3194(being)X
X3402(stored)X
X3627(in)X
X3718(the)X
X3845(table,)X
X4050(near)X
X4218(optimal)X
X2706 1268(bucket)N
X2943(sizes)X
X3122(and)X
X3261(\256ll)X
X3372(factors)X
X3614(may)X
X3775(be)X
X3874(selected)X
X4155(by)X
X4257(apply-)X
X2706 1356(ing)N
X2828(the)X
X2946(equation:)X
X0 f
X8 s
X2706 1655(\(1\))N
X2994 -0.3938(\(\(average_pair_length)AX
X3830(+)X
X3906(4\))X
X4020(*)X
X3032 1743(ffactor\))N
X3374(>=)X
X3488(bsize)X
X1 f
X10 s
X2706 2042(For)N
X2859(highly)X
X3104(time)X
X3287(critical)X
X3551(applications,)X
X3999(experimenting)X
X2706 2130(with)N
X2919(different)X
X3266(bucket)X
X3550(sizes)X
X3776(and)X
X3962(\256ll)X
X4120(factors)X
X4409(is)X
X2706 2218(encouraged.)N
X2878 2332(Figures)N
X3144(5a,b,)X
X3326(and)X
X3468(c)X
X3530(illustrate)X
X3836(the)X
X3960(effects)X
X4200(of)X
X4292(vary-)X
X2706 2420(ing)N
X2841(page)X
X3026(sizes)X
X3215(and)X
X3363(\256ll)X
X3483(factors)X
X3734(for)X
X3860(the)X
X3990(same)X
X4187(data)X
X4353(set.)X
X2706 2508(The)N
X2864(data)X
X3031(set)X
X3152(consisted)X
X3482(of)X
X3581(24474)X
X3813(keys)X
X3992(taken)X
X4198(from)X
X4386(an)X
X2706 2596(online)N
X2931(dictionary.)X
X3301(The)X
X3451(data)X
X3609(value)X
X3807(for)X
X3925(each)X
X4097(key)X
X4237(was)X
X4386(an)X
X2706 2684(ASCII)N
X2938(string)X
X3143(for)X
X3260(an)X
X3359(integer)X
X3605(from)X
X3784(1)X
X3847(to)X
X3931(24474)X
X4153(inclusive.)X
X2706 2772(The)N
X2867(test)X
X3013(run)X
X3155(consisted)X
X3488(of)X
X3590(creating)X
X3884(a)X
X3955(new)X
X4124(hash)X
X4306(table)X
X2706 2860(\(where)N
X2966(the)X
X3100(ultimate)X
X3398(size)X
X3559(of)X
X3662(the)X
X3796(table)X
X3987(was)X
X4147(known)X
X4400(in)X
X2706 2948(advance\),)N
X3054(entering)X
X3354(each)X
X3539(key/data)X
X3848(pair)X
X4010(into)X
X4171(the)X
X4306(table)X
X2706 3036(and)N
X2849(then)X
X3014(retrieving)X
X3353(each)X
X3528(key/data)X
X3827(pair)X
X3979(from)X
X4162(the)X
X4286(table.)X
X2706 3124(Each)N
X2898(of)X
X2996(the)X
X3125(graphs)X
X3369(shows)X
X3599(the)X
X3727(timings)X
X3996(resulting)X
X4306(from)X
X2706 3212(varying)N
X2973(the)X
X3093(pagesize)X
X3392(from)X
X3570(128)X
X3712(bytes)X
X3903(to)X
X3986(1M)X
X4118(and)X
X4255(the)X
X4374(\256ll)X
X2706 3300(factor)N
X2929(from)X
X3120(1)X
X3195(to)X
X3292(128.)X
X3486(For)X
X3631(each)X
X3813(run,)X
X3974(the)X
X4106(buffer)X
X4337(size)X
X2706 3388(was)N
X2874(set)X
X3006(at)X
X3106(1M.)X
X3299(The)X
X3466(tests)X
X3650(were)X
X3849(all)X
X3971(run)X
X4120(on)X
X4242(an)X
X4360(HP)X
X2706 3476(9000/370)N
X3077(\(33.3)X
X3312(Mhz)X
X3527(MC68030\),)X
X3966(with)X
X4176(16M)X
X4395(of)X
X2706 3564(memory,)N
X3042(64K)X
X3228(physically)X
X3605(addressed)X
X3970(cache,)X
X4222(and)X
X4386(an)X
X2706 3652(HP7959S)N
X3055(disk)X
X3231(drive,)X
X3459(running)X
X3751(4.3BSD-Reno)X
X4244(single-)X
X2706 3740(user.)N
X2878 3854(Both)N
X3066(system)X
X3321(time)X
X3496(\(Figure)X
X3764(5a\))X
X3899(and)X
X4047(elapsed)X
X4320(time)X
X2706 3942(\(Figure)N
X2966(5b\))X
X3097(show)X
X3290(that)X
X3434(for)X
X3552(all)X
X3655(bucket)X
X3892(sizes,)X
X4091(the)X
X4212(greatest)X
X2706 4030(performance)N
X3137(gains)X
X3329(are)X
X3451(made)X
X3648(by)X
X3751(increasing)X
X4104(the)X
X4225(\256ll)X
X4336(fac-)X
X2706 4118(tor)N
X2822(until)X
X2995(equation)X
X3298(1)X
X3365(is)X
X3445(satis\256ed.)X
X3774(The)X
X3925(user)X
X4085(time)X
X4253(shown)X
X2706 4206(in)N
X2791(Figure)X
X3023(5c)X
X3122(gives)X
X3314(a)X
X3373(more)X
X3561(detailed)X
X3838(picture)X
X4083(of)X
X4172(how)X
X4332(per-)X
X2706 4294(formance)N
X3054(varies.)X
X3330(The)X
X3499(smaller)X
X3778(bucket)X
X4035(sizes)X
X4234(require)X
X2706 4382(fewer)N
X2921(keys)X
X3099(per)X
X3233(page)X
X3416(to)X
X3509(satisfy)X
X3749(equation)X
X4056(1)X
X4127(and)X
X4274(there-)X
X2706 4470(fore)N
X2860(incur)X
X3049(fewer)X
X3257(collisions.)X
X3607(However,)X
X3946(when)X
X4144(the)X
X4265(buffer)X
X2706 4558(pool)N
X2884(size)X
X3045(is)X
X3134(\256xed,)X
X3349(smaller)X
X3620(pages)X
X3838(imply)X
X4059(more)X
X4259(pages.)X
X2706 4646(An)N
X2830(increased)X
X3160(number)X
X3430(of)X
X3522(pages)X
X3730(means)X
X3960(more)X
X2 f
X4150(malloc\(3\))X
X1 f
X2706 4734(calls)N
X2879(and)X
X3021(more)X
X3212(overhead)X
X3533(in)X
X3621(the)X
X3745(hash)X
X3918(package's)X
X4265(buffer)X
X2706 4822(manager)N
X3003(to)X
X3085(manage)X
X3355(the)X
X3473(additional)X
X3813(pages.)X
X2878 4936(The)N
X3028(tradeoff)X
X3308(works)X
X3529(out)X
X3655(most)X
X3834(favorably)X
X4166(when)X
X4364(the)X
X2706 5024(page)N
X2886(size)X
X3039(is)X
X3120(256)X
X3268(and)X
X3412(the)X
X3538(\256ll)X
X3654(factor)X
X3870(is)X
X3950(8.)X
X4057(Similar)X
X4319(con-)X
X2706 5112(clusions)N
X3009(were)X
X3207(obtained)X
X3524(if)X
X3614(the)X
X3753(test)X
X3905(was)X
X4071(run)X
X4218(without)X
X2706 5200(knowing)N
X3007(the)X
X3126(\256nal)X
X3289(table)X
X3466(size)X
X3612(in)X
X3695(advance.)X
X4020(If)X
X4095(the)X
X4214(\256le)X
X4337(was)X
X2706 5288(closed)N
X2942(and)X
X3088(written)X
X3345(to)X
X3437(disk,)X
X3620(the)X
X3748(conclusions)X
X4156(were)X
X4343(still)X
X2706 5376(the)N
X2832(same.)X
X3065(However,)X
X3408(rereading)X
X3740(the)X
X3865(\256le)X
X3994(from)X
X4177(disk)X
X4337(was)X
X2706 5464(slightly)N
X2983(faster)X
X3199(if)X
X3285(a)X
X3358(larger)X
X3583(bucket)X
X3834(size)X
X3996(and)X
X4149(\256ll)X
X4274(factor)X
X2706 5552(were)N
X2898(used)X
X3079(\(1K)X
X3238(bucket)X
X3486(size)X
X3645(and)X
X3795(32)X
X3909(\256ll)X
X4031(factor\).)X
X4320(This)X
X2706 5640(follows)N
X2987(intuitively)X
X3356(from)X
X3553(the)X
X3691(improved)X
X4038(ef\256ciency)X
X4395(of)X
X3 f
X720 5960(USENIX)N
X9 f
X1042(-)X
X3 f
X1106(Winter)X
X1371('91)X
X9 f
X1498(-)X
X3 f
X1562(Dallas,)X
X1815(TX)X
X4424(7)X
X
X8 p
X%%Page: 8 8
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X432 258(A)N
X510(New)X
X682(Hashing)X
X985(Package)X
X1290(for)X
X1413(UNIX)X
X3663(Seltzer)X
X3920(&)X
X4007(Yigit)X
X1 f
X432 538(performing)N
X830(1K)X
X965(reads)X
X1172(from)X
X1365(the)X
X1500(disk)X
X1670(rather)X
X1894(than)X
X2068(256)X
X432 626(byte)N
X609(reads.)X
X857(In)X
X962(general,)X
X1257(performance)X
X1702(for)X
X1834(disk)X
X2005(based)X
X432 714(tables)N
X639(is)X
X712(best)X
X861(when)X
X1055(the)X
X1173(page)X
X1345(size)X
X1490(is)X
X1563(approximately)X
X2046(1K.)X
X10 f
X432 802 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X619 2380 MXY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X629 2437 MXY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X648 2504 MXY
X-12 25 Dl
X24 0 Dl
X-12 -25 Dl
X686 2515 MXY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X762 2516 MXY
X-12 24 Dl
X25 0 Dl
X-13 -24 Dl
X916 2515 MXY
X-13 24 Dl
X25 0 Dl
X-12 -24 Dl
X1222 2516 MXY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X1834 2515 MXY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X1 Dt
X619 2392 MXY
X10 57 Dl
X19 67 Dl
X38 11 Dl
X76 1 Dl
X154 -1 Dl
X306 1 Dl
X612 -1 Dl
X8 s
X1 f
X1628 2522(128)N
X3 Dt
X607 2245 MXY
X24 Dc
X617 2375 MXY
X23 Dc
X635 2442 MXY
X24 Dc
X674 2525 MXY
X23 Dc
X750 2529 MXY
X24 Dc
X904 2527 MXY
X23 Dc
X1210 MX
X23 Dc
X1822 2528 MXY
X23 Dc
X20 Ds
X1 Dt
X619 2245 MXY
X10 130 Dl
X19 67 Dl
X38 83 Dl
X76 4 Dl
X154 -2 Dl
X306 0 Dl
X612 1 Dl
X678 2482(256)N
X-1 Ds
X3 Dt
X619 2127 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X629 2191 MXY
X0 25 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X648 2334 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X686 2409 MXY
X0 25 Dl
X0 -13 Dl
X12 0 Dl
X-24 0 Dl
X762 2516 MXY
X0 25 Dl
X0 -12 Dl
X13 0 Dl
X-25 0 Dl
X916 2516 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-25 0 Dl
X1222 2515 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X1834 2515 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X5 Dt
X619 2139 MXY
X10 65 Dl
X19 142 Dl
X38 75 Dl
X76 108 Dl
X154 -1 Dl
X306 -1 Dl
X612 0 Dl
X694 2401(512)N
X3 Dt
X631 2064 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X641 2077 MXY
X-24 25 Dl
X12 -12 Dl
X-12 -13 Dl
X24 25 Dl
X660 2132 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X698 2292 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X775 2382 MXY
X-25 24 Dl
X12 -12 Dl
X-12 -12 Dl
X25 24 Dl
X928 2516 MXY
X-25 24 Dl
X13 -12 Dl
X-13 -12 Dl
X25 24 Dl
X1234 2516 MXY
X-24 25 Dl
X12 -12 Dl
X-12 -13 Dl
X24 25 Dl
X1846 2516 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X16 Ds
X1 Dt
X619 2076 MXY
X10 14 Dl
X19 54 Dl
X38 160 Dl
X76 90 Dl
X154 134 Dl
X306 1 Dl
X612 -1 Dl
X694 2257(1024)N
X-1 Ds
X3 Dt
X619 1877 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X629 1855 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X648 1838 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X686 1860 MXY
X12 -25 Dl
X-24 0 Dl
X12 25 Dl
X762 1923 MXY
X13 -24 Dl
X-25 0 Dl
X12 24 Dl
X916 2087 MXY
X12 -24 Dl
X-25 0 Dl
X13 24 Dl
X1222 2256 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X1834 2541 MXY
X12 -25 Dl
X-24 0 Dl
X12 25 Dl
X619 1865 MXY
X10 -22 Dl
X19 -17 Dl
X38 21 Dl
X76 64 Dl
X154 164 Dl
X306 169 Dl
X612 285 Dl
X1645 2427(4096)N
X619 1243 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X629 1196 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X648 1146 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X686 1174 MXY
X0 25 Dl
X0 -13 Dl
X12 0 Dl
X-24 0 Dl
X762 1249 MXY
X0 24 Dl
X0 -12 Dl
X13 0 Dl
X-25 0 Dl
X916 1371 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-25 0 Dl
X1222 1680 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X1834 1999 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X619 1255 MXY
X10 -47 Dl
X19 -50 Dl
X38 28 Dl
X76 75 Dl
X154 122 Dl
X306 309 Dl
X612 319 Dl
X1741 1934(8192)N
X5 Dt
X609 2531 MXY
X1225 0 Dl
X609 MX
X0 -1553 Dl
X2531 MY
X0 16 Dl
X4 Ds
X1 Dt
X2531 MY
X0 -1553 Dl
X593 2625(0)N
X-1 Ds
X5 Dt
X916 2531 MXY
X0 16 Dl
X4 Ds
X1 Dt
X2531 MY
X0 -1553 Dl
X884 2625(32)N
X-1 Ds
X5 Dt
X1222 2531 MXY
X0 16 Dl
X4 Ds
X1 Dt
X2531 MY
X0 -1553 Dl
X1190 2625(64)N
X-1 Ds
X5 Dt
X1528 2531 MXY
X0 16 Dl
X4 Ds
X1 Dt
X2531 MY
X0 -1553 Dl
X1496 2625(96)N
X-1 Ds
X5 Dt
X1834 2531 MXY
X0 16 Dl
X4 Ds
X1 Dt
X2531 MY
X0 -1553 Dl
X1786 2625(128)N
X-1 Ds
X5 Dt
X609 2531 MXY
X-16 0 Dl
X4 Ds
X1 Dt
X609 MX
X1225 0 Dl
X545 2558(0)N
X-1 Ds
X5 Dt
X609 2013 MXY
X-16 0 Dl
X4 Ds
X1 Dt
X609 MX
X1225 0 Dl
X481 2040(100)N
X-1 Ds
X5 Dt
X609 1496 MXY
X-16 0 Dl
X4 Ds
X1 Dt
X609 MX
X1225 0 Dl
X481 1523(200)N
X-1 Ds
X5 Dt
X609 978 MXY
X-16 0 Dl
X4 Ds
X1 Dt
X609 MX
X1225 0 Dl
X481 1005(300)N
X1088 2724(Fill)N
X1194(Factor)X
X422 1611(S)N
X426 1667(e)N
X426 1724(c)N
X424 1780(o)N
X424 1837(n)N
X424 1893(d)N
X428 1949(s)N
X3 Dt
X-1 Ds
X3 f
X432 2882(Figure)N
X636(5a:)X
X1 f
X744(System)X
X956(Time)X
X1113(for)X
X1209(dictionary)X
X1490(data)X
X1618(set)X
X1711(with)X
X1847(1M)X
X1958(of)X
X2033(buffer)X
X432 2970(space)N
X594(and)X
X707(varying)X
X923(bucket)X
X1114(sizes)X
X1259(and)X
X1372(\256ll)X
X1465(factors.)X
X1675(Each)X
X1823(line)X
X1940(is)X
X2004(labeled)X
X432 3058(with)N
X562(its)X
X639(bucket)X
X825(size.)X
X10 s
X10 f
X432 3234 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X8 s
X1 f
X428 4381(s)N
X424 4325(d)N
X424 4269(n)N
X424 4212(o)N
X426 4156(c)N
X426 4099(e)N
X422 4043(S)N
X1116 5156(Fill)N
X1222(Factor)X
X506 3437(3200)N
X4 Ds
X1 Dt
X666 3410 MXY
X1168 0 Dl
X-1 Ds
X5 Dt
X666 MX
X-16 0 Dl
X506 3825(2400)N
X4 Ds
X1 Dt
X666 3799 MXY
X1168 0 Dl
X-1 Ds
X5 Dt
X666 MX
X-16 0 Dl
X506 4214(1600)N
X4 Ds
X1 Dt
X666 4186 MXY
X1168 0 Dl
X-1 Ds
X5 Dt
X666 MX
X-16 0 Dl
X538 4602(800)N
X4 Ds
X1 Dt
X666 4575 MXY
X1168 0 Dl
X-1 Ds
X5 Dt
X666 MX
X-16 0 Dl
X602 4990(0)N
X4 Ds
X1 Dt
X666 4963 MXY
X1168 0 Dl
X-1 Ds
X5 Dt
X666 MX
X-16 0 Dl
X1786 5057(128)N
X4 Ds
X1 Dt
X1834 4963 MXY
X0 -1553 Dl
X-1 Ds
X5 Dt
X4963 MY
X0 16 Dl
X1510 5057(96)N
X4 Ds
X1 Dt
X1542 4963 MXY
X0 -1553 Dl
X-1 Ds
X5 Dt
X4963 MY
X0 16 Dl
X1218 5057(64)N
X4 Ds
X1 Dt
X1250 4963 MXY
X0 -1553 Dl
X-1 Ds
X5 Dt
X4963 MY
X0 16 Dl
X926 5057(32)N
X4 Ds
X1 Dt
X958 4963 MXY
X0 -1553 Dl
X-1 Ds
X5 Dt
X4963 MY
X0 16 Dl
X650 5057(0)N
X4 Ds
X1 Dt
X666 4963 MXY
X0 -1553 Dl
X-1 Ds
X5 Dt
X4963 MY
X0 16 Dl
X4963 MY
X0 -1553 Dl
X4963 MY
X1168 0 Dl
X1741 4752(8192)N
X3 Dt
X675 3732 MXY
X9 -172 Dl
X18 -118 Dl
X37 128 Dl
X73 -121 Dl
X146 623 Dl
X292 497 Dl
X584 245 Dl
X4802 MY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X1250 4557 MXY
X0 25 Dl
X0 -13 Dl
X12 0 Dl
X-24 0 Dl
X958 4060 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X812 3437 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X739 3558 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X702 3430 MXY
X0 25 Dl
X0 -13 Dl
X13 0 Dl
X-25 0 Dl
X684 3548 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X675 3720 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X1637 4912(4096)N
X675 4307 MXY
X9 -58 Dl
X18 30 Dl
X37 89 Dl
X73 144 Dl
X146 235 Dl
X292 122 Dl
X584 89 Dl
X4970 MY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X1250 4881 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X958 4759 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X812 4524 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X739 4380 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X702 4291 MXY
X13 -24 Dl
X-25 0 Dl
X12 24 Dl
X684 4261 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X675 4319 MXY
X12 -24 Dl
X-24 0 Dl
X12 24 Dl
X734 4662(1024)N
X16 Ds
X1 Dt
X675 4352 MXY
X9 60 Dl
X18 134 Dl
X37 266 Dl
X73 117 Dl
X146 30 Dl
X292 0 Dl
X584 -1 Dl
X-1 Ds
X3 Dt
X1846 4946 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X1262 4946 MXY
X-24 25 Dl
X12 -12 Dl
X-12 -13 Dl
X24 25 Dl
X970 4947 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X824 4917 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X751 4800 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X715 4534 MXY
X-25 25 Dl
X12 -13 Dl
X-12 -12 Dl
X25 25 Dl
X696 4400 MXY
X-24 24 Dl
X12 -12 Dl
X-12 -12 Dl
X24 24 Dl
X687 4339 MXY
X-24 25 Dl
X12 -12 Dl
X-12 -13 Dl
X24 25 Dl
X718 4792(512)N
X5 Dt
X675 4422 MXY
X9 137 Dl
X18 278 Dl
X37 105 Dl
X73 18 Dl
X146 -1 Dl
X292 0 Dl
X584 -1 Dl
X3 Dt
X4946 MY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X1250 4946 MXY
X0 25 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X958 4947 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X812 4948 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X739 4930 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X702 4824 MXY
X0 25 Dl
X0 -12 Dl
X13 0 Dl
X-25 0 Dl
X684 4547 MXY
X0 24 Dl
X0 -12 Dl
X12 0 Dl
X-24 0 Dl
X675 4410 MXY
X0 25 Dl
X0 -13 Dl
X12 0 Dl
X-24 0 Dl
X750 4921(256)N
X20 Ds
X1 Dt
X675 4597 MXY
X9 246 Dl
X18 106 Dl
X37 10 Dl
X73 0 Dl
X146 0 Dl
X292 0 Dl
X584 -1 Dl
X-1 Ds
X3 Dt
X1822 MX
X23 Dc
X1238 4959 MXY
X23 Dc
X946 MX
X23 Dc
X800 MX
X23 Dc
X727 MX
X23 Dc
X691 4949 MXY
X23 Dc
X672 4843 MXY
X24 Dc
X663 4597 MXY
X24 Dc
X1395 4961(128)N
X1 Dt
X675 4855 MXY
X9 93 Dl
X18 10 Dl
X37 1 Dl
X73 0 Dl
X146 -1 Dl
X292 0 Dl
X584 0 Dl
X3 Dt
X4946 MY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X1250 MX
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X958 MX
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X812 MX
X-12 25 Dl
X24 0 Dl
X-12 -25 Dl
X739 4947 MXY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X702 4946 MXY
X-12 24 Dl
X25 0 Dl
X-13 -24 Dl
X684 4936 MXY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X675 4843 MXY
X-12 24 Dl
X24 0 Dl
X-12 -24 Dl
X3 Dt
X-1 Ds
X3 f
X432 5314(Figure)N
X634(5b:)X
X1 f
X744(Elapsed)X
X967(Time)X
X1123(for)X
X1218(dictionary)X
X1498(data)X
X1625(set)X
X1717(with)X
X1851(1M)X
X1960(of)X
X2033(buffer)X
X432 5402(space)N
X593(and)X
X705(varying)X
X920(bucket)X
X1110(sizes)X
X1254(and)X
X1366(\256ll)X
X1457(factors.)X
X1681(Each)X
X1827(line)X
X1942(is)X
X2004(labeled)X
X432 5490(with)N
X562(its)X
X639(bucket)X
X825(size.)X
X10 s
X2590 538(If)N
X2677(an)X
X2785(approximation)X
X3284(of)X
X3383(the)X
X3513(number)X
X3790(of)X
X3889(elements)X
X2418 626(ultimately)N
X2773(to)X
X2866(be)X
X2973(stored)X
X3200(in)X
X3293(the)X
X3422(hash)X
X3599(table)X
X3785(is)X
X3868(known)X
X4116(at)X
X2418 714(the)N
X2564(time)X
X2754(of)X
X2869(creation,)X
X3196(the)X
X3342(hash)X
X3536(package)X
X3847(takes)X
X4059(this)X
X2418 802(number)N
X2688(as)X
X2779(a)X
X2839(parameter)X
X3185(and)X
X3325(uses)X
X3487(it)X
X3555(to)X
X3641(hash)X
X3812(entries)X
X4050(into)X
X2418 890(the)N
X2541(full)X
X2677(sized)X
X2867(table)X
X3048(rather)X
X3261(than)X
X3424(growing)X
X3716(the)X
X3838(table)X
X4018(from)X
X2418 978(a)N
X2477(single)X
X2691(bucket.)X
X2968(If)X
X3044(this)X
X3181(number)X
X3448(is)X
X3523(not)X
X3647(known,)X
X3907(the)X
X4027(hash)X
X2418 1066(table)N
X2632(starts)X
X2859(with)X
X3059(a)X
X3153(single)X
X3402(bucket)X
X3674(and)X
X3848(gracefully)X
X2418 1154(expands)N
X2707(as)X
X2800(elements)X
X3111(are)X
X3236(added,)X
X3474(although)X
X3780(a)X
X3842(slight)X
X4044(per-)X
X2418 1242(formance)N
X2747(degradation)X
X3151(may)X
X3313(be)X
X3413(noticed.)X
X3713(Figure)X
X3946(6)X
X4010(illus-)X
X2418 1330(trates)N
X2625(the)X
X2756(difference)X
X3116(in)X
X3211(performance)X
X3651(between)X
X3952(storing)X
X2418 1418(keys)N
X2588(in)X
X2673(a)X
X2732(\256le)X
X2857(when)X
X3054(the)X
X3174(ultimate)X
X3458(size)X
X3605(is)X
X3680(known)X
X3920(\(the)X
X4067(left)X
X2418 1506(bars)N
X2581(in)X
X2672(each)X
X2849(set\),)X
X3014(compared)X
X3360(to)X
X3450(building)X
X3744(the)X
X3870(\256le)X
X4000(when)X
X2418 1594(the)N
X2550(ultimate)X
X2846(size)X
X3005(is)X
X3091(unknown)X
X3422(\(the)X
X3580(right)X
X3764(bars)X
X3931(in)X
X4026(each)X
X2418 1682(set\).)N
X2609(Once)X
X2814(the)X
X2947(\256ll)X
X3069(factor)X
X3291(is)X
X3378(suf\256ciently)X
X3772(high)X
X3948(for)X
X4076(the)X
X2418 1770(page)N
X2596(size)X
X2747(\(8\),)X
X2887(growing)X
X3180(the)X
X3304(table)X
X3486(dynamically)X
X3908(does)X
X4081(lit-)X
X2418 1858(tle)N
X2518(to)X
X2600(degrade)X
X2875(performance.)X
X10 f
X2418 1946 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X9 s
X1 f
X2413 3238(s)N
X2409 3173(d)N
X2409 3108(n)N
X2409 3043(o)N
X2411 2979(c)N
X2411 2914(e)N
X2407 2849(S)N
X3143 4129(Fill)N
X3261(Factor)X
X2448 2152(15)N
X4 Ds
X1 Dt
X2557 2122 MXY
X1473 0 Dl
X-1 Ds
X5 Dt
X2557 MX
X-19 0 Dl
X2448 2747(10)N
X4 Ds
X1 Dt
X2557 2717 MXY
X1473 0 Dl
X-1 Ds
X5 Dt
X2557 MX
X-19 0 Dl
X2484 3343(5)N
X4 Ds
X1 Dt
X2557 3313 MXY
X1473 0 Dl
X-1 Ds
X5 Dt
X2557 MX
X-19 0 Dl
X2484 3938(0)N
X4 Ds
X1 Dt
X2557 3908 MXY
X1473 0 Dl
X-1 Ds
X5 Dt
X2557 MX
X-19 0 Dl
X3976 4015(128)N
X4 Ds
X1 Dt
X4030 3908 MXY
X0 -1786 Dl
X-1 Ds
X5 Dt
X3908 MY
X0 19 Dl
X3626 4015(96)N
X4 Ds
X1 Dt
X3662 3908 MXY
X0 -1786 Dl
X-1 Ds
X5 Dt
X3908 MY
X0 19 Dl
X3258 4015(64)N
X4 Ds
X1 Dt
X3294 3908 MXY
X0 -1786 Dl
X-1 Ds
X5 Dt
X3908 MY
X0 19 Dl
X2889 4015(32)N
X4 Ds
X1 Dt
X2925 3908 MXY
X0 -1786 Dl
X-1 Ds
X5 Dt
X3908 MY
X0 19 Dl
X2539 4015(0)N
X4 Ds
X1 Dt
X2557 3908 MXY
X0 -1786 Dl
X-1 Ds
X5 Dt
X3908 MY
X0 19 Dl
X3908 MY
X0 -1786 Dl
X3908 MY
X1473 0 Dl
X4053 2378(8192)N
X3 Dt
X2569 2277 MXY
X11 0 Dl
X23 48 Dl
X46 -167 Dl
X92 35 Dl
X184 12 Dl
X369 143 Dl
X736 0 Dl
X2334 MY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X3294 2334 MXY
X0 28 Dl
X0 -14 Dl
X13 0 Dl
X-27 0 Dl
X2925 2192 MXY
X0 27 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2741 2180 MXY
X0 27 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2649 2144 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2603 2311 MXY
X0 27 Dl
X0 -13 Dl
X14 0 Dl
X-28 0 Dl
X2580 2263 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2569 2263 MXY
X0 28 Dl
X0 -14 Dl
X13 0 Dl
X-27 0 Dl
X4053 2591(4096)N
X2569 2348 MXY
X11 -11 Dl
X23 -96 Dl
X46 71 Dl
X92 72 Dl
X184 226 Dl
X369 48 Dl
X736 -60 Dl
X2612 MY
X14 -28 Dl
X-28 0 Dl
X14 28 Dl
X3294 2672 MXY
X13 -28 Dl
X-27 0 Dl
X14 28 Dl
X2925 2624 MXY
X14 -28 Dl
X-28 0 Dl
X14 28 Dl
X2741 2398 MXY
X14 -28 Dl
X-28 0 Dl
X14 28 Dl
X2649 2326 MXY
X14 -27 Dl
X-28 0 Dl
X14 27 Dl
X2603 2255 MXY
X14 -28 Dl
X-28 0 Dl
X14 28 Dl
X2580 2350 MXY
X14 -27 Dl
X-28 0 Dl
X14 27 Dl
X2569 2362 MXY
X13 -28 Dl
X-27 0 Dl
X14 28 Dl
X4053 2681(1024)N
X16 Ds
X1 Dt
X2569 2300 MXY
X11 48 Dl
X23 96 Dl
X46 95 Dl
X92 274 Dl
X184 202 Dl
X369 -155 Dl
X736 -190 Dl
X-1 Ds
X3 Dt
X4044 2656 MXY
X-28 28 Dl
X14 -14 Dl
X-14 -14 Dl
X28 28 Dl
X3307 2846 MXY
X-27 28 Dl
X14 -14 Dl
X-14 -14 Dl
X27 28 Dl
X2939 3001 MXY
X-28 28 Dl
X14 -14 Dl
X-14 -14 Dl
X28 28 Dl
X2755 2799 MXY
X-28 28 Dl
X14 -14 Dl
X-14 -14 Dl
X28 28 Dl
X2663 2525 MXY
X-28 28 Dl
X14 -14 Dl
X-14 -14 Dl
X28 28 Dl
X2617 2430 MXY
X-28 28 Dl
X14 -14 Dl
X-14 -14 Dl
X28 28 Dl
X2594 2334 MXY
X-28 28 Dl
X14 -14 Dl
X-14 -14 Dl
X28 28 Dl
X2582 2287 MXY
X-27 27 Dl
X14 -14 Dl
X-14 -13 Dl
X27 27 Dl
X4053 2851(512)N
X5 Dt
X2569 2372 MXY
X11 -24 Dl
X23 405 Dl
X46 83 Dl
X92 227 Dl
X184 -72 Dl
X369 -119 Dl
X736 -107 Dl
X3 Dt
X2751 MY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X3294 2858 MXY
X0 28 Dl
X0 -14 Dl
X13 0 Dl
X-27 0 Dl
X2925 2977 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2741 3049 MXY
X0 27 Dl
X0 -13 Dl
X14 0 Dl
X-28 0 Dl
X2649 2823 MXY
X0 27 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2603 2739 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2580 2334 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2569 2358 MXY
X0 28 Dl
X0 -14 Dl
X13 0 Dl
X-27 0 Dl
X4053 2795(256)N
X20 Ds
X1 Dt
X2569 2456 MXY
X11 285 Dl
X23 95 Dl
X46 251 Dl
X92 -60 Dl
X184 -84 Dl
X369 -107 Dl
X736 -71 Dl
X-1 Ds
X3 Dt
X4016 MX
X27 Dc
X3280 2836 MXY
X27 Dc
X2912 2943 MXY
X27 Dc
X2728 3027 MXY
X27 Dc
X2635 3087 MXY
X28 Dc
X2589 2836 MXY
X28 Dc
X2566 2741 MXY
X27 Dc
X2554 2456 MXY
X28 Dc
X4053 2741(128)N
X1 Dt
X2569 2729 MXY
X11 203 Dl
X23 131 Dl
X46 -60 Dl
X92 -119 Dl
X184 -60 Dl
X369 -83 Dl
X736 -12 Dl
X3 Dt
X2716 MY
X-14 27 Dl
X28 0 Dl
X-14 -27 Dl
X3294 2727 MXY
X-14 28 Dl
X27 0 Dl
X-13 -28 Dl
X2925 2811 MXY
X-14 27 Dl
X28 0 Dl
X-14 -27 Dl
X2741 2870 MXY
X-14 28 Dl
X28 0 Dl
X-14 -28 Dl
X2649 2989 MXY
X-14 28 Dl
X28 0 Dl
X-14 -28 Dl
X2603 3049 MXY
X-14 27 Dl
X28 0 Dl
X-14 -27 Dl
X2580 2918 MXY
X-14 28 Dl
X28 0 Dl
X-14 -28 Dl
X2569 2716 MXY
X-14 27 Dl
X27 0 Dl
X-13 -27 Dl
X3 Dt
X-1 Ds
X3 f
X8 s
X2418 4286(Figure)N
X2628(5c:)X
X1 f
X2738(User)X
X2887(Time)X
X3051(for)X
X3154(dictionary)X
X3442(data)X
X3577(set)X
X3677(with)X
X3820(1M)X
X3938(of)X
X4019(buffer)X
X2418 4374(space)N
X2579(and)X
X2691(varying)X
X2906(bucket)X
X3096(sizes)X
X3240(and)X
X3352(\256ll)X
X3443(factors.)X
X3667(Each)X
X3813(line)X
X3928(is)X
X3990(labeled)X
X2418 4462(with)N
X2548(its)X
X2625(bucket)X
X2811(size.)X
X10 s
X10 f
X2418 4638 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X1 f
X2590 4840(Since)N
X2796(no)X
X2904(known)X
X3150(hash)X
X3325(function)X
X3620(performs)X
X3938(equally)X
X2418 4928(well)N
X2589(on)X
X2702(all)X
X2815(possible)X
X3110(data,)X
X3297(the)X
X3428(user)X
X3595(may)X
X3766(\256nd)X
X3923(that)X
X4076(the)X
X2418 5016(built-in)N
X2678(hash)X
X2849(function)X
X3140(does)X
X3311(poorly)X
X3544(on)X
X3648(a)X
X3708(particular)X
X4040(data)X
X2418 5104(set.)N
X2548(In)X
X2636(this)X
X2771(case,)X
X2950(a)X
X3006(hash)X
X3173(function,)X
X3480(taking)X
X3700(two)X
X3840(arguments)X
X2418 5192(\(a)N
X2507(pointer)X
X2760(to)X
X2848(a)X
X2910(byte)X
X3074(string)X
X3282(and)X
X3424(a)X
X3486(length\))X
X3739(and)X
X3880(returning)X
X2418 5280(an)N
X2517(unsigned)X
X2829(long)X
X2993(to)X
X3077(be)X
X3175(used)X
X3344(as)X
X3433(the)X
X3553(hash)X
X3722(value,)X
X3938(may)X
X4098(be)X
X2418 5368(speci\256ed)N
X2731(at)X
X2817(hash)X
X2992(table)X
X3176(creation)X
X3463(time.)X
X3673(When)X
X3893(an)X
X3996(exist-)X
X2418 5456(ing)N
X2570(hash)X
X2767(table)X
X2973(is)X
X3076(opened)X
X3358(and)X
X3524(a)X
X3609(hash)X
X3805(function)X
X4121(is)X
X2418 5544(speci\256ed,)N
X2752(the)X
X2879(hash)X
X3054(package)X
X3346(will)X
X3498(try)X
X3615(to)X
X3705(determine)X
X4054(that)X
X2418 5632(the)N
X2546(hash)X
X2723(function)X
X3020(supplied)X
X3321(is)X
X3404(the)X
X3532(one)X
X3678(with)X
X3850(which)X
X4076(the)X
X2418 5720(table)N
X2630(was)X
X2811(created.)X
X3139(There)X
X3382(are)X
X3536(a)X
X3627(variety)X
X3905(of)X
X4027(hash)X
X3 f
X432 5960(8)N
X2970(USENIX)X
X9 f
X3292(-)X
X3 f
X3356(Winter)X
X3621('91)X
X9 f
X3748(-)X
X3 f
X3812(Dallas,)X
X4065(TX)X
X
X9 p
X%%Page: 9 9
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X720 258(Seltzer)N
X977(&)X
X1064(Yigit)X
X3278(A)X
X3356(New)X
X3528(Hashing)X
X3831(Package)X
X4136(for)X
X4259(UNIX)X
X1 f
X720 538(functions)N
X1065(provided)X
X1397(with)X
X1586(the)X
X1731(package.)X
X2082(The)X
X2253(default)X
X720 626(function)N
X1014(for)X
X1135(the)X
X1260(package)X
X1551(is)X
X1631(the)X
X1755(one)X
X1897(which)X
X2119(offered)X
X2378(the)X
X720 714(best)N
X875(performance)X
X1308(in)X
X1396(terms)X
X1600(of)X
X1693(cycles)X
X1920(executed)X
X2232(per)X
X2360(call)X
X720 802(\(it)N
X827(did)X
X965(not)X
X1103(produce)X
X1398(the)X
X1531(fewest)X
X1776(collisions)X
X2117(although)X
X2432(it)X
X720 890(was)N
X866(within)X
X1091(a)X
X1148(small)X
X1341(percentage)X
X1710(of)X
X1797(the)X
X1915(function)X
X2202(that)X
X2342(pro-)X
X720 978(duced)N
X947(the)X
X1080(fewest)X
X1324(collisions\).)X
X1731(Again,)X
X1981(in)X
X2077(time)X
X2253(critical)X
X720 1066(applications,)N
X1152(users)X
X1342(are)X
X1466(encouraged)X
X1862(to)X
X1949(experiment)X
X2334(with)X
X720 1154(a)N
X783(variety)X
X1032(of)X
X1125(hash)X
X1298(functions)X
X1622(to)X
X1710(achieve)X
X1982(optimal)X
X2252(perfor-)X
X720 1242(mance.)N
X10 f
X720 1330 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X3 f
X7 s
X1038 2925(Full)N
X1149(size)X
X1251(table)X
X1384(\(left\))X
X1547 2718(Fill)N
X1643(Factor)X
X2268 2662(64)N
X1964(32)X
X1674(16)X
X1384(8)X
X1093(4)X
X4 Ds
X1 Dt
X900 2280 MXY
X1548 0 Dl
X900 1879 MXY
X1548 0 Dl
X900 1506 MXY
X1548 0 Dl
X1563 2902 MXY
X111 0 Dl
X-1 Ds
X900 MX
X110 0 Dl
X1425 2828(System)N
X983(User)X
X1895 2778 MXY
X 1895 2778 lineto
X 1950 2778 lineto
X 1950 2833 lineto
X 1895 2833 lineto
X 1895 2778 lineto
Xclosepath 21 1895 2778 1950 2833 Dp
X1342 MX
X 1342 2778 lineto
X 1397 2778 lineto
X 1397 2833 lineto
X 1342 2833 lineto
X 1342 2778 lineto
Xclosepath 14 1342 2778 1397 2833 Dp
X900 MX
X 900 2778 lineto
X 955 2778 lineto
X 955 2833 lineto
X 900 2833 lineto
X 900 2778 lineto
Xclosepath 3 900 2778 955 2833 Dp
X5 Dt
X2283 2211 MXY
X96 0 Dl
X1992 MX
X97 0 Dl
X1702 MX
X97 0 Dl
X1411 2252 MXY
X97 0 Dl
X4 Ds
X1 Dt
X2283 2211 MXY
X 2283 2211 lineto
X 2379 2211 lineto
X 2379 2252 lineto
X 2283 2252 lineto
X 2283 2211 lineto
Xclosepath 14 2283 2211 2379 2252 Dp
X1992 MX
X 1992 2211 lineto
X 2089 2211 lineto
X 2089 2252 lineto
X 1992 2252 lineto
X 1992 2211 lineto
Xclosepath 14 1992 2211 2089 2252 Dp
X1702 MX
X 1702 2211 lineto
X 1799 2211 lineto
X 1799 2252 lineto
X 1702 2252 lineto
X 1702 2211 lineto
Xclosepath 14 1702 2211 1799 2252 Dp
X1411 2252 MXY
X 1411 2252 lineto
X 1508 2252 lineto
X 1508 2294 lineto
X 1411 2294 lineto
X 1411 2252 lineto
Xclosepath 14 1411 2252 1508 2294 Dp
X2283 MX
X 2283 2252 lineto
X 2379 2252 lineto
X 2379 2612 lineto
X 2283 2612 lineto
X 2283 2252 lineto
Xclosepath 3 2283 2252 2379 2612 Dp
X1992 MX
X 1992 2252 lineto
X 2089 2252 lineto
X 2089 2612 lineto
X 1992 2612 lineto
X 1992 2252 lineto
Xclosepath 3 1992 2252 2089 2612 Dp
X1702 MX
X 1702 2252 lineto
X 1799 2252 lineto
X 1799 2612 lineto
X 1702 2612 lineto
X 1702 2252 lineto
Xclosepath 3 1702 2252 1799 2612 Dp
X1411 2294 MXY
X 1411 2294 lineto
X 1508 2294 lineto
X 1508 2612 lineto
X 1411 2612 lineto
X 1411 2294 lineto
Xclosepath 3 1411 2294 1508 2612 Dp
X-1 Ds
X2158 2238 MXY
X 2158 2238 lineto
X 2255 2238 lineto
X 2255 2252 lineto
X 2158 2252 lineto
X 2158 2238 lineto
Xclosepath 21 2158 2238 2255 2252 Dp
X1868 MX
X 1868 2238 lineto
X 1965 2238 lineto
X 1965 2280 lineto
X 1868 2280 lineto
X 1868 2238 lineto
Xclosepath 21 1868 2238 1965 2280 Dp
X1577 MX
X 1577 2238 lineto
X 1674 2238 lineto
X 1674 2308 lineto
X 1577 2308 lineto
X 1577 2238 lineto
Xclosepath 21 1577 2238 1674 2308 Dp
X1287 2308 MXY
X 1287 2308 lineto
X 1287 2280 lineto
X 1384 2280 lineto
X 1384 2308 lineto
X 1287 2308 lineto
Xclosepath 21 1287 2280 1384 2308 Dp
X2158 2280 MXY
X 2158 2280 lineto
X 2158 2252 lineto
X 2255 2252 lineto
X 2255 2280 lineto
X 2158 2280 lineto
Xclosepath 14 2158 2252 2255 2280 Dp
X1868 2308 MXY
X 1868 2308 lineto
X 1868 2280 lineto
X 1965 2280 lineto
X 1965 2308 lineto
X 1868 2308 lineto
Xclosepath 14 1868 2280 1965 2308 Dp
X1577 2335 MXY
X 1577 2335 lineto
X 1577 2308 lineto
X 1674 2308 lineto
X 1674 2335 lineto
X 1577 2335 lineto
Xclosepath 14 1577 2308 1674 2335 Dp
X1287 2363 MXY
X 1287 2363 lineto
X 1287 2308 lineto
X 1384 2308 lineto
X 1384 2363 lineto
X 1287 2363 lineto
Xclosepath 14 1287 2308 1384 2363 Dp
X2158 2280 MXY
X 2158 2280 lineto
X 2255 2280 lineto
X 2255 2612 lineto
X 2158 2612 lineto
X 2158 2280 lineto
Xclosepath 3 2158 2280 2255 2612 Dp
X1868 2308 MXY
X 1868 2308 lineto
X 1965 2308 lineto
X 1965 2612 lineto
X 1868 2612 lineto
X 1868 2308 lineto
Xclosepath 3 1868 2308 1965 2612 Dp
X1577 2335 MXY
X 1577 2335 lineto
X 1674 2335 lineto
X 1674 2612 lineto
X 1577 2612 lineto
X 1577 2335 lineto
Xclosepath 3 1577 2335 1674 2612 Dp
X1287 2363 MXY
X 1287 2363 lineto
X 1384 2363 lineto
X 1384 2612 lineto
X 1287 2612 lineto
X 1287 2363 lineto
Xclosepath 3 1287 2363 1384 2612 Dp
X4 Ds
X1121 2066 MXY
X 1121 2066 lineto
X 1218 2066 lineto
X 1224 2080 lineto
X 1127 2080 lineto
X 1121 2066 lineto
Xclosepath 21 1121 2066 1224 2080 Dp
X2080 MY
X 1121 2080 lineto
X 1218 2080 lineto
X 1218 2273 lineto
X 1121 2273 lineto
X 1121 2080 lineto
Xclosepath 14 1121 2080 1218 2273 Dp
X2273 MY
X 1121 2273 lineto
X 1218 2273 lineto
X 1218 2612 lineto
X 1121 2612 lineto
X 1121 2273 lineto
Xclosepath 3 1121 2273 1218 2612 Dp
X-1 Ds
X997 1589 MXY
X 997 1589 lineto
X 1093 1589 lineto
X 1093 1644 lineto
X 997 1644 lineto
X 997 1589 lineto
Xclosepath 21 997 1589 1093 1644 Dp
X1644 MY
X 997 1644 lineto
X 1093 1644 lineto
X 1093 2280 lineto
X 997 2280 lineto
X 997 1644 lineto
Xclosepath 14 997 1644 1093 2280 Dp
X2280 MY
X 997 2280 lineto
X 1093 2280 lineto
X 1093 2612 lineto
X 997 2612 lineto
X 997 2280 lineto
Xclosepath 3 997 2280 1093 2612 Dp
X10 s
X719 2093(s)N
X712 2037(d)N
X712 1982(n)N
X714 1927(o)N
X716 1872(c)N
X716 1816(e)N
X712 1761(S)N
X804 2286(10)N
X804 1899(20)N
X804 1540(30)N
X3 Dt
X900 1506 MXY
X0 1106 Dl
X1548 0 Dl
X7 s
X1978 2828(Elapsed)N
X1701 2925(Dynamically)N
X2018(grown)X
X2184(table)X
X2317(\(right\))X
X3 Dt
X-1 Ds
X8 s
X720 3180(Figure)N
X934(6:)X
X1 f
X1020(The)X
X1152(total)X
X1299(regions)X
X1520(indicate)X
X1755(the)X
X1865(difference)X
X2154(between)X
X2398(the)X
X720 3268(elapsed)N
X931(time)X
X1065(and)X
X1177(the)X
X1275(sum)X
X1402(of)X
X1475(the)X
X1573(system)X
X1771(and)X
X1883(user)X
X2008(time.)X
X2173(The)X
X2291(left)X
X2395(bar)X
X720 3356(of)N
X798(each)X
X939(set)X
X1035(depicts)X
X1241(the)X
X1344(timing)X
X1537(of)X
X1615(the)X
X1718(test)X
X1831(run)X
X1940(when)X
X2102(the)X
X2204(number)X
X2423(of)X
X720 3444(entries)N
X910(is)X
X973(known)X
X1167(in)X
X1237(advance.)X
X1496(The)X
X1614(right)X
X1754(bars)X
X1879(depict)X
X2054(the)X
X2151(timing)X
X2338(when)X
X720 3532(the)N
X814(\256le)X
X912(is)X
X971(grown)X
X1150(from)X
X1290(a)X
X1334(single)X
X1503(bucket.)X
X10 s
X10 f
X720 3708 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X1 f
X892 3910(Since)N
X1131(this)X
X1307(hashing)X
X1617(package)X
X1942(provides)X
X2279(buffer)X
X720 3998(management,)N
X1188(the)X
X1323(amount)X
X1600(of)X
X1704(space)X
X1920(allocated)X
X2247(for)X
X2378(the)X
X720 4086(buffer)N
X948(pool)X
X1121(may)X
X1290(be)X
X1397(speci\256ed)X
X1713(by)X
X1824(the)X
X1953(user.)X
X2157(Using)X
X2378(the)X
X720 4174(same)N
X910(data)X
X1069(set)X
X1183(and)X
X1324(test)X
X1459(procedure)X
X1805(as)X
X1896(used)X
X2067(to)X
X2153(derive)X
X2378(the)X
X720 4262(graphs)N
X962(in)X
X1052(Figures)X
X1320(5a-c,)X
X1507(Figure)X
X1744(7)X
X1812(shows)X
X2039(the)X
X2164(impact)X
X2409(of)X
X720 4350(varying)N
X997(the)X
X1126(size)X
X1282(of)X
X1380(the)X
X1509(buffer)X
X1737(pool.)X
X1950(The)X
X2106(bucket)X
X2351(size)X
X720 4438(was)N
X873(set)X
X989(to)X
X1078(256)X
X1225(bytes)X
X1421(and)X
X1564(the)X
X1689(\256ll)X
X1804(factor)X
X2019(was)X
X2171(set)X
X2287(to)X
X2376(16.)X
X720 4526(The)N
X869(buffer)X
X1090(pool)X
X1256(size)X
X1404(was)X
X1552(varied)X
X1776(from)X
X1955(0)X
X2018(\(the)X
X2166(minimum)X
X720 4614(number)N
X986(of)X
X1074(pages)X
X1277(required)X
X1565(to)X
X1647(be)X
X1743(buffered\))X
X2063(to)X
X2145(1M.)X
X2316(With)X
X720 4702(1M)N
X854(of)X
X944(buffer)X
X1164(space,)X
X1386(the)X
X1507(package)X
X1794(performed)X
X2151(no)X
X2253(I/O)X
X2382(for)X
X720 4790(this)N
X871(data)X
X1040(set.)X
X1204(As)X
X1328(Figure)X
X1572(7)X
X1647(illustrates,)X
X2013(increasing)X
X2378(the)X
X720 4878(buffer)N
X944(pool)X
X1113(size)X
X1265(can)X
X1404(have)X
X1583(a)X
X1646(dramatic)X
X1954(affect)X
X2165(on)X
X2271(result-)X
X720 4966(ing)N
X842(performance.)X
X2 f
X8 s
X1269 4941(7)N
X1 f
X16 s
X720 5353 MXY
X864 0 Dl
X2 f
X8 s
X760 5408(7)N
X1 f
X9 s
X826 5433(Some)N
X1024(allocators)X
X1338(are)X
X1460(extremely)X
X1782(inef\256cient)X
X2107(at)X
X2192(allocating)X
X720 5513(memory.)N
X1029(If)X
X1110(you)X
X1251(\256nd)X
X1396(that)X
X1536(applications)X
X1916(are)X
X2036(running)X
X2292(out)X
X2416(of)X
X720 5593(memory)N
X1005(before)X
X1234(you)X
X1386(think)X
X1578(they)X
X1746(should,)X
X2000(try)X
X2124(varying)X
X2388(the)X
X720 5673(pagesize)N
X986(to)X
X1060(get)X
X1166(better)X
X1348(utilization)X
X1658(from)X
X1816(the)X
X1922(memory)X
X2180(allocator.)X
X10 s
X2830 1975 MXY
X0 -28 Dl
X28 0 Dl
X0 28 Dl
X-28 0 Dl
X2853 2004 MXY
X0 -27 Dl
X28 0 Dl
X0 27 Dl
X-28 0 Dl
X2876 2016 MXY
X0 -27 Dl
X27 0 Dl
X0 27 Dl
X-27 0 Dl
X2922 1998 MXY
X0 -27 Dl
X27 0 Dl
X0 27 Dl
X-27 0 Dl
X2967 2025 MXY
X0 -28 Dl
X28 0 Dl
X0 28 Dl
X-28 0 Dl
X3013 2031 MXY
X0 -28 Dl
X28 0 Dl
X0 28 Dl
X-28 0 Dl
X3059 MX
X0 -28 Dl
X27 0 Dl
X0 28 Dl
X-27 0 Dl
X3196 2052 MXY
X0 -28 Dl
X27 0 Dl
X0 28 Dl
X-27 0 Dl
X3561 2102 MXY
X0 -28 Dl
X28 0 Dl
X0 28 Dl
X-28 0 Dl
X4292 2105 MXY
X0 -28 Dl
X27 0 Dl
X0 28 Dl
X-27 0 Dl
X4 Ds
X1 Dt
X2844 1961 MXY
X23 30 Dl
X23 12 Dl
X45 -18 Dl
X46 26 Dl
X46 6 Dl
X45 0 Dl
X137 21 Dl
X366 50 Dl
X730 3 Dl
X9 s
X4227 2158(User)N
X-1 Ds
X3 Dt
X2830 1211 MXY
X27 Dc
X2853 1261 MXY
X27 Dc
X2876 1267 MXY
X27 Dc
X2921 1341 MXY
X27 Dc
X2967 1385 MXY
X27 Dc
X3013 1450 MXY
X27 Dc
X3059 1497 MXY
X27 Dc
X3196 1686 MXY
X27 Dc
X3561 2109 MXY
X27 Dc
X4292 2295 MXY
X27 Dc
X20 Ds
X1 Dt
X2844 1211 MXY
X23 50 Dl
X23 6 Dl
X45 74 Dl
X46 44 Dl
X46 65 Dl
X45 47 Dl
X137 189 Dl
X366 423 Dl
X730 186 Dl
X4181 2270(System)N
X-1 Ds
X3 Dt
X2844 583 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2867 672 MXY
X0 27 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X2890 701 MXY
X0 28 Dl
X0 -14 Dl
X13 0 Dl
X-27 0 Dl
X2935 819 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-27 0 Dl
X2981 849 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X3027 908 MXY
X0 27 Dl
X0 -13 Dl
X14 0 Dl
X-28 0 Dl
X3072 1026 MXY
X0 27 Dl
X0 -13 Dl
X14 0 Dl
X-27 0 Dl
X3209 1292 MXY
X0 27 Dl
X0 -14 Dl
X14 0 Dl
X-27 0 Dl
X3575 1823 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-28 0 Dl
X4305 2059 MXY
X0 28 Dl
X0 -14 Dl
X14 0 Dl
X-27 0 Dl
X5 Dt
X2844 597 MXY
X23 88 Dl
X23 30 Dl
X45 118 Dl
X46 30 Dl
X46 59 Dl
X45 118 Dl
X137 265 Dl
X366 532 Dl
X730 236 Dl
X4328 2103(Total)N
X2844 2310 MXY
X1461 0 Dl
X2844 MX
X0 -1772 Dl
X2310 MY
X0 18 Dl
X4 Ds
X1 Dt
X2310 MY
X0 -1772 Dl
X2826 2416(0)N
X-1 Ds
X5 Dt
X3209 2310 MXY
X0 18 Dl
X4 Ds
X1 Dt
X2310 MY
X0 -1772 Dl
X3155 2416(256)N
X-1 Ds
X5 Dt
X3575 2310 MXY
X0 18 Dl
X4 Ds
X1 Dt
X2310 MY
X0 -1772 Dl
X3521 2416(512)N
X-1 Ds
X5 Dt
X3940 2310 MXY
X0 18 Dl
X4 Ds
X1 Dt
X2310 MY
X0 -1772 Dl
X3886 2416(768)N
X-1 Ds
X5 Dt
X4305 2310 MXY
X0 18 Dl
X4 Ds
X1 Dt
X2310 MY
X0 -1772 Dl
X4233 2416(1024)N
X-1 Ds
X5 Dt
X2844 2310 MXY
X-18 0 Dl
X4 Ds
X1 Dt
X2844 MX
X1461 0 Dl
X2771 2340(0)N
X-1 Ds
X5 Dt
X2844 2014 MXY
X-18 0 Dl
X2844 1719 MXY
X-18 0 Dl
X4 Ds
X1 Dt
X2844 MX
X1461 0 Dl
X2735 1749(20)N
X-1 Ds
X5 Dt
X2844 1423 MXY
X-18 0 Dl
X2844 1128 MXY
X-18 0 Dl
X4 Ds
X1 Dt
X2844 MX
X1461 0 Dl
X2735 1158(40)N
X-1 Ds
X5 Dt
X2844 833 MXY
X-18 0 Dl
X2844 538 MXY
X-18 0 Dl
X4 Ds
X1 Dt
X2844 MX
X1461 0 Dl
X2735 568(60)N
X3239 2529(Buffer)N
X3445(Pool)X
X3595(Size)X
X3737(\(in)X
X3835(K\))X
X2695 1259(S)N
X2699 1324(e)N
X2699 1388(c)N
X2697 1452(o)N
X2697 1517(n)N
X2697 1581(d)N
X2701 1645(s)N
X3 Dt
X-1 Ds
X3 f
X8 s
X2706 2773(Figure)N
X2908(7:)X
X1 f
X2982(User)X
X3123(time)X
X3258(is)X
X3322(virtually)X
X3560(insensitive)X
X3854(to)X
X3924(the)X
X4022(amount)X
X4234(of)X
X4307(buffer)X
X2706 2861(pool)N
X2852(available,)X
X3130(however,)X
X3396(both)X
X3541(system)X
X3750(time)X
X3895(and)X
X4018(elapsed)X
X4240(time)X
X4385(are)X
X2706 2949(inversely)N
X2960(proportional)X
X3296(to)X
X3366(the)X
X3464(size)X
X3583(of)X
X3656(the)X
X3753(buffer)X
X3927(pool.)X
X4092(Even)X
X4242(for)X
X4335(large)X
X2706 3037(data)N
X2831(sets)X
X2946(where)X
X3120(one)X
X3230(expects)X
X3439(few)X
X3552(collisions,)X
X3832(specifying)X
X4116(a)X
X4162(large)X
X4307(buffer)X
X2706 3125(pool)N
X2836(dramatically)X
X3171(improves)X
X3425(performance.)X
X10 s
X10 f
X2706 3301 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X3 f
X3175 3543(Enhanced)N
X3536(Functionality)X
X1 f
X2878 3675(This)N
X3046(hashing)X
X3320(package)X
X3609(provides)X
X3910(a)X
X3971(set)X
X4085(of)X
X4177(compati-)X
X2706 3763(bility)N
X2895(routines)X
X3174(to)X
X3257(implement)X
X3620(the)X
X2 f
X3739(ndbm)X
X1 f
X3937(interface.)X
X4279(How-)X
X2706 3851(ever,)N
X2893(when)X
X3095(the)X
X3220(native)X
X3443(interface)X
X3752(is)X
X3832(used,)X
X4026(the)X
X4151(following)X
X2706 3939(additional)N
X3046(functionality)X
X3475(is)X
X3548(provided:)X
X10 f
X2798 4071(g)N
X1 f
X2946(Inserts)X
X3197(never)X
X3413(fail)X
X3556(because)X
X3847(too)X
X3985(many)X
X4199(keys)X
X2946 4159(hash)N
X3113(to)X
X3195(the)X
X3313(same)X
X3498(value.)X
X10 f
X2798 4247(g)N
X1 f
X2946(Inserts)X
X3187(never)X
X3393(fail)X
X3527(because)X
X3808(key)X
X3950(and/or)X
X4181(asso-)X
X2946 4335(ciated)N
X3158(data)X
X3312(is)X
X3385(too)X
X3507(large)X
X10 f
X2798 4423(g)N
X1 f
X2946(Hash)X
X3131(functions)X
X3449(may)X
X3607(be)X
X3703(user-speci\256ed.)X
X10 f
X2798 4511(g)N
X1 f
X2946(Multiple)X
X3268(pages)X
X3498(may)X
X3683(be)X
X3806(cached)X
X4077(in)X
X4186(main)X
X2946 4599(memory.)N
X2706 4731(It)N
X2801(also)X
X2976(provides)X
X3298(a)X
X3380(set)X
X3514(of)X
X3626(compatibility)X
X4097(routines)X
X4400(to)X
X2706 4819(implement)N
X3087(the)X
X2 f
X3224(hsearch)X
X1 f
X3516(interface.)X
X3876(Again,)X
X4130(the)X
X4266(native)X
X2706 4907(interface)N
X3008(offers)X
X3216(enhanced)X
X3540(functionality:)X
X10 f
X2798 5039(g)N
X1 f
X2946(Files)X
X3121(may)X
X3279(grow)X
X3464(beyond)X
X2 f
X3720(nelem)X
X1 f
X3932(elements.)X
X10 f
X2798 5127(g)N
X1 f
X2946(Multiple)X
X3247(hash)X
X3420(tables)X
X3632(may)X
X3795(be)X
X3896(accessed)X
X4203(con-)X
X2946 5215(currently.)N
X10 f
X2798 5303(g)N
X1 f
X2946(Hash)X
X3134(tables)X
X3344(may)X
X3505(be)X
X3604(stored)X
X3823(and)X
X3962(accessed)X
X4266(on)X
X2946 5391(disk.)N
X10 f
X2798 5479(g)N
X1 f
X2946(Hash)X
X3155(functions)X
X3497(may)X
X3679(be)X
X3799(user-speci\256ed)X
X4288(at)X
X2946 5567(runtime.)N
X3 f
X720 5960(USENIX)N
X9 f
X1042(-)X
X3 f
X1106(Winter)X
X1371('91)X
X9 f
X1498(-)X
X3 f
X1562(Dallas,)X
X1815(TX)X
X4424(9)X
X
X10 p
X%%Page: 10 10
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X432 258(A)N
X510(New)X
X682(Hashing)X
X985(Package)X
X1290(for)X
X1413(UNIX)X
X3663(Seltzer)X
X3920(&)X
X4007(Yigit)X
X459 538(Relative)N
X760(Performance)X
X1227(of)X
X1314(the)X
X1441(New)X
X1613(Implementation)X
X1 f
X604 670(The)N
X761(performance)X
X1200(testing)X
X1445(of)X
X1544(the)X
X1674(new)X
X1840(package)X
X2135(is)X
X432 758(divided)N
X711(into)X
X874(two)X
X1033(test)X
X1183(suites.)X
X1424(The)X
X1588(\256rst)X
X1751(suite)X
X1941(of)X
X2046(tests)X
X432 846(requires)N
X727(that)X
X882(the)X
X1015(tables)X
X1237(be)X
X1348(read)X
X1522(from)X
X1713(and)X
X1864(written)X
X2126(to)X
X432 934(disk.)N
X640(In)X
X742(these)X
X942(tests,)X
X1139(the)X
X1272(basis)X
X1467(for)X
X1595(comparison)X
X2003(is)X
X2090(the)X
X432 1022(4.3BSD-Reno)N
X908(version)X
X1169(of)X
X2 f
X1260(ndbm)X
X1 f
X1438(.)X
X1502(Based)X
X1722(on)X
X1826(the)X
X1948(designs)X
X432 1110(of)N
X2 f
X521(sdbm)X
X1 f
X712(and)X
X2 f
X850(gdbm)X
X1 f
X1028(,)X
X1070(they)X
X1230(are)X
X1351(expected)X
X1659(to)X
X1743(perform)X
X2024(simi-)X
X432 1198(larly)N
X605(to)X
X2 f
X693(ndbm)X
X1 f
X871(,)X
X917(and)X
X1059(we)X
X1179(do)X
X1285(not)X
X1413(show)X
X1608(their)X
X1781(performance)X
X432 1286(numbers.)N
X800(The)X
X977(second)X
X1252(suite)X
X1454(contains)X
X1772(the)X
X1921(memory)X
X432 1374(resident)N
X712(test)X
X849(which)X
X1071(does)X
X1243(not)X
X1370(require)X
X1623(that)X
X1768(the)X
X1891(\256les)X
X2049(ever)X
X432 1462(be)N
X533(written)X
X784(to)X
X870(disk,)X
X1047(only)X
X1213(that)X
X1357(hash)X
X1528(tables)X
X1739(may)X
X1901(be)X
X2001(mani-)X
X432 1550(pulated)N
X692(in)X
X778(main)X
X961(memory.)X
X1291(In)X
X1381(this)X
X1519(test,)X
X1673(we)X
X1790(compare)X
X2090(the)X
X432 1638(performance)N
X859(to)X
X941(that)X
X1081(of)X
X1168(the)X
X2 f
X1286(hsearch)X
X1 f
X1560(routines.)X
X604 1752(For)N
X760(both)X
X947(suites,)X
X1194(two)X
X1358(different)X
X1679(databases)X
X2031(were)X
X432 1840(used.)N
X656(The)X
X818(\256rst)X
X979(is)X
X1069(the)X
X1204(dictionary)X
X1566(database)X
X1880(described)X
X432 1928(previously.)N
X836(The)X
X987(second)X
X1236(was)X
X1386(constructed)X
X1781(from)X
X1962(a)X
X2023(pass-)X
X432 2016(word)N
X647(\256le)X
X799(with)X
X990(approximately)X
X1502(300)X
X1671(accounts.)X
X2041(Two)X
X432 2104(records)N
X700(were)X
X887(constructed)X
X1287(for)X
X1411(each)X
X1589(account.)X
X1909(The)X
X2064(\256rst)X
X432 2192(used)N
X604(the)X
X727(logname)X
X1028(as)X
X1120(the)X
X1243(key)X
X1384(and)X
X1525(the)X
X1648(remainder)X
X1999(of)X
X2090(the)X
X432 2280(password)N
X768(entry)X
X965(for)X
X1091(the)X
X1221(data.)X
X1427(The)X
X1584(second)X
X1839(was)X
X1996(keyed)X
X432 2368(by)N
X541(uid)X
X672(and)X
X817(contained)X
X1157(the)X
X1283(entire)X
X1494(password)X
X1825(entry)X
X2018(as)X
X2113(its)X
X432 2456(data)N
X589(\256eld.)X
X794(The)X
X942(tests)X
X1107(were)X
X1287(all)X
X1389(run)X
X1518(on)X
X1620(the)X
X1740(HP)X
X1864(9000)X
X2046(with)X
X432 2544(the)N
X574(same)X
X783(con\256guration)X
X1254(previously)X
X1636(described.)X
X2027(Each)X
X432 2632(test)N
X576(was)X
X734(run)X
X874(\256ve)X
X1027(times)X
X1232(and)X
X1380(the)X
X1510(timing)X
X1750(results)X
X1991(of)X
X2090(the)X
X432 2720(runs)N
X602(were)X
X791(averaged.)X
X1154(The)X
X1311(variance)X
X1616(across)X
X1849(the)X
X1979(5)X
X2050(runs)X
X432 2808(was)N
X591(approximately)X
X1088(1%)X
X1229(of)X
X1330(the)X
X1462(average)X
X1746(yielding)X
X2041(95%)X
X432 2896(con\256dence)N
X800(intervals)X
X1096(of)X
X1183(approximately)X
X1666(2%.)X
X3 f
X1021 3050(Disk)N
X1196(Based)X
X1420(Tests)X
X1 f
X604 3182(In)N
X693(these)X
X880(tests,)X
X1064(we)X
X1180(use)X
X1308(a)X
X1365(bucket)X
X1600(size)X
X1746(of)X
X1834(1024)X
X2015(and)X
X2152(a)X
X432 3270(\256ll)N
X540(factor)X
X748(of)X
X835(32.)X
X3 f
X432 3384(create)N
X663(test)X
X1 f
X547 3498(The)N
X703(keys)X
X881(are)X
X1011(entered)X
X1279(into)X
X1433(the)X
X1561(hash)X
X1738(table,)X
X1944(and)X
X2090(the)X
X547 3586(\256le)N
X669(is)X
X742(\257ushed)X
X993(to)X
X1075(disk.)X
X3 f
X432 3700(read)N
X608(test)X
X1 f
X547 3814(A)N
X640(lookup)X
X897(is)X
X984(performed)X
X1353(for)X
X1481(each)X
X1663(key)X
X1813(in)X
X1909(the)X
X2041(hash)X
X547 3902(table.)N
X3 f
X432 4016(verify)N
X653(test)X
X1 f
X547 4130(A)N
X640(lookup)X
X897(is)X
X984(performed)X
X1353(for)X
X1481(each)X
X1663(key)X
X1813(in)X
X1909(the)X
X2041(hash)X
X547 4218(table,)N
X759(and)X
X911(the)X
X1045(data)X
X1215(returned)X
X1519(is)X
X1608(compared)X
X1961(against)X
X547 4306(that)N
X687(originally)X
X1018(stored)X
X1234(in)X
X1316(the)X
X1434(hash)X
X1601(table.)X
X3 f
X432 4420(sequential)N
X798(retrieve)X
X1 f
X547 4534(All)N
X674(keys)X
X846(are)X
X970(retrieved)X
X1281(in)X
X1367(sequential)X
X1716(order)X
X1910(from)X
X2090(the)X
X547 4622(hash)N
X724(table.)X
X950(The)X
X2 f
X1105(ndbm)X
X1 f
X1313(interface)X
X1625(allows)X
X1863(sequential)X
X547 4710(retrieval)N
X848(of)X
X948(the)X
X1079(keys)X
X1259(from)X
X1448(the)X
X1578(database,)X
X1907(but)X
X2041(does)X
X547 4798(not)N
X701(return)X
X945(the)X
X1094(data)X
X1279(associated)X
X1660(with)X
X1853(each)X
X2052(key.)X
X547 4886(Therefore,)N
X929(we)X
X1067(compare)X
X1388(the)X
X1530(performance)X
X1980(of)X
X2090(the)X
X547 4974(new)N
X703(package)X
X989(to)X
X1073(two)X
X1215(different)X
X1514(runs)X
X1674(of)X
X2 f
X1763(ndbm)X
X1 f
X1941(.)X
X2002(In)X
X2090(the)X
X547 5062(\256rst)N
X697(case,)X
X2 f
X882(ndbm)X
X1 f
X1086(returns)X
X1335(only)X
X1503(the)X
X1627(keys)X
X1800(while)X
X2003(in)X
X2090(the)X
X547 5150(second,)N
X2 f
X823(ndbm)X
X1 f
X1034(returns)X
X1290(both)X
X1465(the)X
X1596(keys)X
X1776(and)X
X1924(the)X
X2054(data)X
X547 5238(\(requiring)N
X894(a)X
X956(second)X
X1204(call)X
X1345(to)X
X1432(the)X
X1555(library\).)X
X1861(There)X
X2074(is)X
X2152(a)X
X547 5326(single)N
X764(run)X
X897(for)X
X1017(the)X
X1141(new)X
X1300(library)X
X1539(since)X
X1729(it)X
X1798(returns)X
X2046(both)X
X547 5414(the)N
X665(key)X
X801(and)X
X937(the)X
X1055(data.)X
X3 f
X3014 538(In-Memory)N
X3431(Test)X
X1 f
X2590 670(This)N
X2757(test)X
X2892(uses)X
X3054(a)X
X3114(bucket)X
X3352(size)X
X3501(of)X
X3592(256)X
X3736(and)X
X3876(a)X
X3936(\256ll)X
X4048(fac-)X
X2418 758(tor)N
X2527(of)X
X2614(8.)X
X3 f
X2418 872(create/read)N
X2827(test)X
X1 f
X2533 986(In)N
X2627(this)X
X2769(test,)X
X2927(a)X
X2989(hash)X
X3162(table)X
X3344(is)X
X3423(created)X
X3682(by)X
X3788(inserting)X
X4094(all)X
X2533 1074(the)N
X2660(key/data)X
X2961(pairs.)X
X3186(Then)X
X3380(a)X
X3445(keyed)X
X3666(retrieval)X
X3963(is)X
X4044(per-)X
X2533 1162(formed)N
X2801(for)X
X2931(each)X
X3115(pair,)X
X3295(and)X
X3446(the)X
X3579(hash)X
X3761(table)X
X3952(is)X
X4040(des-)X
X2533 1250(troyed.)N
X3 f
X2938 1404(Performance)N
X3405(Results)X
X1 f
X2590 1536(Figures)N
X2866(8a)X
X2978(and)X
X3130(8b)X
X3246(show)X
X3451(the)X
X3585(user)X
X3755(time,)X
X3952(system)X
X2418 1624(time,)N
X2608(and)X
X2752(elapsed)X
X3021(time)X
X3191(for)X
X3312(each)X
X3487(test)X
X3625(for)X
X3746(both)X
X3915(the)X
X4040(new)X
X2418 1712(implementation)N
X2951(and)X
X3098(the)X
X3227(old)X
X3360(implementation)X
X3893(\()X
X2 f
X3920(hsearch)X
X1 f
X2418 1800(or)N
X2 f
X2528(ndbm)X
X1 f
X2706(,)X
X2769(whichever)X
X3147(is)X
X3243(appropriate\))X
X3678(as)X
X3787(well)X
X3967(as)X
X4076(the)X
X2418 1888(improvement.)N
X2929(The)X
X3098(improvement)X
X3569(is)X
X3666(expressed)X
X4027(as)X
X4138(a)X
X2418 1976(percentage)N
X2787(of)X
X2874(the)X
X2992(old)X
X3114(running)X
X3383(time:)X
X0 f
X8 s
X2418 2275(%)N
X2494(=)X
X2570(100)X
X2722(*)X
X2798 -0.4219(\(old_time)AX
X3178(-)X
X3254 -0.4219(new_time\))AX
X3634(/)X
X3710(old_time)X
X1 f
X10 s
X2590 2600(In)N
X2700(nearly)X
X2944(all)X
X3067(cases,)X
X3299(the)X
X3439(new)X
X3615(routines)X
X3915(perform)X
X2418 2688(better)N
X2628(than)X
X2793(the)X
X2918(old)X
X3047(routines)X
X3332(\(both)X
X2 f
X3527(hsearch)X
X1 f
X3807(and)X
X2 f
X3949(ndbm)X
X1 f
X4127(\).)X
X2418 2776(Although)N
X2755(the)X
X3 f
X2888(create)X
X1 f
X3134(tests)X
X3311(exhibit)X
X3567(superior)X
X3864(user)X
X4032(time)X
X2418 2864(performance,)N
X2869(the)X
X2991(test)X
X3126(time)X
X3292(is)X
X3369(dominated)X
X3731(by)X
X3834(the)X
X3955(cost)X
X4107(of)X
X2418 2952(writing)N
X2677(the)X
X2803(actual)X
X3023(\256le)X
X3153(to)X
X3243(disk.)X
X3444(For)X
X3583(the)X
X3709(large)X
X3897(database)X
X2418 3040(\(the)N
X2564(dictionary\),)X
X2957(this)X
X3093(completely)X
X3470(overwhelmed)X
X3927(the)X
X4045(sys-)X
X2418 3128(tem)N
X2570(time.)X
X2783(However,)X
X3129(for)X
X3254(the)X
X3383(small)X
X3587(data)X
X3752(base,)X
X3946(we)X
X4071(see)X
X2418 3216(that)N
X2569(differences)X
X2958(in)X
X3051(both)X
X3224(user)X
X3389(and)X
X3536(system)X
X3788(time)X
X3960(contri-)X
X2418 3304(bute)N
X2576(to)X
X2658(the)X
X2776(superior)X
X3059(performance)X
X3486(of)X
X3573(the)X
X3691(new)X
X3845(package.)X
X2590 3418(The)N
X3 f
X2764(read)X
X1 f
X2920(,)X
X3 f
X2989(verify)X
X1 f
X3190(,)X
X3259(and)X
X3 f
X3424(sequential)X
X1 f
X3818(results)X
X4075(are)X
X2418 3506(deceptive)N
X2758(for)X
X2883(the)X
X3012(small)X
X3216(database)X
X3524(since)X
X3720(the)X
X3849(entire)X
X4063(test)X
X2418 3594(ran)N
X2551(in)X
X2643(under)X
X2856(a)X
X2922(second.)X
X3215(However,)X
X3560(on)X
X3669(the)X
X3796(larger)X
X4013(data-)X
X2418 3682(base)N
X2590(the)X
X3 f
X2716(read)X
X1 f
X2900(and)X
X3 f
X3044(verify)X
X1 f
X3273(tests)X
X3443(bene\256t)X
X3689(from)X
X3873(the)X
X3999(cach-)X
X2418 3770(ing)N
X2546(of)X
X2639(buckets)X
X2910(in)X
X2998(the)X
X3122(new)X
X3282(package)X
X3571(to)X
X3658(improve)X
X3950(perfor-)X
X2418 3858(mance)N
X2666(by)X
X2784(over)X
X2965(80%.)X
X3169(Since)X
X3384(the)X
X3519(\256rst)X
X3 f
X3680(sequential)X
X1 f
X4063(test)X
X2418 3946(does)N
X2598(not)X
X2733(require)X
X2 f
X2994(ndbm)X
X1 f
X3205(to)X
X3299(return)X
X3523(the)X
X3653(data)X
X3819(values,)X
X4076(the)X
X2418 4034(user)N
X2573(time)X
X2735(is)X
X2808(lower)X
X3011(than)X
X3169(for)X
X3283(the)X
X3401(new)X
X3555(package.)X
X3879(However)X
X2418 4122(when)N
X2613(we)X
X2728(require)X
X2977(both)X
X3139(packages)X
X3454(to)X
X3536(return)X
X3748(data,)X
X3922(the)X
X4040(new)X
X2418 4210(package)N
X2702(excels)X
X2923(in)X
X3005(all)X
X3105(three)X
X3286(timings.)X
X2590 4324(The)N
X2773(small)X
X3003(database)X
X3337(runs)X
X3532(so)X
X3660(quickly)X
X3957(in)X
X4076(the)X
X2418 4412(memory-resident)N
X3000(case)X
X3173(that)X
X3326(the)X
X3457(results)X
X3699(are)X
X3831(uninterest-)X
X2418 4500(ing.)N
X2589(However,)X
X2933(for)X
X3056(the)X
X3183(larger)X
X3400(database)X
X3706(the)X
X3833(new)X
X3995(pack-)X
X2418 4588(age)N
X2567(pays)X
X2751(a)X
X2824(small)X
X3033(penalty)X
X3305(in)X
X3403(system)X
X3661(time)X
X3839(because)X
X4130(it)X
X2418 4676(limits)N
X2636(its)X
X2748(main)X
X2944(memory)X
X3247(utilization)X
X3607(and)X
X3759(swaps)X
X3991(pages)X
X2418 4764(out)N
X2550(to)X
X2642(temporary)X
X3002(storage)X
X3264(in)X
X3356(the)X
X3484(\256le)X
X3616(system)X
X3868(while)X
X4076(the)X
X2 f
X2418 4852(hsearch)N
X1 f
X2698(package)X
X2988(requires)X
X3273(that)X
X3419(the)X
X3543(application)X
X3924(allocate)X
X2418 4940(enough)N
X2692(space)X
X2909(for)X
X3041(all)X
X3159(key/data)X
X3468(pair.)X
X3670(However,)X
X4022(even)X
X2418 5028(with)N
X2600(the)X
X2738(system)X
X3000(time)X
X3182(penalty,)X
X3477(the)X
X3614(resulting)X
X3933(elapsed)X
X2418 5116(time)N
X2580(improves)X
X2898(by)X
X2998(over)X
X3161(50%.)X
X3 f
X432 5960(10)N
X2970(USENIX)X
X9 f
X3292(-)X
X3 f
X3356(Winter)X
X3621('91)X
X9 f
X3748(-)X
X3 f
X3812(Dallas,)X
X4065(TX)X
X
X11 p
X%%Page: 11 11
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X720 258(Seltzer)N
X977(&)X
X1064(Yigit)X
X3278(A)X
X3356(New)X
X3528(Hashing)X
X3831(Package)X
X4136(for)X
X4259(UNIX)X
X1 f
X10 f
X908 454(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2 f
X1379 546(hash)N
X1652(ndbm)X
X1950(%change)X
X1 f
X10 f
X908 550(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X948 642(CREATE)N
X10 f
X908 646(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X1125 738(user)N
X1424(6.4)X
X1671(12.2)X
X2073(48)X
X1157 826(sys)N
X1384(32.5)X
X1671(34.7)X
X2113(6)X
X3 f
X1006 914(elapsed)N
X10 f
X1310 922(c)N
X890(c)Y
X810(c)Y
X730(c)Y
X3 f
X1384 914(90.4)N
X10 f
X1581 922(c)N
X890(c)Y
X810(c)Y
X730(c)Y
X3 f
X1671 914(99.6)N
X10 f
X1883 922(c)N
X890(c)Y
X810(c)Y
X730(c)Y
X3 f
X2113 914(9)N
X1 f
X10 f
X908 910(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X908 926(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X948 1010(READ)N
X10 f
X908 1014(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X1125 1106(user)N
X1424(3.4)X
X1711(6.1)X
X2073(44)X
X1157 1194(sys)N
X1424(1.2)X
X1671(15.3)X
X2073(92)X
X3 f
X1006 1282(elapsed)N
X10 f
X1310 1290(c)N
X1258(c)Y
X1178(c)Y
X1098(c)Y
X3 f
X1424 1282(4.0)N
X10 f
X1581 1290(c)N
X1258(c)Y
X1178(c)Y
X1098(c)Y
X3 f
X1671 1282(21.2)N
X10 f
X1883 1290(c)N
X1258(c)Y
X1178(c)Y
X1098(c)Y
X3 f
X2073 1282(81)N
X1 f
X10 f
X908 1278(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X908 1294(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X948 1378(VERIFY)N
X10 f
X908 1382(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X1125 1474(user)N
X1424(3.5)X
X1711(6.3)X
X2073(44)X
X1157 1562(sys)N
X1424(1.2)X
X1671(15.3)X
X2073(92)X
X3 f
X1006 1650(elapsed)N
X10 f
X1310 1658(c)N
X1626(c)Y
X1546(c)Y
X1466(c)Y
X3 f
X1424 1650(4.0)N
X10 f
X1581 1658(c)N
X1626(c)Y
X1546(c)Y
X1466(c)Y
X3 f
X1671 1650(21.2)N
X10 f
X1883 1658(c)N
X1626(c)Y
X1546(c)Y
X1466(c)Y
X3 f
X2073 1650(81)N
X1 f
X10 f
X908 1646(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X908 1662(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X948 1746(SEQUENTIAL)N
X10 f
X908 1750(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X1125 1842(user)N
X1424(2.7)X
X1711(1.9)X
X2046(-42)X
X1157 1930(sys)N
X1424(0.7)X
X1711(3.9)X
X2073(82)X
X3 f
X1006 2018(elapsed)N
X10 f
X1310 2026(c)N
X1994(c)Y
X1914(c)Y
X1834(c)Y
X3 f
X1424 2018(3.0)N
X10 f
X1581 2026(c)N
X1994(c)Y
X1914(c)Y
X1834(c)Y
X3 f
X1711 2018(5.0)N
X10 f
X1883 2026(c)N
X1994(c)Y
X1914(c)Y
X1834(c)Y
X3 f
X2073 2018(40)N
X1 f
X10 f
X908 2014(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X908 2030(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X948 2114(SEQUENTIAL)N
X1467(\(with)X
X1656(data)X
X1810(retrieval\))X
X10 f
X908 2118(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X1125 2210(user)N
X1424(2.7)X
X1711(8.2)X
X2073(67)X
X1157 2298(sys)N
X1424(0.7)X
X1711(4.3)X
X2073(84)X
X3 f
X1006 2386(elapsed)N
X1424(3.0)X
X1671(12.0)X
X2073(75)X
X1 f
X10 f
X908 2390(i)N
X927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X899 2394(c)N
X2378(c)Y
X2298(c)Y
X2218(c)Y
X2138(c)Y
X2058(c)Y
X1978(c)Y
X1898(c)Y
X1818(c)Y
X1738(c)Y
X1658(c)Y
X1578(c)Y
X1498(c)Y
X1418(c)Y
X1338(c)Y
X1258(c)Y
X1178(c)Y
X1098(c)Y
X1018(c)Y
X938(c)Y
X858(c)Y
X778(c)Y
X698(c)Y
X618(c)Y
X538(c)Y
X1310 2394(c)N
X2362(c)Y
X2282(c)Y
X2202(c)Y
X1581 2394(c)N
X2362(c)Y
X2282(c)Y
X2202(c)Y
X1883 2394(c)N
X2362(c)Y
X2282(c)Y
X2202(c)Y
X2278 2394(c)N
X2378(c)Y
X2298(c)Y
X2218(c)Y
X2138(c)Y
X2058(c)Y
X1978(c)Y
X1898(c)Y
X1818(c)Y
X1738(c)Y
X1658(c)Y
X1578(c)Y
X1498(c)Y
X1418(c)Y
X1338(c)Y
X1258(c)Y
X1178(c)Y
X1098(c)Y
X1018(c)Y
X938(c)Y
X858(c)Y
X778(c)Y
X698(c)Y
X618(c)Y
X538(c)Y
X905 2574(i)N
X930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2 f
X1318 2666(hash)N
X1585(hsearch)X
X1953(%change)X
X1 f
X10 f
X905 2670(i)N
X930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X945 2762(CREATE/READ)N
X10 f
X905 2766(i)N
X930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X1064 2858(user)N
X1343(6.6)X
X1642(17.2)X
X2096(62)X
X1096 2946(sys)N
X1343(1.1)X
X1682(0.3)X
X2029(-266)X
X3 f
X945 3034(elapsed)N
X1343(7.8)X
X1642(17.0)X
X2096(54)X
X1 f
X10 f
X905 3038(i)N
X930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X896 3050(c)N
X2978(c)Y
X2898(c)Y
X2818(c)Y
X2738(c)Y
X2658(c)Y
X1249 3034(c)N
X3010(c)Y
X2930(c)Y
X2850(c)Y
X1520 3034(c)N
X3010(c)Y
X2930(c)Y
X2850(c)Y
X1886 3034(c)N
X3010(c)Y
X2930(c)Y
X2850(c)Y
X2281 3050(c)N
X2978(c)Y
X2898(c)Y
X2818(c)Y
X2738(c)Y
X2658(c)Y
X3 f
X720 3174(Figure)N
X967(8a:)X
X1 f
X1094(Timing)X
X1349(results)X
X1578(for)X
X1692(the)X
X1810(dictionary)X
X2155(database.)X
X10 f
X720 3262 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X3 f
X1407 3504(Conclusion)N
X1 f
X892 3636(This)N
X1063(paper)X
X1271(has)X
X1407(presented)X
X1744(the)X
X1871(design,)X
X2129(implemen-)X
X720 3724(tation)N
X928(and)X
X1070(performance)X
X1503(of)X
X1596(a)X
X1658(new)X
X1818(hashing)X
X2093(package)X
X2382(for)X
X720 3812(UNIX.)N
X993(The)X
X1150(new)X
X1316(package)X
X1612(provides)X
X1919(a)X
X1986(superset)X
X2280(of)X
X2378(the)X
X720 3900(functionality)N
X1159(of)X
X1255(existing)X
X1537(hashing)X
X1815(packages)X
X2139(and)X
X2284(incor-)X
X720 3988(porates)N
X975(additional)X
X1318(features)X
X1596(such)X
X1766(as)X
X1855(large)X
X2038(key)X
X2176(handling,)X
X720 4076(user)N
X876(de\256ned)X
X1134(hash)X
X1302(functions,)X
X1641(multiple)X
X1928(hash)X
X2096(tables,)X
X2324(vari-)X
X720 4164(able)N
X894(sized)X
X1099(pages,)X
X1342(and)X
X1498(linear)X
X1721(hashing.)X
X2050(In)X
X2156(nearly)X
X2396(all)X
X720 4252(cases,)N
X954(the)X
X1096(new)X
X1274(package)X
X1582(provides)X
X1902(improved)X
X2252(perfor-)X
X720 4340(mance)N
X974(on)X
X1098(the)X
X1240(order)X
X1454(of)X
X1565(50-80%)X
X1863(for)X
X2001(the)X
X2142(workloads)X
X720 4428(shown.)N
X990(Applications)X
X1420(such)X
X1588(as)X
X1676(the)X
X1794(loader,)X
X2035(compiler,)X
X2360(and)X
X720 4516(mail,)N
X921(which)X
X1156(currently)X
X1485(implement)X
X1866(their)X
X2051(own)X
X2227(hashing)X
X720 4604(routines,)N
X1032(should)X
X1279(be)X
X1389(modi\256ed)X
X1706(to)X
X1801(use)X
X1941(the)X
X2072(generic)X
X2342(rou-)X
X720 4692(tines.)N
X892 4806(This)N
X1087(hashing)X
X1389(package)X
X1705(is)X
X1810(one)X
X1978(access)X
X2236(method)X
X720 4894(which)N
X953(is)X
X1043(part)X
X1205(of)X
X1309(a)X
X1382(generic)X
X1656(database)X
X1970(access)X
X2212(package)X
X720 4982(being)N
X955(developed)X
X1342(at)X
X1457(the)X
X1612(University)X
X2007(of)X
X2131(California,)X
X720 5070(Berkeley.)N
X1089(It)X
X1177(will)X
X1340(include)X
X1614(a)X
X1688(btree)X
X1887(access)X
X2131(method)X
X2409(as)X
X720 5158(well)N
X916(as)X
X1041(\256xed)X
X1259(and)X
X1433(variable)X
X1750(length)X
X2007(record)X
X2270(access)X
X720 5246(methods)N
X1024(in)X
X1119(addition)X
X1414(to)X
X1509(the)X
X1640(hashed)X
X1896(support)X
X2168(presented)X
X720 5334(here.)N
X948(All)X
X1099(of)X
X1215(the)X
X1361(access)X
X1615(methods)X
X1934(are)X
X2081(based)X
X2312(on)X
X2440(a)X
X720 5422(key/data)N
X1037(pair)X
X1207(interface)X
X1533(and)X
X1693(appear)X
X1952(identical)X
X2272(to)X
X2378(the)X
X720 5510(application)N
X1121(layer,)X
X1347(allowing)X
X1671(application)X
X2071(implementa-)X
X720 5598(tions)N
X906(to)X
X999(be)X
X1106(largely)X
X1360(independent)X
X1783(of)X
X1881(the)X
X2010(database)X
X2318(type.)X
X720 5686(The)N
X873(package)X
X1165(is)X
X1246(expected)X
X1560(to)X
X1650(be)X
X1754(an)X
X1858(integral)X
X2131(part)X
X2284(of)X
X2378(the)X
X2706 538(4.4BSD)N
X3006(system,)X
X3293(with)X
X3479(various)X
X3759(standard)X
X4075(applications)X
X2706 626(such)N
X2879(as)X
X2972(more\(1\),)X
X3277(sort\(1\))X
X3517(and)X
X3659(vi\(1\))X
X3841(based)X
X4050(on)X
X4156(it.)X
X4266(While)X
X2706 714(the)N
X2833(current)X
X3089(design)X
X3326(does)X
X3501(not)X
X3631(support)X
X3899(multi-user)X
X4256(access)X
X2706 802(or)N
X2804(transactions,)X
X3238(they)X
X3407(could)X
X3616(be)X
X3723(incorporated)X
X4159(relatively)X
X2706 890(easily.)N
X10 f
X2894 938(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2 f
X3365 1030(hash)N
X3638(ndbm)X
X3936(%change)X
X1 f
X10 f
X2894 1034(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X2934 1126(CREATE)N
X10 f
X2894 1130(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X3111 1222(user)N
X3390(0.2)X
X3677(0.4)X
X4079(50)X
X3143 1310(sys)N
X3390(0.1)X
X3677(1.0)X
X4079(90)X
X3 f
X2992 1398(elapsed)N
X10 f
X3296 1406(c)N
X1374(c)Y
X1294(c)Y
X1214(c)Y
X3 f
X3390 1398(0)N
X10 f
X3567 1406(c)N
X1374(c)Y
X1294(c)Y
X1214(c)Y
X3 f
X3677 1398(3.2)N
X10 f
X3869 1406(c)N
X1374(c)Y
X1294(c)Y
X1214(c)Y
X3 f
X4039 1398(100)N
X1 f
X10 f
X2894 1394(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2894 1410(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X2934 1494(READ)N
X10 f
X2894 1498(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X3111 1590(user)N
X3390(0.1)X
X3677(0.1)X
X4119(0)X
X3143 1678(sys)N
X3390(0.1)X
X3677(0.4)X
X4079(75)X
X3 f
X2992 1766(elapsed)N
X10 f
X3296 1774(c)N
X1742(c)Y
X1662(c)Y
X1582(c)Y
X3 f
X3390 1766(0.0)N
X10 f
X3567 1774(c)N
X1742(c)Y
X1662(c)Y
X1582(c)Y
X3 f
X3677 1766(0.0)N
X10 f
X3869 1774(c)N
X1742(c)Y
X1662(c)Y
X1582(c)Y
X3 f
X4119 1766(0)N
X1 f
X10 f
X2894 1762(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2894 1778(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X2934 1862(VERIFY)N
X10 f
X2894 1866(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X3111 1958(user)N
X3390(0.1)X
X3677(0.2)X
X4079(50)X
X3143 2046(sys)N
X3390(0.1)X
X3677(0.3)X
X4079(67)X
X3 f
X2992 2134(elapsed)N
X10 f
X3296 2142(c)N
X2110(c)Y
X2030(c)Y
X1950(c)Y
X3 f
X3390 2134(0.0)N
X10 f
X3567 2142(c)N
X2110(c)Y
X2030(c)Y
X1950(c)Y
X3 f
X3677 2134(0.0)N
X10 f
X3869 2142(c)N
X2110(c)Y
X2030(c)Y
X1950(c)Y
X3 f
X4119 2134(0)N
X1 f
X10 f
X2894 2130(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2894 2146(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X2934 2230(SEQUENTIAL)N
X10 f
X2894 2234(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X3111 2326(user)N
X3390(0.1)X
X3677(0.0)X
X4012(-100)X
X3143 2414(sys)N
X3390(0.1)X
X3677(0.1)X
X4119(0)X
X3 f
X2992 2502(elapsed)N
X10 f
X3296 2510(c)N
X2478(c)Y
X2398(c)Y
X2318(c)Y
X3 f
X3390 2502(0.0)N
X10 f
X3567 2510(c)N
X2478(c)Y
X2398(c)Y
X2318(c)Y
X3 f
X3677 2502(0.0)N
X10 f
X3869 2510(c)N
X2478(c)Y
X2398(c)Y
X2318(c)Y
X3 f
X4119 2502(0)N
X1 f
X10 f
X2894 2498(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2894 2514(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X2934 2598(SEQUENTIAL)N
X3453(\(with)X
X3642(data)X
X3796(retrieval\))X
X10 f
X2894 2602(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X3111 2694(user)N
X3390(0.1)X
X3677(0.1)X
X4119(0)X
X3143 2782(sys)N
X3390(0.1)X
X3677(0.1)X
X4119(0)X
X3 f
X2992 2870(elapsed)N
X3390(0.0)X
X3677(0.0)X
X4119(0)X
X1 f
X10 f
X2894 2874(i)N
X2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2885 2878(c)N
X2862(c)Y
X2782(c)Y
X2702(c)Y
X2622(c)Y
X2542(c)Y
X2462(c)Y
X2382(c)Y
X2302(c)Y
X2222(c)Y
X2142(c)Y
X2062(c)Y
X1982(c)Y
X1902(c)Y
X1822(c)Y
X1742(c)Y
X1662(c)Y
X1582(c)Y
X1502(c)Y
X1422(c)Y
X1342(c)Y
X1262(c)Y
X1182(c)Y
X1102(c)Y
X1022(c)Y
X3296 2878(c)N
X2846(c)Y
X2766(c)Y
X2686(c)Y
X3567 2878(c)N
X2846(c)Y
X2766(c)Y
X2686(c)Y
X3869 2878(c)N
X2846(c)Y
X2766(c)Y
X2686(c)Y
X4264 2878(c)N
X2862(c)Y
X2782(c)Y
X2702(c)Y
X2622(c)Y
X2542(c)Y
X2462(c)Y
X2382(c)Y
X2302(c)Y
X2222(c)Y
X2142(c)Y
X2062(c)Y
X1982(c)Y
X1902(c)Y
X1822(c)Y
X1742(c)Y
X1662(c)Y
X1582(c)Y
X1502(c)Y
X1422(c)Y
X1342(c)Y
X1262(c)Y
X1182(c)Y
X1102(c)Y
X1022(c)Y
X2891 3058(i)N
X2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2 f
X3304 3150(hash)N
X3571(hsearch)X
X3939(%change)X
X1 f
X10 f
X2891 3154(i)N
X2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X2931 3246(CREATE/READ)N
X10 f
X2891 3250(i)N
X2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X1 f
X3050 3342(user)N
X3329(0.3)X
X3648(0.4)X
X4048(25)X
X3082 3430(sys)N
X3329(0.0)X
X3648(0.0)X
X4088(0)X
X3 f
X2931 3518(elapsed)N
X3329(0.0)X
X3648(0.0)X
X4088(0)X
X1 f
X10 f
X2891 3522(i)N
X2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
X2882 3534(c)N
X3462(c)Y
X3382(c)Y
X3302(c)Y
X3222(c)Y
X3142(c)Y
X3235 3518(c)N
X3494(c)Y
X3414(c)Y
X3334(c)Y
X3506 3518(c)N
X3494(c)Y
X3414(c)Y
X3334(c)Y
X3872 3518(c)N
X3494(c)Y
X3414(c)Y
X3334(c)Y
X4267 3534(c)N
X3462(c)Y
X3382(c)Y
X3302(c)Y
X3222(c)Y
X3142(c)Y
X3 f
X2706 3658(Figure)N
X2953(8b:)X
X1 f
X3084(Timing)X
X3339(results)X
X3568(for)X
X3682(the)X
X3800(password)X
X4123(database.)X
X10 f
X2706 3746 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X3 f
X3396 3988(References)N
X1 f
X2706 4120([ATT79])N
X3058(AT&T,)X
X3358(DBM\(3X\),)X
X2 f
X3773(Unix)X
X3990(Programmer's)X
X2878 4208(Manual,)N
X3194(Seventh)X
X3491(Edition,)X
X3793(Volume)X
X4085(1)X
X1 f
X(,)S
X4192(January,)X
X2878 4296(1979.)N
X2706 4472([ATT85])N
X3027(AT&T,)X
X3296(HSEARCH\(BA_LIB\),)X
X2 f
X4053(Unix)X
X4239(System)X
X2878 4560(User's)N
X3112(Manual,)X
X3401(System)X
X3644(V.3)X
X1 f
X3753(,)X
X3793(pp.)X
X3913(506-508,)X
X4220(1985.)X
X2706 4736([BRE73])N
X3025(Brent,)X
X3253(Richard)X
X3537(P.,)X
X3651(``Reducing)X
X4041(the)X
X4168(Retrieval)X
X2878 4824(Time)N
X3071(of)X
X3162(Scatter)X
X3409(Storage)X
X3678(Techniques'',)X
X2 f
X4146(Commun-)X
X2878 4912(ications)N
X3175(of)X
X3281(the)X
X3422(ACM)X
X1 f
X3591(,)X
X3654(Volume)X
X3955(16,)X
X4098(No.)X
X4259(2,)X
X4362(pp.)X
X2878 5000(105-109,)N
X3185(February,)X
X3515(1973.)X
X2706 5176([BSD86])N
X3055(NDBM\(3\),)X
X2 f
X3469(4.3BSD)X
X3775(Unix)X
X3990(Programmer's)X
X2878 5264(Manual)N
X3155(Reference)X
X3505(Guide)X
X1 f
X3701(,)X
X3749(University)X
X4114(of)X
X4208(Califor-)X
X2878 5352(nia,)N
X3016(Berkeley,)X
X3346(1986.)X
X2706 5528([ENB88])N
X3025(Enbody,)X
X3319(R.)X
X3417(J.,)X
X3533(Du,)X
X3676(H.)X
X3779(C.,)X
X3897(``Dynamic)X
X4270(Hash-)X
X2878 5616(ing)N
X3034(Schemes'',)X
X2 f
X3427(ACM)X
X3630(Computing)X
X4019(Surveys)X
X1 f
X4269(,)X
X4322(Vol.)X
X2878 5704(20,)N
X2998(No.)X
X3136(2,)X
X3216(pp.)X
X3336(85-113,)X
X3603(June)X
X3770(1988.)X
X3 f
X720 5960(USENIX)N
X9 f
X1042(-)X
X3 f
X1106(Winter)X
X1371('91)X
X9 f
X1498(-)X
X3 f
X1562(Dallas,)X
X1815(TX)X
X4384(11)X
X
X12 p
X%%Page: 12 12
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X432 258(A)N
X510(New)X
X682(Hashing)X
X985(Package)X
X1290(for)X
X1413(UNIX)X
X3663(Seltzer)X
X3920(&)X
X4007(Yigit)X
X1 f
X432 538([FAG79])N
X776(Ronald)X
X1057(Fagin,)X
X1308(Jurg)X
X1495(Nievergelt,)X
X1903(Nicholas)X
X604 626(Pippenger,)N
X1003(H.)X
X1135(Raymond)X
X1500(Strong,)X
X1787(``Extendible)X
X604 714(Hashing)N
X901(--)X
X985(A)X
X1073(Fast)X
X1236(Access)X
X1493(Method)X
X1771(for)X
X1894(Dynamic)X
X604 802(Files'',)N
X2 f
X855(ACM)X
X1046(Transactions)X
X1485(on)X
X1586(Database)X
X1914(Systems)X
X1 f
X2168(,)X
X604 890(Volume)N
X882(4,)X
X962(No.)X
X1100(3.,)X
X1200(September)X
X1563(1979,)X
X1763(pp)X
X1863(315-34)X
X432 1066([KNU68],)N
X802(Knuth,)X
X1064(D.E.,)X
X2 f
X1273(The)X
X1434(Art)X
X1577(of)X
X1680(Computer)X
X2041(Pro-)X
X604 1154(gramming)N
X971(Vol.)X
X1140(3:)X
X1245(Sorting)X
X1518(and)X
X1676(Searching)X
X1 f
X2001(,)X
X2058(sec-)X
X604 1242(tions)N
X779(6.3-6.4,)X
X1046(pp)X
X1146(481-550.)X
X432 1418([LAR78])N
X747(Larson,)X
X1011(Per-Ake,)X
X1319(``Dynamic)X
X1687(Hashing'',)X
X2 f
X2048(BIT)X
X1 f
X(,)S
X604 1506(Vol.)N
X764(18,)X
X884(1978,)X
X1084(pp.)X
X1204(184-201.)X
X432 1682([LAR88])N
X752(Larson,)X
X1021(Per-Ake,)X
X1335(``Dynamic)X
X1709(Hash)X
X1900(Tables'',)X
X2 f
X604 1770(Communications)N
X1183(of)X
X1281(the)X
X1415(ACM)X
X1 f
X1584(,)X
X1640(Volume)X
X1934(31,)X
X2070(No.)X
X604 1858(4.,)N
X704(April)X
X893(1988,)X
X1093(pp)X
X1193(446-457.)X
X432 2034([LIT80])N
X731(Witold,)X
X1013(Litwin,)X
X1286(``Linear)X
X1590(Hashing:)X
X1939(A)X
X2036(New)X
X604 2122(Tool)N
X786(for)X
X911(File)X
X1065(and)X
X1211(Table)X
X1424(Addressing'',)X
X2 f
X1893(Proceed-)X
X604 2210(ings)N
X761(of)X
X847(the)X
X969(6th)X
X1095(International)X
X1540(Conference)X
X1933(on)X
X2036(Very)X
X604 2298(Large)N
X815(Databases)X
X1 f
X1153(,)X
X1193(1980.)X
X432 2474([NEL90])N
X743(Nelson,)X
X1011(Philip)X
X1222(A.,)X
X2 f
X1341(Gdbm)X
X1558(1.4)X
X1679(source)X
X1913(distribu-)X
X604 2562(tion)N
X748(and)X
X888(README)X
X1 f
X1209(,)X
X1249(August)X
X1500(1990.)X
X432 2738([THOM90])N
X840(Ken)X
X1011(Thompson,)X
X1410(private)X
X1670(communication,)X
X604 2826(Nov.)N
X782(1990.)X
X432 3002([TOR87])N
X790(Torek,)X
X1066(C.,)X
X1222(``Re:)X
X1470(dbm.a)X
X1751(and)X
X1950(ndbm.a)X
X604 3090(archives'',)N
X2 f
X966(USENET)X
X1279(newsgroup)X
X1650(comp.unix)X
X1 f
X2002(1987.)X
X432 3266([TOR88])N
X760(Torek,)X
X1006(C.,)X
X1133(``Re:)X
X1351(questions)X
X1686(regarding)X
X2027(data-)X
X604 3354(bases)N
X826(created)X
X1106(with)X
X1295(dbm)X
X1484(and)X
X1647(ndbm)X
X1876(routines'')X
X2 f
X604 3442(USENET)N
X937(newsgroup)X
X1328(comp.unix.questions)X
X1 f
X1982(,)X
X2041(June)X
X604 3530(1988.)N
X432 3706([WAL84])N
X773(Wales,)X
X1018(R.,)X
X1135(``Discussion)X
X1564(of)X
X1655("dbm")X
X1887(data)X
X2045(base)X
X604 3794(system'',)N
X2 f
X973(USENET)X
X1339(newsgroup)X
X1762(unix.wizards)X
X1 f
X2168(,)X
X604 3882(January,)N
X894(1984.)X
X432 4058([YIG89])N
X751(Ozan)X
X963(S.)X
X1069(Yigit,)X
X1294(``How)X
X1545(to)X
X1648(Roll)X
X1826(Your)X
X2032(Own)X
X604 4146(Dbm/Ndbm'',)N
X2 f
X1087(unpublished)X
X1504(manuscript)X
X1 f
X(,)S
X1910(Toronto,)X
X604 4234(July,)N
X777(1989)X
X3 f
X432 5960(12)N
X2970(USENIX)X
X9 f
X3292(-)X
X3 f
X3356(Winter)X
X3621('91)X
X9 f
X3748(-)X
X3 f
X3812(Dallas,)X
X4065(TX)X
X
X13 p
X%%Page: 13 13
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X720 258(Seltzer)N
X977(&)X
X1064(Yigit)X
X3278(A)X
X3356(New)X
X3528(Hashing)X
X3831(Package)X
X4136(for)X
X4259(UNIX)X
X1 f
X720 538(Margo)N
X960(I.)X
X1033(Seltzer)X
X1282(is)X
X1361(a)X
X1423(Ph.D.)X
X1631(student)X
X1887(in)X
X1974(the)X
X2097(Department)X
X720 626(of)N
X823(Electrical)X
X1167(Engineering)X
X1595(and)X
X1747(Computer)X
X2102(Sciences)X
X2418(at)X
X720 714(the)N
X850(University)X
X1220(of)X
X1318(California,)X
X1694(Berkeley.)X
X2055(Her)X
X2207(research)X
X720 802(interests)N
X1017(include)X
X1283(\256le)X
X1415(systems,)X
X1718(databases,)X
X2076(and)X
X2221(transac-)X
X720 890(tion)N
X896(processing)X
X1291(systems.)X
X1636(She)X
X1807(spent)X
X2027(several)X
X2306(years)X
X720 978(working)N
X1026(at)X
X1123(startup)X
X1380(companies)X
X1762(designing)X
X2112(and)X
X2267(imple-)X
X720 1066(menting)N
X1048(\256le)X
X1216(systems)X
X1535(and)X
X1716(transaction)X
X2133(processing)X
X720 1154(software)N
X1026(and)X
X1170(designing)X
X1509(microprocessors.)X
X2103(Ms.)X
X2253(Seltzer)X
X720 1242(received)N
X1057(her)X
X1223(AB)X
X1397(in)X
X1522(Applied)X
X1843(Mathematics)X
X2320(from)X
X720 1330 0.1953(Harvard/Radcliffe)AN
X1325(College)X
X1594(in)X
X1676(1983.)X
X720 1444(In)N
X810(her)X
X936(spare)X
X1129(time,)X
X1313(Margo)X
X1549(can)X
X1683(usually)X
X1936(be)X
X2034(found)X
X2243(prepar-)X
X720 1532(ing)N
X868(massive)X
X1171(quantities)X
X1527(of)X
X1639(food)X
X1831(for)X
X1970(hungry)X
X2242(hoards,)X
X720 1620(studying)N
X1022(Japanese,)X
X1355(or)X
X1449(playing)X
X1716(soccer)X
X1948(with)X
X2116(an)X
X2218(exciting)X
X720 1708(Bay)N
X912(Area)X
X1132(Women's)X
X1507(Soccer)X
X1788(team,)X
X2026(the)X
X2186(Berkeley)X
X720 1796(Bruisers.)N
X720 1910(Ozan)N
X915(\()X
X3 f
X942(Oz)X
X1 f
X1040(\))X
X1092(Yigit)X
X1281(is)X
X1358(currently)X
X1672(a)X
X1732(software)X
X2033(engineer)X
X2334(with)X
X720 1998(the)N
X886(Communications)X
X1499(Research)X
X1861(and)X
X2044(Development)X
X720 2086(group,)N
X948(Computing)X
X1328(Services,)X
X1641(York)X
X1826(University.)X
X2224(His)X
X2355(for-)X
X720 2174(mative)N
X967(years)X
X1166(were)X
X1352(also)X
X1510(spent)X
X1708(at)X
X1795(York,)X
X2009(where)X
X2234(he)X
X2338(held)X
X720 2262(system)N
X985(programmer)X
X1425(and)X
X1583(administrator)X
X2052(positions)X
X2382(for)X
X720 2350(various)N
X995(mixtures)X
X1314(of)X
X1420(of)X
X1526(UNIX)X
X1765(systems)X
X2056(starting)X
X2334(with)X
X720 2438(Berkeley)N
X1031(4.1)X
X1151(in)X
X1233(1982,)X
X1433(while)X
X1631(at)X
X1709(the)X
X1827(same)X
X2012(time)X
X2174(obtaining)X
X720 2526(a)N
X776(degree)X
X1011(in)X
X1093(Computer)X
X1433(Science.)X
X720 2640(In)N
X813(his)X
X931(copious)X
X1205(free)X
X1356(time,)X
X1543(Oz)X
X1662(enjoys)X
X1896(working)X
X2188(on)X
X2293(what-)X
X720 2728(ever)N
X890(software)X
X1197(looks)X
X1400(interesting,)X
X1788(which)X
X2014(often)X
X2209(includes)X
X720 2816(language)N
X1044(interpreters,)X
X1464(preprocessors,)X
X1960(and)X
X2110(lately,)X
X2342(pro-)X
X720 2904(gram)N
X905(generators)X
X1260(and)X
X1396(expert)X
X1617(systems.)X
X720 3018(Oz)N
X836(has)X
X964(authored)X
X1266(several)X
X1515(public-domain)X
X2003(software)X
X2301(tools,)X
X720 3106(including)N
X1069(an)X
X1191(nroff-like)X
X1545(text)X
X1711(formatter)X
X2 f
X2056(proff)X
X1 f
X2257(that)X
X2423(is)X
X720 3194(apparently)N
X1083(still)X
X1226(used)X
X1397(in)X
X1483(some)X
X1676(basement)X
X2002(PCs.)X
X2173(His)X
X2307(latest)X
X720 3282(obsessions)N
X1143(include)X
X1460(the)X
X1639(incredible)X
X2040(programming)X
X720 3370(language)N
X1030(Scheme,)X
X1324(and)X
X1460(Chinese)X
X1738(Brush)X
X1949(painting.)X
X3 f
X720 5960(USENIX)N
X9 f
X1042(-)X
X3 f
X1106(Winter)X
X1371('91)X
X9 f
X1498(-)X
X3 f
X1562(Dallas,)X
X1815(TX)X
X4384(13)X
X
X14 p
X%%Page: 14 14
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X432 5960(14)N
X2970(USENIX)X
X9 f
X3292(-)X
X3 f
X3356(Winter)X
X3621('91)X
X9 f
X3748(-)X
X3 f
X3812(Dallas,)X
X4065(TX)X
X
X14 p
X%%Trailer
Xxt
X
Xxs
END_OF_FILE
if test 74476 -ne `wc -c <'doc/hash.ps.02'`; then
    echo shar: \"'doc/hash.ps.02'\" unpacked with wrong size!
fi
# end of 'doc/hash.ps.02'
fi
echo shar: End of archive 8 \(of 9\).
cp /dev/null ark8isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 9 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 9 archives.
    rm -f ark[1-9]isdone ark[1-9][0-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0