APP-Notes

Hashing

• inserts,updates, deletes in O(1)
  • Beter dan O(log n) of (n) voor de meeste andere datastructuren
• Volgordelijkheid niet mogelijk
• De bijbehorende datastructuur is de Hash table
  • key-value pair
• Techniek voor vinden van sleutel heet de hash function
  • Moet snel en slim zijn
• Primgetal omdat anders alleen bijvoorbeeld de even getallen gevuld worden

Java

• HashTable: synchronized, geen null values
• HashMap: niet synchronized, mag 1 null value als key bevatten
• String.hashCode()

Separate Chaining

Array met bij ieder item een linked-list

• Dubbele waardes komen in de linked-list

Probing

Eerstvolgende lege cell zoeken

• Lineair
• Quadratic

Huiswerk

• 20.5
• 20.6 (met 11)
• 20.2
• 20.3