Flashcards
4.2.6 Hash Table
Cards in this deck (16)
- 1SearchingLinear Search: This involves placing each value in sequential memory locations, then searching from start to finish to find it.
This is an inefficient search, as in the worst case scenario, it could take as many searches as there are values in the list. - 2Hash TablesAnother way to store data to make it quick to search is by using Hash Tables.
The idea behind a hash table is that a hash function is used on the data to determine where it is stored
A hash function is a non-reversible function that produces an output within a specified range. - 3Hash TableTo search this table, we apply the hash function to the record we’re looking for and go straight to that memory location.
We can now find a record in 1 step. - 4CollisionsWhat happens if 2 values have the same hash?
If we want to store 90002985, it has a mod 7 value of 2, which is already in use.
This is called a collision. - 5CollisionOpen Hashing
Closed Hashing - 6Open HashingIf a collision occurs, place the value in the next available slot.
Goes to next slot open.
But Table needs to be bigger than list size - 7Open HashingDuring searching, a linear search is performed from the hash value until the next null cell
- 8Open HashingFor open hashing to work, the table needs to be roughly a third larger than the maximum number of records.
This can lead to inefficiency if there are few collisions. - 9Closed HashingClosed hashing make use of linked lists
Each address contains a pointer to the first element of a linked list.
If a collision happens, a new element is added to the linked list. - 10Closed HashingClosed hashing can be more efficient than open hashing when there are lots of collisions.
If a value isn’t there, only the length of the linked list needs searching.
If there are no collisions, closed hashing has more overhead than open hashing. - 11Hash FunctionThe n mod m hash function works ok for our examples.
Real hash functions can be different.
A perfect hash function is one that results in no collisions, but they are very difficult to find in real examples.
The better the hash function, the fewer collisions. - 12DeletingTo prevent this issue, a deleted value must have a specific “deleted” flag set, rather than just removing the value.
As long as the system is able to differentiate between a genuinely empty cell and one which contains a deleted value, the hash table will still work. - 13DeletingWhen adding a new value, deleted values will be overwritten.
- 14RehashingHash tables offer exceptional performance when not overly full.
Array-based data structures all have the same issue:
Make the table to small, and performance degrades, and possibly overflows
Make the table too big and waste memory - 15RehashingRehashing attempts to avoid this issue by expanding the table as it fills.
With open hashing, performance degrades once more than half the slots are filled
So when it goes past half full we re-hash the table
To re-hash, simply expand the table, then run the hash function on the existing data to get its new slot. - 16—
Information
- Description
- Flashcards on 4.2.6 Hash Table, created by Ed Allen on 30/04/2020.
- Created by
- Ed Allen
- Views
- 1
- Rating