This week's book giveaway is in the Java in General forum.
We're giving away four copies of Event Streams in Action and have Alexander Dean & Valentin Crettaz on-line!
See this thread for details.
Win a copy of Event Streams in Action this week in the Java in General forum!
  • 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
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

How does ArrayList or LinkedList maintain insertion order but not HashMap despite same data-structu?

 
Ranch Hand
Posts: 232
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I searched but could not understand what implementation of linked-list data-structure makes LinkedList preserve insertion order and why it is not the same for HashMap despite HashMap uses linked-list data structure for nodes.

Thanks in advance.
 
Marshal
Posts: 65038
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Arun Singh Raaj wrote:. . . HashMap uses linked-list data structure for nodes. . . .

I think you have misunderstood the structure of lists and maps. A hash map doesn't actually have nodes, and the most recent implementations no longer use links as they used to. I think I shall have to start from scratch with you. Watch this thread for at least three more posts.
 
Campbell Ritchie
Marshal
Posts: 65038
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is how an array list works, grossly simplified. This is similar to the actual implementation, but not exactly the same. You can find the code by unzipping the src.zip file which you may find somewhere in your Java® installation directory.

You have an array of Objects. Generics means you are only allowed types matching the type of E at compile time. When you retrieve anything from the array, you cast it to E. So let us look at the get(int) method first.That bit is easy enough to understand, I hope. The array values contains the elements of the list, and the index allows you to find the desired element. The size variable tells you how many elements you have, not the capacity of the array. The add(E) method adds one element to the end of the array.Remember the semantics of size++ and see how well it matches the 0‑based array indices. There is no risk of throwing an exception from line 72, so you always add an element to the array there, and you can therefore be aure you can return true. See the add link for more explanation about what that method returns.

You can now see that an array list maintains insertion order with the order of elements in the array. Remember we told you in answer to one of your other questions that it is possible to insert elements in a List at any location; when you do that, you are altering the list so it now has an order different from its insertion order; you can also alter its order by sorting the List.

One type of data structure down: two to go. I shan't be able to reply immediately, I am afraid.
 
Ranch Foreman
Posts: 3298
22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arun, is it possible you read about LinkedHashMap and confused it with a regular HashMap?  Those are two different classes, similar in many ways but different in others.  The LinkedHashMap does use a linked list structure, in addition to the regular HashMap structure.  But a regular HashMap has no linked list, normally.  It's possible you've mixed up info on these two different classes.
 
Arun Singh Raaj
Ranch Hand
Posts: 232
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the info.

Campbell Ritchie wrote:This is how an array list works, grossly simplified. This is similar to the actual implementation, but not exactly the same.

I get it!

I should've asked you about only LinkedList and HashMap. As I've read somewhere, the linked-list of nodes in HashMap (Java 8)is converted into Red-black tree when it exceeds 8 elements so it still does have linked-list.
Anyway, I want to know in context of Java 7. How does insertion order is preserved in LinkedList and why it couldn't preserve in HashMap. It would be a great help if you respond. Thanks.
 
Campbell Ritchie
Marshal
Posts: 65038
247
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Arun Singh Raaj wrote:Thanks for the info. . . .

That's a pleasure

I should've asked you about only LinkedList and HashMap.

Too late; as Magnus Magnussen would have said, “I've started, so I'll finish.” Mwaahaahaahaahaahaahaahaahaahaa!

As I've read somewhere, the linked-list of nodes in HashMap (Java 8)is converted into Red-black tree when it exceeds 8 elements . . . .

But that bit isn't relevant. I shall have a look at linked lists. Remind yourself how a linked list works from a diagram; this Wikipedia page has better diagrams than I coiuld draw on screen. Most linked lists to be used as lists are implemented as doubly#x2011;linked lists, as you will see if you scroll that page about one‑quarter way down.Adding something at the end of the list entails something like this:-Note how much more you have to do than simply assigning an array element. Note that previous and next fields in the nodes are accessible because they are private fields in nested classes. As you can see, the linked list has nodes which can be accessed from each other. To find a node n it is necessary to traverse n − 1 nodes to find it. As we told you in a different thread, that is why it is slower to find elements with the get() method in a linked list. I am sure you can see why the linked list maintains insertion order.

Hash maps are totally different, but it will be a little while before I can explain them. Two down, one to go.
 
Saloon Keeper
Posts: 6039
58
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Arun Singh Raaj wrote:Thanks for the info. I get it! I should've asked you about only LinkedList and HashMap. As I've read somewhere, the linked-list of nodes in HashMap (Java 8)is converted into Red-black tree when it exceeds 8 elements so it still does have linked-list. Anyway, I want to know in context of Java 7. How does insertion order is preserved in LinkedList and why it couldn't preserve in HashMap. It would be a great help if you respond. Thanks.


A red-black TREE is not a LIST or, more specifically, not a LINKED-LIST.

