Please enable JavaScript.
Coggle requires JavaScript to display documents.
Hash Tables Pag 254 Thomas Cormen "Introduction to Algorithms",…
Hash Tables
Pag 254 Thomas Cormen
"Introduction to Algorithms"
Fundamentals
Hash Tables
A hash table is an effective data structure for implementing dictionaries.
It generalizes the simpler notion of an ordinary array.
average time to search in a table is 0(1), but can take O(n) like a linked list.
Possible Cases
When the
set K of keys stored in a dictionary is much smaller than the universe U of all possible keys
. A HASH TABLE REQUIRES MUCH LESS STORAGE THAN A DIRECT ADDRESS TABLE.
reduced to:
while mantaining the time searching for an element:
If the universe U is large, storing a table T of size U may be impactical, but why??
Given the memory available on a typical computer.
Direct address tables
Simple technique that works well when the universe U keys is reasonably small.
Pag 254
Exercises
Pag 255
Applications
Collision Resolution by Chaining
Analysis of Haching
with chaining
Some Exercises
Pag 261
Hash Functions
Interpreting keys as natural numbers for hash functions.
The multiplication Method
Designing a universal class of hash functions
Tables
Opern Addressing
Linear probing
Quadratic probing
Double Hashing
Analysis of open-address hashing
Perfect Hashing
Case of Study
and Practical problems
Tablas Hash
Funcion procinicpal
Busqueda
Enocntrar la menor cantidad de colisiones
nO PODEMOS ORDENAR
Eficiencia ees la mejor.
Pero el cabezal
Session 4
