Week 10 Workshop 7 Linear Data Structures – Part 3 Application - Hashing

 0    12 flashcards    up804653
mp3 indir Baskı oynamak kendini kontrol et
 
soru English cevap English
what is hashing?
öğrenmeye başla
Hashing involves using an array for the efficient storage and retrieval of information
what is the idea effeicency for hashing for storage and retrival?
öğrenmeye başla
O(1)
how are collisions resolved?
öğrenmeye başla
Collision is resolved by finding a free location. Next location (1) is still free - use this location. Key 10 maps to position 2
what defines a " good hash function"
öğrenmeye başla
A good hash function must: Quick and easy to compute Minimise collisions Achieve an even distribution of keys Aim: Efficiency O(1) for storage and retrieval of data
what is truncation?
öğrenmeye başla
Ignores parts of the key and uses remaining parts as the hash value. Fast but can fail to distribute keys uniformly.
what is folding?
öğrenmeye başla
Split key into several parts and then combine the parts to obtain hash value. Often gives better spread than truncation.
what is Modula Arithmetic?
öğrenmeye başla
Divide key by table size - use remainder as the hash value For good spread - table size must be prime.
what is Collision Resolution with Chaining
öğrenmeye başla
Uses singly linked lists to resolve the collisions.
what is Collision Resolution with Open Addressing using Linear Rehash or Linear Probing
öğrenmeye başla
A linear search of the table from the hashed position is used to find an empty slot.
what is Collision Resolution with Open Addressing using Quadratic Rehash or Quadratic Probing
öğrenmeye başla
The following slots are tried to find an empty slot: h + i2 (mod table size) for i = 1,2,3... ie: slots tried are: h, h+1, h+4, h+9, h+16 ...... (mod table size) Works well if the table size is prime.
what is Collision Resolution with Open Addressing using Add the hash Rehash
öğrenmeye başla
The hash value is added to the hashed value repetitively to find an empty slot. ie: slots tried are: h, 2h, 3h, 4h, ... (mod table size) Works well if the table size is prime.
what is Collision Resolution with Open Addressing using random Rehash
öğrenmeye başla
a pseudo‑random number generator is used to obtain the increments Uses a seed to initiate the sequence of random numbers. Excellent in avoiding collisions but slower

Yorum yapmak için giriş yapmalısınız.