How best to make a spreadsheet

3

I have to implement a hash table, also known as a spreadsheet table, however my inexperience with this data structure can cause many collisions to occur in my implementation. I would like to know what practices I should address and how to know if my table is well spread.

    
asked by anonymous 20.05.2016 / 02:36

1 answer

3

A mirroring table uses some slots to store objects according to hash , not the hash .

Collisions are expected, as several hashes can be stored in the same slot .

One of the internal implementations of Java creates an array of slots based on the number of elements in the table (map, in case).

hashes are nothing more than numbers, basically if you make an account and determine that if the hash number is in a given range it will stop at a position vector.

For example, imagine that in your system hashes can assume values of 1..100 . You can create a table with 10 positions so that if the hash of an element belongs to the [1..10] set, 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 a collision when adding, you simply add the new element to the list.

The problem is that at the time of retrieving, in addition to finding the position in the table, you have to go through this list by checking if the element to be taken from the table is in that list.

The implication of this is that the most efficient hashing algorithms are those that generate more uniformly distributed values.

In addition, a more advanced implementation can check for many conflicts and dynamically increase the number of positions in the mirroring table, in order to decrease the number of collisions.

    
20.05.2016 / 11:15