4.2.6-7 - FoDS (Hash Tables and Dictionaries) Flashcards
What is a hash table
A Data structure that creates a mapping between keys and values as pairs
What are hash tables made of
- An array we call a hash table
- This is linked to a hash function
- Keys are inputted into the function which returns a hash value
- The hash value determines where in the hash table the value is stored
What are some examples of hash functions
- Summations
- Modulus functions
What is meant by a collision
- When two key values compute to the same hash
What are the 3 ways to avoid collisions
- Closed Hashing
- Open Hashing
- Rehashing
How does a Closed-Hashing work
When there is a collision:
- data is stored in the next available empty location in the hash table
- The original location points to the next location
How does Rehashing work
When you rehash, a new hash table is created (larger if needed). The key for each item in the existing table will be rehashed and the item will be inserted into the new hash table.
How does Open Hashing work
data that will cause collisions to a specific location will be put into an overflow table that appends size when needed and is pointed to by a pointer that is initially set to null
How does a simple Searching Algorithm in a hash table work
- Feed the key into the hash function
- Go to the array index of the value that is outputted by the hash function
- If the value, we are searching for is the value that is found we stop
- If not follow the overflow linked list in sequence until the value is found
How does a simple Inserting Algorithm in a hash table work
- Feed the key into the hash function
- Go to the array index of the value that is outputted by the hash function
- If the location is empty insert the value into that memory location
- If not follow the linked list until a free space is found (shouldn’t it be full at the end, then you append)
- Then you insert the value in that free space
How does a simple Deleting Algorithm in a hash table work
- Feed the key into the hash function
- Go to the array index of the value that is outputted by the hash function
- If the value, we are searching for is the value that is found mark the memory location as empty
- If not follow the linked list in sequence until the value, we want is found and mark that index as free
- Update the free pointers in the linked list
What is meant by a dictionary
A dictionary is a collection of key-value pairs in which the value is accessed via the associated key
What is meant by an abstract data type
- It is an abstract data type meaning that it’s a conceptual model of how data is stored and the operations that can be performed on them
What are the features of a dictionary
- General purpose data structure
- Random Access
- Used for storing groups of objects
- Has a set of keys, each with an individual associated value
- When the key is supplied the value is returned
- No order
What are other uses of dictionary
- Information retrieval
- Caching
- Dictionary based compression
- Natural Language dictionaries
What is meant by the load factor of a hash table, what is teh max load factor and what does a high load factor entail
- The ratio between the number of stored elements and the size of tthe hash table
- The decimal value cannot be greater than 1
- A high load factor means the table is nearly full
