📄 hash_usenix.ps
字号:
2706 2568(mance)N2942(equal)X3142(or)X3235(superior)X3524(to)X3612(that)X3758(of)X3851(the)X3975(existing)X4253(imple-)X2706 2656(mentations.)N3152(In)X3274(order)X3498(to)X3614(provide)X3913(a)X4003(compact)X4329(disk)X2706 2744(representation,)N3224(graceful)X3531(table)X3729(growth,)X4018(and)X4176(expected)X2706 2832(constant)N3033(time)X3234(performance,)X3720(we)X3873(selected)X4191(Litwin's)X2706 2920(linear)N2923(hashing)X3206(algorithm)X3551([LAR88,)X3872(LIT80].)X4178(We)X4324(then)X2706 3008(enhanced)N3037(the)X3161(algorithm)X3498(to)X3586(handle)X3826(page)X4004(over\257ows)X4346(and)X2706 3096(large)N2900(key)X3049(handling)X3362(with)X3537(a)X3606(single)X3830(mechanism,)X4248(named)X2706 3184(buddy-in-waiting.)N3 f2975 3338(Existing)N3274(UNIX)X3499(Hashing)X3802(Techniques)X1 f2878 3470(Over)N3076(the)X3210(last)X3357(decade,)X3637(several)X3901(dynamic)X4213(hashing)X2706 3558(schemes)N3000(have)X3174(been)X3348(developed)X3700(for)X3816(the)X3936(UNIX)X4159(timeshar-)X2706 3646(ing)N2856(system,)X3146(starting)X3433(with)X3622(the)X3767(inclusion)X4107(of)X2 f4221(dbm)X1 f4359(,)X4426(a)X2706 3734(minimal)N3008(database)X3321(library)X3571(written)X3834(by)X3950(Ken)X4120(Thompson)X2706 3822([THOM90],)N3141(in)X3248(the)X3391(Seventh)X3694(Edition)X3974(UNIX)X4220(system.)X2706 3910(Since)N2916(then,)X3106(an)X3214(extended)X3536(version)X3804(of)X3903(the)X4032(same)X4228(library,)X2 f2706 3998(ndbm)N1 f2884(,)X2933(and)X3078(a)X3142(public-domain)X3637(clone)X3839(of)X3934(the)X4060(latter,)X2 f4273(sdbm)X1 f4442(,)X2706 4086(have)N2902(been)X3098(developed.)X3491(Another)X3797 0.1645(interface-compatible)AX2706 4174(library)N2 f2950(gdbm)X1 f3128(,)X3178(was)X3333(recently)X3622(made)X3826(available)X4145(as)X4241(part)X4395(of)X2706 4262(the)N2829(Free)X2997(Software)X3312(Foundation's)X3759(\(FSF\))X3970(software)X4271(distri-)X2706 4350(bution.)N2878 4464(All)N3017(of)X3121(these)X3323(implementations)X3893(are)X4029(based)X4248(on)X4364(the)X2706 4552(idea)N2871(of)X2969(revealing)X3299(just)X3445(enough)X3711(bits)X3856(of)X3953(a)X4019(hash)X4196(value)X4400(to)X2706 4640(locate)N2920(a)X2978(page)X3151(in)X3234(a)X3291(single)X3503(access.)X3770(While)X2 f3987(dbm/ndbm)X1 f4346(and)X2 f2706 4728(sdbm)N1 f2908(map)X3079(the)X3210(hash)X3390(value)X3597(directly)X3874(to)X3968(a)X4036(disk)X4201(address,)X2 f2706 4816(gdbm)N1 f2921(uses)X3096(the)X3231(hash)X3414(value)X3624(to)X3722(index)X3936(into)X4096(a)X2 f4168(directory)X1 f2706 4904([ENB88])N3020(containing)X3378(disk)X3531(addresses.)X2878 5018(The)N2 f3033(hsearch)X1 f3317(routines)X3605(in)X3697(System)X3962(V)X4049(are)X4177(designed)X2706 5106(to)N2804(provide)X3085(memory-resident)X3669(hash)X3852(tables.)X4115(Since)X4328(data)X2706 5194(access)N2948(does)X3131(not)X3269(require)X3533(disk)X3702(access,)X3964(simple)X4213(hashing)X2706 5282(schemes)N3010(which)X3238(may)X3408(require)X3667(multiple)X3964(probes)X4209(into)X4364(the)X2706 5370(table)N2889(are)X3015(used.)X3209(A)X3294(more)X3486(interesting)X3851(version)X4114(of)X2 f4208(hsearch)X1 f2706 5458(is)N2784(a)X2845(public)X3070(domain)X3335(library,)X2 f3594(dynahash)X1 f3901(,)X3945(that)X4089(implements)X2706 5546(Larson's)N3036(in-memory)X3440(adaptation)X3822([LAR88])X4164(of)X4279(linear)X2706 5634(hashing)N2975([LIT80].)X3 f720 5960(USENIX)N9 f1042(-)X3 f1106(Winter)X1371('91)X9 f1498(-)X3 f1562(Dallas,)X1815(TX)X1 f4424(1)X2 p%%Page: 2 210 s 10 xH 0 xS 1 f3 f432 258(A)N510(New)X682(Hashing)X985(Package)X1290(for)X1413(UNIX)X3663(Seltzer)X3920(&)X4007(Yigit)X2 f1074 538(dbm)N1 f1232(and)X2 f1368(ndbm)X1 f604 670(The)N2 f760(dbm)X1 f928(and)X2 f1074(ndbm)X1 f1282(library)X1526(implementations)X2089(are)X432 758(based)N667(on)X799(the)X949(same)X1166(algorithm)X1529(by)X1661(Ken)X1846(Thompson)X432 846([THOM90,)N824(TOR88,)X1113(WAL84],)X1452(but)X1582(differ)X1789(in)X1879(their)X2054(pro-)X432 934(grammatic)N801(interfaces.)X1160(The)X1311(latter)X1502(is)X1581(a)X1643(modi\256ed)X1952(version)X432 1022(of)N533(the)X665(former)X918(which)X1148(adds)X1328(support)X1601(for)X1728(multiple)X2027(data-)X432 1110(bases)N634(to)X724(be)X828(open)X1011(concurrently.)X1484(The)X1636(discussion)X1996(of)X2090(the)X432 1198(algorithm)N774(that)X925(follows)X1196(is)X1280(applicable)X1640(to)X1732(both)X2 f1904(dbm)X1 f2072(and)X2 f432 1286(ndbm)N1 f610(.)X604 1400(The)N760(basic)X956(structure)X1268(of)X2 f1366(dbm)X1 f1535(calls)X1712(for)X1836(\256xed-sized)X432 1488(disk)N612(blocks)X868(\(buckets\))X1214(and)X1377(an)X2 f1499(access)X1 f1755(function)X2068(that)X432 1576(maps)N623(a)X681(key)X819(to)X902(a)X959(bucket.)X1234(The)X1380(interface)X1683(routines)X1962(use)X2090(the)X2 f432 1664(access)N1 f673(function)X970(to)X1062(obtain)X1292(the)X1420(appropriate)X1816(bucket)X2060(in)X2152(a)X432 1752(single)N643(disk)X796(access.)X604 1866(Within)N869(the)X2 f1010(access)X1 f1263(function,)X1593(a)X1672(bit-randomizing)X432 1954(hash)N610(function)X2 f8 s877 1929(2)N1 f10 s940 1954(is)N1024(used)X1202(to)X1294(convert)X1565(a)X1631(key)X1777(into)X1931(a)X1997(32-bit)X432 2042(hash)N605(value.)X825(Out)X971(of)X1064(these)X1254(32)X1359(bits,)X1519(only)X1686(as)X1778(many)X1981(bits)X2121(as)X432 2130(necessary)N773(are)X900(used)X1075(to)X1165(determine)X1514(the)X1639(particular)X1974(bucket)X432 2218(on)N533(which)X750(a)X807(key)X944(resides.)X1228(An)X1347(in-memory)X1724(bitmap)X1967(is)X2041(used)X432 2306(to)N533(determine)X893(how)X1070(many)X1287(bits)X1441(are)X1579(required.)X1905(Each)X2104(bit)X432 2394(indicates)N746(whether)X1033(its)X1136(associated)X1494(bucket)X1736(has)X1871(been)X2051(split)X432 2482(yet)N562(\(a)X657(0)X728(indicating)X1079(that)X1230(the)X1359(bucket)X1604(has)X1742(not)X1875(yet)X2004(split\).)X432 2570(The)N590(use)X730(of)X830(the)X961(hash)X1141(function)X1441(and)X1590(the)X1720(bitmap)X1974(is)X2059(best)X432 2658(described)N769(by)X878(stepping)X1177(through)X1454(database)X1759(creation)X2046(with)X432 2746(multiple)N718(invocations)X1107(of)X1194(a)X2 f1250(store)X1 f1430(operation.)X604 2860(Initially,)N906(the)X1033(hash)X1209(table)X1394(contains)X1690(a)X1755(single)X1974(bucket)X432 2948(\(bucket)N711(0\),)X836(the)X972(bit)X1094(map)X1270(contains)X1575(a)X1649(single)X1878(bit)X2000(\(bit)X2148(0)X432 3036(corresponding)N913(to)X997(bucket)X1233(0\),)X1342(and)X1480(0)X1542(bits)X1699(of)X1788(a)X1846(hash)X2014(value)X432 3124(are)N560(examined)X901(to)X992(determine)X1342(where)X1568(a)X1633(key)X1778(is)X1860(placed)X2099(\(in)X432 3212(bucket)N670(0\).)X801(When)X1017(bucket)X1255(0)X1319(is)X1396(full,)X1551(its)X1650(bit)X1758(in)X1844(the)X1966(bitmap)X432 3300(\(bit)N564(0\))X652(is)X726(set,)X856(and)X993(its)X1089(contents)X1377(are)X1497(split)X1655(between)X1943(buckets)X432 3388(0)N499(and)X641(1,)X727(by)X833(considering)X1233(the)X1357(0)X2 f7 s3356(th)Y10 s1 f1480 3388(bit)N1590(\(the)X1741(lowest)X1976(bit)X2086(not)X432 3476(previously)N800(examined\))X1169(of)X1266(the)X1393(hash)X1569(value)X1772(for)X1895(each)X2072(key)X432 3564(within)N668(the)X798(bucket.)X1064(Given)X1292(a)X1359(well-designed)X1840(hash)X2018(func-)X432 3652(tion,)N613(approximately)X1112(half)X1273(of)X1376(the)X1510(keys)X1693(will)X1853(have)X2041(hash)X432 3740(values)N666(with)X837(the)X964(0)X2 f7 s3708(th)Y10 s1 f1090 3740(bit)N1203(set.)X1341(All)X1471(such)X1646(keys)X1821(and)X1965(associ-)X432 3828(ated)N586(data)X740(are)X859(moved)X1097(to)X1179(bucket)X1413(1,)X1493(and)X1629(the)X1747(rest)X1883(remain)X2126(in)X432 3916(bucket)N666(0.)X604 4030(After)N804(this)X949(split,)X1135(the)X1262(\256le)X1393(now)X1560(contains)X1856(two)X2005(buck-)X432 4118(ets,)N562(and)X699(the)X818(bitmap)X1061(contains)X1349(three)X1530(bits:)X1687(the)X1805(0)X2 f7 s4086(th)Y10 s1 f1922 4118(bit)N2026(is)X2099(set)X432 4206(to)N525(indicate)X810(a)X876(bucket)X1120(0)X1190(split)X1357(when)X1561(no)X1671(bits)X1816(of)X1913(the)X2041(hash)X432 4294(value)N648(are)X789(considered,)X1199(and)X1357(two)X1519(more)X1726(unset)X1937(bits)X2094(for)X432 4382(buckets)N706(0)X775(and)X920(1.)X1029(The)X1183(placement)X1542(of)X1638(an)X1742(incoming)X2072(key)X432 4470(now)N604(requires)X897(examination)X1327(of)X1428(the)X1560(0)X2 f7 s4438(th)Y10 s1 f1691 4470(bit)N1809(of)X1910(the)X2041(hash)X432 4558(value,)N667(and)X824(the)X963(key)X1119(is)X1212(placed)X1462(either)X1685(in)X1787(bucket)X2041(0)X2121(or)X432 4646(bucket)N674(1.)X782(If)X864(either)X1075(bucket)X1317(0)X1385(or)X1480(bucket)X1722(1)X1790(\256lls)X1937(up,)X2064(it)X2135(is)X432 4734(split)N598(as)X693(before,)X947(its)X1050(bit)X1162(is)X1243(set)X1360(in)X1450(the)X1576(bitmap,)X1846(and)X1990(a)X2054(new)X432 4822(set)N541(of)X628(unset)X817(bits)X952(are)X1071(added)X1283(to)X1365(the)X1483(bitmap.)X604 4936(Each)N791(time)X959(we)X1079(consider)X1376(a)X1437(new)X1596(bit)X1705(\(bit)X1841(n\),)X1953(we)X2072(add)X432 5024(2)N2 f7 s4992(n)Y9 f509(+)X1 f540(1)X10 s595 5024(bits)N737(to)X826(the)X951(bitmap)X1199(and)X1341(obtain)X1567(2)X2 f7 s4992(n)Y9 f1644(+)X1 f1675(1)X10 s1729 5024(more)N1920(address-)X432 5112(able)N595(buckets)X869(in)X960(the)X1087(\256le.)X1258(As)X1376(a)X1441(result,)X1668(the)X1795(bitmap)X2045(con-)X432 5200(tains)N618(the)X751(previous)X1062(2)X2 f7 s5168(n)Y9 f1139(+)X1 f1170(1)X2 f10 s9 f5200(-)Y1 f1242(1)X1317(bits)X1467(\(1)X2 f9 f1534(+)X1 f1578(2)X2 f9 f(+)S1 f1662(4)X2 f9 f(+)S1 f1746(...)X2 f9 f(+)S1 f1850(2)X2 f7 s5168(n)Y10 s1 f1931 5200(\))N1992(which)X432 5288(trace)N649(the)X807(entire)X2 f1050(split)X1247(history)X1 f1529(of)X1656(the)X1813(addressable)X16 s432 5433 MXY864 0 Dl2 f8 s472 5488(2)N1 f9 s523 5513(This)N670(bit-randomizing)X1153(property)X1416(is)X1482(important)X1780(to)X1854(obtain)X2052(radi-)X432 5593(cally)N599(different)X874(hash)X1033(values)X1244(for)X1355(nearly)X1562(identical)X1836(keys,)X2012(which)X432 5673(in)N506(turn)X640(avoids)X846(clustering)X1148(of)X1226(such)X1376(keys)X1526(in)X1600(a)X1650(single)X1840(bucket.)X10 s2418 538(buckets.)N2590 652(Given)N2809(a)X2868(key)X3007(and)X3146(the)X3267(bitmap)X3512(created)X3768(by)X3871(this)X4009(algo-)X2418 740(rithm,)N⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -