• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • paul wheaton
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Tim Holloway
  • Carey Brown
  • salvin francis

Why hashmap elements aren't in sorted order despite Red-black Tree data structure?

 
Ranch Hand
Posts: 238
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Red black trees always store elements in sorted order so TreeMap uses the RBT to store entries in buckets. HashMap too uses RBT then why HashMap isn't sorted?

Thanks.
 
Saloon Keeper
Posts: 10539
224
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Where did you get that HashMap uses a red-black tree? That's not true at all.
 
Master Rancher
Posts: 195
7
IntelliJ IDE Spring Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How I understood it:
- A TreeMap uses a RBT.
- A HashMap uses a hash table.
 
Marshal
Posts: 65467
249
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Afraid you have misunderstood the structure of both kinds of Map implementation. You also appear to have forgotten that you asked a very similar question only three weeks ago. Please remind yourself of that old discussion first. I thought we had answered all your questions there.
A TreeMap doesn't have buckets, but uses a red‑black tree to accommodate all its pairs. There is no need for buckets because each node on the tree contains exactly one pair.
As for a HashMap, how do you know that it uses trees at all? You said that in your previous thre‍ad. As I told you three weeks ago, the iteration order of a HashMap doesn't have anything to do with trees, nor with links, but something to do with hash codes. Remember that the iteration order will change if rehashing occurs because pairs will be redistributed to different buckets, and the way the hash codes are used will be different. Please have a look at the keySet() method for both Map implementations. Note what it says about iteration order in the documentation fo both methods. Also note what it says in HashMap about what structure the buckets contain.

We might merge this discussion with your older one.
 
Arun Singh Raaj
Ranch Hand
Posts: 238
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Please remind yourself of that old discussion first. I thought we had answered all your questions there.

Yes I do remember and I'm grateful to you all.

As for a HashMap, how do you know that it uses trees at all?

Yes, RBT isn't mentioned in java-docs of HashMap but wiki page of RBT and implementation page of HashMap given by Josh Bloch (I don't know how official this page is) do talk about it.

If HashMap really uses RBT to store entries in a bucket then the number of entries referenced to a single bucket are sorted, that's the reason of using RBT over linked-list so that search operation is improved from O(n) to O(log n). Isn't it?
 
Master Rancher
Posts: 4223
47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
From the implementation comment in that link (lines 143 onwards):

    * This map usually acts as a binned (bucketed) hash table, but
    * when bins get too large, they are transformed into bins of
    * TreeNodes, each structured similarly to those in
    * java.util.TreeMap. Most methods try to use normal bins, but
    * relay to TreeNode methods when applicable (simply by checking
    * instanceof a node).  Bins of TreeNodes may be traversed and
    * used like any others, but additionally support faster lookup
    * when overpopulated. However, since the vast majority of bins in
    * normal use are not overpopulated, checking for existence of
    * tree bins may be delayed in the course of table methods.
    *
    * Tree bins (i.e., bins whose elements are all TreeNodes) are
    * ordered primarily by hashCode
, but in the case of ties, if two
    * elements are of the same "class C implements Comparable<C>",
    * type then their compareTo method is used for ordering. (We
    * conservatively check generic types via reflection to validate
    * this -- see method comparableClassFor).  The added complexity
    * of tree bins is worthwhile in providing worst-case O(log n)
    * operations when keys either have distinct hashes or are
    * orderable, Thus, performance degrades gracefully under
    * accidental or malicious usages in which hashCode() methods
    * return values that are poorly distributed, as well as those in
    * which many keys share a hashCode, so long as they are also
    * Comparable. (If neither of these apply, we may waste about a
    * factor of two in time and space compared to taking no
    * precautions. But the only known cases stem from poor user
    * programming practices that are already so slow that this makes
    * little difference.)

The two bolded bits.
It's bins, some of which can be TreeMaps.
Those TreeMaps are sorted by hashcode.

Consequently, even if all the bins were TreeMaps they wouldn't be sorted in any meaningful (user-friendly) way in any case.
 
Campbell Ritchie
Marshal
Posts: 65467
249
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Arun Singh Raaj wrote:. . . don't know how official this page is . . .

Search your Java® installation folder for a file called src.zip. If you find it, unzip it and search for a file called java/base/java/util/HashMap.java or java/util/HashMap.java and inspect it. You will probably find its source the same as the openJDK link you posted; I think, yes, that link is “official”.
Remember that the implementation note is for internal use, and it is possible that a Java15 implementation will use something completely different.
The use of linked lists (old version) or trees (new version) is there to deal with poorly‑written hashCode() methods. If two distinct objects return the same hash code but false from ob1.equals(ob2), they will go into the same bucket, but you will have seen from the source JB posted that the chance of that happening 8× is approx 0.00000006 for a well‑written hashCode() method.. So you are only going to have buckets large enough for search speed to matter if you have a very badly‑written hashCode() method. Only if you have the same n right bits of the hash code after rehashing and using h & c − 1, as shown in this post, will you get your pairs going into the same bucket. A tree will speed searching that bucket from linear time to logarithmic time, as you said, but searching the tree/linked list is only part of the time required to find a “K” in your bucket.
And as Dave has told you, any trees are ordered by something to do with the hash code. Any linked lists are ordered by order of insertion to that bucket, which after rehashing will most probably be different from real insertion order, so you are not going to have a predictable iteration order.

Remember, as we saw earlier, linked maps and tree maps (which implement SortedMap) do give you a predictable iteration order. TreeMap has another requirement: the compareTo() method (or the appropriate Comparator#compare() method) must implement an ordering “consistent with equals”. Since it says nothing in the HashMap documentation about consistency with equals, I presume there is some mechanism in the buckets to include two objects returning false from equals() but with the same hash codes.
 
Stephan van Hulst
Saloon Keeper
Posts: 10539
224
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note also that the source speaks of using tree bins when the bins are overpopulated. With a normal loading factor, that should almost never happen.
 
Humans and their filthy friendship brings nothing but trouble. My only solace is this tiny ad:
professionally read, modify and write PDF files from Java
https://products.aspose.com/pdf/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!