3
I have to implement a hash table, also known as a scattering table, however my inexperience with this data structure can cause many collisions in my implementation. I would like to know what practices I should approach and how to know if my table is well spread.
3
A mirroring table uses some slots to store objects according to the hash, not the hash in itself.
Collisions are expected, as several hashes may be stored in the same slot.
One of the internal Java implementations creates an array of slots based on the number of elements in the table (map, in case).
Like hashes are nothing more than numbers, basically one makes an account and it is determined that if the number of the hash is in a certain range it will stop at a vector position.
For example, imagine that in your system hashes may assume values of 1..100. You can create a table with 10 positions so that if the hash of an element belongs to the set [1..10], it will be placed in the first position of the table. And so on.
Each table position is actually a list of elements. When there is collision at include time, you simply add the new element in the list.
The problem is that when retrieving, in addition to finding the position in the table, you have to scroll through this list to see if the element to be removed from the table is in that list.
The implication of this is that the most efficient algorithms of hashing are those that generate the most evenly distributed values.
In addition, a more advanced implementation can check for many conflicts and dynamically increase the number of positions in the mirroring table to decrease the number of collisions.
Browser other questions tagged java
You are not signed in. Login or sign up in order to post.
Take a look at this article: https://www.caelum.com.br/apostila-java-structures/tabelas-scattering/#9-1-introducation. If the doubt persists, it would be a good idea to specify your question further, for example by adding more details about your case. Good luck!
– StillBuggin