171 lines
6.9 KiB
XML
171 lines
6.9 KiB
XML
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
|
|
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
|
|
<!-- Created on 2009-04-10 by Jorge Stolfi with the script make-hash-table-figure -->
|
|
|
|
<svg
|
|
xmlns="http://www.w3.org/2000/svg"
|
|
xmlns:xlink="http://www.w3.org/1999/xlink"
|
|
width="315.0"
|
|
height="230.0"
|
|
id="fig"
|
|
stroke-linejoin="round"
|
|
stroke-opacity="1"
|
|
stroke-linecap="round"
|
|
fill-opacity="1"
|
|
fill-rule="evenodd"
|
|
font-family="Bitstream Courier"
|
|
font-style="normal"
|
|
font-weight="normal"
|
|
pagecolor="#ffff00"
|
|
pageopacity="0.0">
|
|
|
|
|
|
<g
|
|
font-size="12px"
|
|
transform="scale(1.0) translate(10,60)"
|
|
>
|
|
|
|
<defs>
|
|
<!-- Start marker for non-null pointers: -->
|
|
<marker id="linkdot_N" viewBox="0 0 8 8" refX="4" refY="4" markerWidth="8" markerHeight="8" orient="auto">
|
|
<circle cx="4" cy="4" r="3" stroke="#000000" fill="#000000" />
|
|
</marker>
|
|
<!-- Start marker for null pointers: -->
|
|
<marker id="linkdot_U" viewBox="0 0 8 8" refX="4" refY="4" markerWidth="8" markerHeight="8" orient="auto">
|
|
<line x1="1" y1="1" x2="7" y2="7" stroke="#000000" />
|
|
<line x1="1" y1="7" x2="7" y2="1" stroke="#000000" />
|
|
</marker>
|
|
|
|
<!-- Tip for arrows: -->
|
|
<marker id="arrowtip_N" viewBox="0 0 14 8" refX="13" refY="4" markerWidth="14" markerHeight="8" orient="auto">
|
|
<polygon points="1,4 1,1 13,4 1,7" stroke="#000000" fill="#000000" />
|
|
</marker>
|
|
<!-- Tip for highlighted arrows: -->
|
|
<marker id="arrowtip_C" viewBox="0 0 14 8" refX="13" refY="4" markerWidth="14" markerHeight="8" orient="auto">
|
|
<polygon points="1,4 1,1 13,4 1,7" stroke="#cc0000" fill="#cc0000" />
|
|
</marker>
|
|
|
|
<!-- Key box in input column, normal: -->
|
|
<rect id="key_box_N" y="0" x="0" width="90" height="20" fill="#00ffff" stroke="none" />
|
|
<!-- Key box in input column, highlighted : -->
|
|
<rect id="key_box_C" y="0" x="0" width="90" height="20" fill="#00ffff" stroke="none" />
|
|
<!-- Key box in bucket or overflow columns, normal: -->
|
|
<rect id="key_box_E" y="0" x="0" width="90" height="20" fill="#9cff9c" stroke="#000000" />
|
|
<!-- Key box in bucket or overflow columns, vacant: -->
|
|
<rect id="key_box_U" y="0" x="0" width="90" height="20" fill="#ddeedd" stroke="#000000" />
|
|
|
|
<!-- Value box in bucket or overflow columns, occupied: -->
|
|
<rect id="val_box_E" y="0" x="0" width="80" height="20" fill="#9cff9c" stroke="#000000" />
|
|
<!-- Value box in bucket or overflow columns, vacant: -->
|
|
<rect id="val_box_U" y="0" x="0" width="80" height="20" fill="#ddeedd" stroke="#000000" />
|
|
|
|
<!-- Pointer box in bucket or overflow columns, used and non-null: -->
|
|
<rect id="ptr_box_E" y="0" x="0" width="20" height="20" fill="#9cff9c" stroke="#000000" />
|
|
<!-- Pointer box in bucket or overflow columns, null/vacant: -->
|
|
<rect id="ptr_box_U" y="0" x="0" width="20" height="20" fill="#ddeedd" stroke="#000000" />
|
|
|
|
<!-- Background for hash value, unused: -->
|
|
<rect id="hsh_box_U" x="3" y="1" width="24" height="18" fill="#ddeedd" stroke="none" />
|
|
<!-- Background for hash value, used: -->
|
|
<rect id="hsh_box_N" x="3" y="1" width="24" height="18" fill="#a8a8ff" stroke="none" />
|
|
<!-- Background for hash value, highlighted: -->
|
|
<rect id="hsh_box_C" x="3" y="1" width="24" height="18" fill="#ee4444" stroke="none" />
|
|
|
|
<!-- Vertical dots: -->
|
|
<g id="vdots">
|
|
<rect x="0" y="06" width="2" height="2" />
|
|
<rect x="0" y="12" width="2" height="2" />
|
|
</g>
|
|
</defs>
|
|
|
|
<!-- Keys and hash function -->
|
|
<g transform="translate(0,000)" text-anchor="middle" stroke="none">
|
|
|
|
<text x="130" y="-30" font-size="15px" font-weight="bold" fill="#000000" stroke="none"> hash </text>
|
|
<text x="130" y="-10" font-size="15px" font-weight="bold" fill="#000000" stroke="none"> function </text>
|
|
|
|
<rect x="100" y="0" width="60" height="160" fill="#aaeecc" stroke="none" />
|
|
|
|
<text x="45" y="-10" font-size="15px" font-weight="bold" fill="#000000" stroke="none"> keys
|
|
</text>
|
|
|
|
<g transform="translate(0,30)">
|
|
<use xlink:href="#key_box_N" />
|
|
<text x="45" y="14" stroke="none">John Smith</text>
|
|
<line x1="95" y1="10" x2="105" y2="10" stroke="#000000" />
|
|
<line x1="105" y1="10" x2="155" y2="20" stroke="#000000" />
|
|
<line x1="155" y1="20" x2="180" y2="20" stroke="#000000" marker-end="url(#arrowtip_N)" />
|
|
</g>
|
|
<g transform="translate(0,70)">
|
|
<use xlink:href="#key_box_N" />
|
|
<text x="45" y="14" stroke="none">Lisa Smith</text>
|
|
<line x1="95" y1="10" x2="105" y2="10" stroke="#000000" />
|
|
<line x1="105" y1="10" x2="155" y2="-40" stroke="#000000" />
|
|
<line x1="155" y1="-40" x2="180" y2="-40" stroke="#000000" marker-end="url(#arrowtip_N)" />
|
|
</g>
|
|
<g transform="translate(0,110)">
|
|
<use xlink:href="#key_box_N" />
|
|
<text x="45" y="14" stroke="none">Sandra Dee</text>
|
|
<line x1="95" y1="10" x2="105" y2="10" stroke="#000000" />
|
|
<line x1="105" y1="10" x2="155" y2="20" stroke="#000000" />
|
|
<line x1="155" y1="20" x2="180" y2="20" stroke="#000000" marker-end="url(#arrowtip_N)" />
|
|
</g>
|
|
|
|
</g>
|
|
|
|
<!-- Hash values and bucket array -->
|
|
<g transform="translate(180,000)" text-anchor="middle" stroke="none">
|
|
|
|
<text x="70" y="-10" font-size="15px" font-weight="bold" fill="#000000" stroke="none">
|
|
buckets
|
|
</text>
|
|
|
|
<g transform="translate(000,0)">
|
|
<use x="0" xlink:href="#hsh_box_U" />
|
|
<text x="15" y="14">00</text>
|
|
<use x="30" xlink:href="#val_box_U" />
|
|
</g>
|
|
<g transform="translate(000,20)">
|
|
<use x="0" xlink:href="#hsh_box_N" />
|
|
<text x="15" y="14">01</text>
|
|
<use x="30" xlink:href="#val_box_E" />
|
|
<text x="70" y="14">521-8976</text>
|
|
</g>
|
|
<g transform="translate(000,40)">
|
|
<use x="0" xlink:href="#hsh_box_N" />
|
|
<text x="15" y="14">02</text>
|
|
<use x="30" xlink:href="#val_box_E" />
|
|
<text x="70" y="14">521-1234</text>
|
|
</g>
|
|
<g transform="translate(000,60)">
|
|
<use x="0" xlink:href="#hsh_box_U" />
|
|
<text x="15" y="14">03</text>
|
|
<use x="30" xlink:href="#val_box_U" />
|
|
</g>
|
|
<g transform="translate(000,80)">
|
|
<text x="15" y="14" font-weight="bold">:</text>
|
|
<text x="70" y="14" font-weight="bold">:</text>
|
|
</g>
|
|
<g transform="translate(000,100)">
|
|
<use x="0" xlink:href="#hsh_box_U" />
|
|
<text x="15" y="14">13</text>
|
|
<use x="30" xlink:href="#val_box_U" />
|
|
</g>
|
|
<g transform="translate(000,120)">
|
|
<use x="0" xlink:href="#hsh_box_N" />
|
|
<text x="15" y="14">14</text>
|
|
<use x="30" xlink:href="#val_box_E" />
|
|
<text x="70" y="14">521-9655</text>
|
|
</g>
|
|
<g transform="translate(000,140)">
|
|
<use x="0" xlink:href="#hsh_box_U" />
|
|
<text x="15" y="14">15</text>
|
|
<use x="30" xlink:href="#val_box_U" />
|
|
</g>
|
|
|
|
</g>
|
|
|
|
|
|
</g>
|
|
</svg>
|