A hashCode() method is a method that returns an int. Each of these methods can make their own choices as to what algorithm is used to come up with the int. From an outsider's point of view, the ints being returned are usually some random distribution of values with no way for the user to discern any order to the data based on the int value. This int is then used to find references to actual objects using this int as an index into a hash table. (A subtlety here is that the HashMap itself my further reduce the int so that the range of values fits a smaller sized table.) When you iterate through a HashMap you are iterating through the table which is (usually) in hash value order, again, apparently random order.
 
Arun Singh Raaj
Ranch Hand
Posts: 232
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Note that previous and next fields in the nodes are accessible because they are private fields in nested classes. As you can see, the linked list has nodes which can be accessed from each other.

Yes, I get it!
It's easy but I took much time to understand.
LinkedHashMap.Entry has two additional fields:
(package private) LinkedHashMap.Entry<K,V> after
(package private) LinkedHashMap.Entry<K,V> before
These two fields record the insertion order. The picture makes it more clear.
linkedhashmap-internal-working-to-record-the-insertion-order.png
[Thumbnail for linkedhashmap-internal-working-to-record-the-insertion-order.png]
 
Campbell Ritchie
Marshal
Posts: 65038
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Forget about linked hash maps for the time being. They are hybrid data structures, with a list running in parallel with a hash map. The map does the indexing, and the list maintains insertion order. I think the additional fields are a red herring at this moment. Any lists are not made until after the Entries have been sorted by hash code.

Let us assume you have a class with a well‑designed hashCode() method, not only correctly implementing the general contract of equals() and hashCode(), but also giving a good spread of different hash code with differences in the lower‑order bits. Let's imagine we have a hash map with a capacity of 16. That map will have a 16‑element Map.Entry[] array. So what you want to do is distribute the Entries across the array. Remember that the array will be replaced by a 32‑element array if you put() more than 12 pairs, and the load factor is the default of 75%.
So, you take the hash code, and you want its rightmost four digits. What you do, as shown in this old thread, is use the bitwise and operator with 15 one less than capacity as the right operand. Calculate h & c − 1 which gives you a non‑negative array index for any array which can take elements and has a size which is a power of 2, i.e. 2⁰=1, 2¹=2, 2²=4, 2³=8, 2⁴=16, 2⁵=32...2³⁰. So entries are put into the array depending on their hash codes, and there is no insertion order at all.
When you enlarge the array because the size of the map exceeded the load factor (default=75%), all the elements are removed fro the old array and put into the new array using a similar technique with h & c − 1 but c has now doubled. As you see, even the old hash code order has been obscured. Two “K”s with hash codes ending ....19 and ....09 (hexadecimal) might be in the same array index for a 16‑element array, but they are in different array indices for a 32‑element array.

Neeless to say, what I have said is a dreadful oversimplification. I haven't mentioned rehashing, because that doesn't reflect insertion order. Nor have I said anything about what happens about collisions (two “K”s with hash codes ending the same and getting the same array index). But I shall mention collisions in the next post.
 
Campbell Ritchie
Marshal
Posts: 65038
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Without some special precautions a map can go wrong if you get collisions. Let's imagine we have two “K”s with (hexadecimal) hash codes ending ....19 and ....09. If you put() them both as parts of pairs into an empty hash map, capacity=16, load factor=75%, then h & c − 1 will give 9 for both, and they both go into index 9. Maybe you use the fields in the Map.Entry to create a little linked list, and maybe you create a little binary tree. So do you get this?or this?If you go to that list or that tree, which order are you going to get the elements back in? Will that order change if the array is full and has to be enlarged? You can only get insertion order if you use some other mechanism to maintain insertion order.

A linked hash map appears to use its Entries to create a linked list, and that is an additional feature over and above what you find in hash map (remember that LinkedHashMap is a subclass of HashMap, and it is only this additional feature that enables a linked hash map to maintain insertion order. These links remain unchanged even if the map's capacity has to be increased.
 
Campbell Ritchie
Marshal
Posts: 65038
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note that Carey didn't say that hash codes are random; he said they appear random to the user; particularly if you take only part of the hash code (h & c − 1), the results are unpredictable by users.
 
Campbell Ritchie
Marshal
Posts: 65038
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Last night, I wrote:. . . a linked list . . . is an additional feature . . .

I have now noticed that MS mentioned that list as an addition to a hash map before I did.
Your diagram with the squares is a bit hard to understand, but it seems correctly to depict what is going on in your capacity 4 map. Remember that you have 5 elements in that map, so you would expect it to have enlarges its backing array to capacity 8. You wrote ArrayList on your diagram where array might be more appropriate, but you can verify that from the map's code.

Your diagram merits a cow
 
Are you okay? You look a little big. Maybe this tiny ad will help:
Java Code Review and Psychology
https://coderanch.com/t/714798/java/Java-Code-Review-Psychology
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!