How to return the position of an element in HashSet?

4

I have the following structure:
HashSet<Contato> contatos = new HashSet<Contato>();
How to return the position of a given Contact element that is contained in HashSet?

I was searching and found a way to get back to the position, but I do not know if the code below is totally :

public int getPosicao(Contato c) {
    int posicao = 0;
    for (Iterator<Contato> it = contatos.iterator(); it.hasNext();) {
        Contato contato = it.next();
        if (contato.equals(c)) {
            break;
        }
        posicao++;
    }
    return posicao;
}
    
asked by anonymous 08.10.2014 / 23:58

2 answers

4

As pointed out by Renan in comments , HashSet s are not sorted, so it does not make much sense to speak of the" position "of an element within it. Changes in the set - or even the creation of another object HashSet with the same elements - can completely change their order.

However, if you want a definite order, you can choose LinkedHashSet or by TreeSet - the first maintains the elements in the order in which they were inserted, and the second uses a comparator (or natural order of objects) to establish the order of the elements of the set. From here you can for example iterate over the elements to find out your index (inefficient, I agree, but I know it's the only way).

For more information about how HashSet works - and why they are not sorted, and why the order may change as the collection changes - see the related question:

    
09.10.2014 / 00:17
4

A hashset is like a book, in which the keys are the table of contents and the values are the chapters.

In other words ... When you insert an element into a hashset, a hash of the object. Hence you have a structure that holds information in pairs. Each pair has on one side the hash of the object and on the other a reference to the object.

It turns out that hashes are usually strings well ... random. For example, assuming the hash algorithm is the MD5 :

  • string hash foo is acbd18db4cc2f85cedef654fccc4a4d8 ;
  • The hash of bar is 37b51d194a7513e45b56f6524f2d51f2 ;
  • And of baz is 73feffa4b7f6bb68e44cf984c85f6e88 .

If you were to sort the hashes in alphabetical or hexadecimal order, you would have to reindex the set to each added element. This would leave the inserts slow, and one of the goals of hashset is to be fast.

Complicating, it is possible to have hashes colliding. This occurs when two objects have the same hash. In this case, it is common for a hashset to add a little salt (this is a technical term!) To one of the objects and generate a new hash different to it. So the clutter in the indexes gets even bigger.

You may want to use a map of chained hashes. This structure guarantees the insertion order and there is a class in Java for this: link

    
09.10.2014 / 00:23