Hashing, Hash Tables and Hashing function Flashcards
Another name for a hashing function?
hashing algorithm
What is a hashing function?
A set of rules which is applied to a key field of the data to point to an address or location within a hash table (hash value).
What is a common hashing algorithm?
divide key by the number of cells within a table and take the remainder as the address
What is the purpose of a hashing algorithm and a hash table?
To create an index for the data by transforming the key fields into addresses. It is done to allow quick lookup, deletion or insertion of data.
What is the problem we often experience with a hashing algorithm? What is this called?
The hashed value is equal to a cell location which is already taken. This is called a synonym
What is the name of a situation where two record keys point to the same address or location within a hash table?
a collision
What do we usually do to overcome the collision?
We place the item at the next free space within the hash table
What is a hash table?
a collection of items set out in a way which allows quick access. It is 2d , with one dimension containing the data and the other the key (hashed one)
A hash table is used to…..
to access data in a random way, just like an array
Can hashing be applied to strings?
Yes by searching up the ASCII values of the alphanumeric data
How is a hash table usually implemented?
An array or a list
What makes a good hashing function?
one that tries to avoid getting duplicate data and causing collisions, however this is unavoidable it can be reduced
What does a hash table store?
keys using hash values as an index
Does a hashing function always return the same hashed value for the same keys?
YES, this is because later we will be able to find the location of the key within the hash table
What does storing key values in the next free space come to?
clustering
this increases the likelihood of collisions
How can we deal with clustering?
combining a hash table with a linked list which will be linked to a hash value within hash table and store keys that have overflown
How can we avoid having clustering and collisions?
by having a good hashing algorithm
How do we search for an item within a hash table?
- apply hashing algorithm to the key field of the item
- examine resulting cell
- if the item is there return it
- if the cell is empty the item is not in the table
- if there is another item at this index then keep moving forward until a free cell is found or the item you’re looking for is found
What will an efficient hashing algorithm do well?
generate the least collisions
What is a folding method?
process of creating a hash value. The key is split into equal size clusters and these are added together. If the resulting address is exceeding the maximum capacity of the table then the address is divided by a 100.
The fuller the hash table becomes the more likely….
collisions will occur, this needs to be taken into account when designing a hashing algorithm and deciding on table size
What is rehashing?
process of finding the next empty slot when a collision has occurred. It can loop round to the beginning of the table if the end has been reached. This can be amended to e.g. check every 3 spaces
What are the primary uses of hashing and hash tables?
- to provide efficient lookup
- encrypted passwords, PINs, etc.
- used to implement a dictionary
When we assign a key to the next free cell what is this called?
linear probing , this creates clustering as the hashed index is not randomly distributed
What is this called when we implement a linked list which has a hash table index pointing to it. This linked list contains the data.
separate chaining
