- Home
- Interview Questions
- Data structures and Algorithms
31.
What is a collision?
A collision is the situation when two different keys x and y have the same hash code - thus, h(x) = h(y).
32.
List the several hashing methods.
Here are some hashing methods:
- division method
- middle square method
- multiplication method
- Fibonacci hashing
33.
Define scatter table?
A scatter table is an array-based hash table. The essential idea behind a scatter table is that all of the information is stored within a fixed size array and hashing is used to identify the position where an item should be stored.
34.
Describe several collision resolution strategies in open addressing.
There are three resolution strategies in open addressing:
- linear probing - the interval between probes is fixed - usually at 1
- quadratic probing - the interval between probes increases linearly. This way, the indices are described by a quadratic function.
- double hashing - the interval between probes is fixed for each record but is computed by another hash function
35.
What is lazy deletion?
lazy deletionis a method of deleting elements from a hash table which uses open addressing. Deletions are performed by marking an element as deleted, without erasing it entirely. Deleted locations are treated as empty when inserting and as occupied during a search.
|
|
||||||||||||||||||||||||||||
