How to return the position of an element in the Hashset?

Asked

Viewed 1,762 times

4

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

I was researching and found a way to get back the position, but I don’t know if the code below is fully right: 

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;
}
java list
  • 1

    Hashsets are not ordered (but it’s important to ask this and have an answer, so here’s a +1).

  • @Renan posted a code on my question..

  • @Pedrorangel Yes, your code is right. I think (it’s been a while since I’ve touched Java, I don’t really remember) that you can simplify it using for ( Contato contato : contatos ) { ... } (foreach). Remembering whenever the position returned may change in the course of the program, of course.

  • @mgibsonbr blz then^^

2 answers

4


Like pointed out by Renan in the comments, HashSets are not ordered, so it does not make much sense to speak in 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 your order.

However, if you want a defined order, you can opt for the LinkedHashSet or by TreeSet - the former maintains the elements in the order in which they were inserted, and the latter uses a comparator (or the natural order of objects) to establish the order of the elements of the set. From there you can for example iterate on the elements to discover your index (inefficient, I agree, but that I know is the only way).

For more information on how the HashSet - and why they are not ordered, and why the order can change as the collection changes - see the related question: "How the implementation of hash tables works?"

4

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

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

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

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

If you were to sort the hashes alphabetically or hexadecimally, you would have to reindexe the set to each added element. This would slow the insertions, and one of the goals of the hashset is to be fast.

To complicate, it is possible to have hash collision. 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 different hash for it. So the mess in the indexes gets even bigger.

You may want to use a chained hash map. This structure ensures the insertion order and there is a class in Java for this: http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html

Browser other questions tagged java list

You are not signed in. Login or sign up in order to post.