ALGORITHMUS-LESENOTIZ

Hash Table

A hash table maps keys to bucket locations using a hash function. It aims for very fast average lookup, insertion and deletion.

TYPDatenstrukturKATEGORIEData StructuresTIEFEEinsteigerTYPISCHE KOMPLEXITÄTavg O(1), worst O(n)

KURZE INTERVIEWANTWORT

Beginne mit diesem mentalen Modell

A hash table maps keys to bucket locations using a hash function. It aims for very fast average lookup, insertion and deletion.

EINFACHE ERKLÄRUNG

So funktioniert es – ohne unnötigen Jargon

The hash function converts a key into an index-like value.

Different keys may collide, so the implementation needs a collision strategy such as chaining or open addressing.

AUSFÜHRUNG

Lies den Algorithmus als Folge von Entscheidungen

Hash the key.

Map the hash to a bucket.

Resolve collisions and compare actual keys.

Ein kleines Beispiel als Orientierung

A user id can be hashed to a bucket; the bucket then stores or finds the actual user entry.

LESBARE JAVASCRIPT-IMPLEMENTIERUNGJavaScript

class HashTable {
  constructor(size = 16) {
    this.buckets = Array.from({ length: size }, () => []);
  }
  hash(key) {
    let h = 0;
    for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
    return h % this.buckets.length;
  }
}

So liest du diesen Code

Lerne die Syntax nicht auswendig. Folge dem Zustand, der sich in jeder Zeile ändert, und verbinde ihn mit der oben beschriebenen Invariante.

KOMPLEXITÄT

avg O(1), worst O(n)

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

WANN EINSETZEN

Gut geeignet

Choose it when its dominant operations match your workload.
Compare memory overhead as well as Big-O.

HÄUFIGE FEHLER

Was typischerweise schiefgeht

Calling average O(1) a guaranteed worst-case O(1).
Ignoring key equality and collision handling.

SO ERKLÄRST DU ES IM INTERVIEW

Struktur einer professionellen Antwort

Explain average O(1), collisions, load factor and resizing. Those details distinguish a strong answer from 'it is just a key-value map'.

Problem→Kernidee→Invariante / Zustand→Big-O→Trade-off

SCHNELLER INTERVIEW-CHECK

What problem does Hash Table solve?

A hash table maps keys to bucket locations using a hash function. It aims for very fast average lookup, insertion and deletion.

Was sollte ich zur Komplexität erwähnen?

Its typical cost here is avg O(1), worst O(n), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

Was ist der häufigste Fehler?

Calling average O(1) a guaranteed worst-case O(1).

WeiterlesenMapSetBloom FilterLRU Cache

class HashTable { constructor(size = 16) { this.buckets = Array.from({ length: size }, () => []); } hash(key) { let h = 0; for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0; return h % this.buckets.length; } }