Hash table

해시 테이블

Hash keys into buckets and keep colliding keys together.

···
html
<div class="v"><header><b>HASH TABLE</b><span id="state"></span></header><main><div class="keys" id="keys"></div><div class="arrow">↓ hash(key) ↓</div><div class="buckets" id="buckets"></div></main><footer>collision in bucket 0</footer></div>
css
.v{width:min(92vw,660px);height:min(86vh,310px);box-sizing:border-box;padding:clamp(9px,2.5vmin,18px);border:1px solid var(--line);border-radius:14px;background:var(--surface);display:flex;flex-direction:column;gap:7px;color:var(--fg);font:500 clamp(15px,4.5vmin,19px)/1.25 var(--font-sans, sans-serif)}.v header,.v footer{display:flex;justify-content:space-between;align-items:center;gap:8px;white-space:nowrap}.v header b{color:var(--accent);font-size:.9em}.v header span,.v footer{color:var(--muted);font-size:.82em}.v main{flex:1;min-height:0;position:relative;overflow:hidden}.v .mono{font-family:ui-monospace,SFMono-Regular,Consolas,monospace}.v .active{background:var(--accent)!important;color:var(--bg)!important;border-color:var(--accent)!important}.v .muted{opacity:.45} .keys,.buckets{display:flex;justify-content:center;gap:4px}.keys{height:27%;align-items:center}.keys b{padding:5px 8px;border:1px solid var(--line);border-radius:6px}.arrow{text-align:center;color:var(--accent);height:25%}.buckets{height:45%;align-items:stretch}.bucket{width:22%;border:1px solid var(--line);border-radius:6px;text-align:center;padding:5px 2px;font:600 .85em ui-monospace,monospace}.bucket span{display:block;color:var(--accent)}
js
const keys=["A","B","C","D"];let n=0;function draw(){document.getElementById("keys").innerHTML=keys.map((k,i)=>"<b class=\""+(i===n?"active":"")+"\">"+k+"</b>").join("");document.getElementById("buckets").innerHTML=[0,1,2].map(i=>"<div class=bucket>"+i+"<span>"+keys.slice(0,n+1).filter((_,j)=>j%3===i).join(" → ")+"</span></div>").join("");document.getElementById("state").textContent=keys[n]+" → "+n%3;n=(n+1)%4}draw();setInterval(draw,900)

A hash table runs a key through a hash function to choose an array position. This direct address makes average lookups and inserts fast.

Distinct keys can collide at the same position. The demo chains items in a bucket; another design can probe for an empty slot.

When to use

Use it for dictionaries, caches, and indexes keyed by an identifier.

Open as page ↗