-2

What would have happened if Map.Entry was Map.Entry [] and not list in hashMap? I just want to understand why bucket is list and not array implementation in hashmap java.

erhun
  • 3,549
  • 2
  • 35
  • 44
Brijesh
  • 191
  • 1
  • 5
  • 11
  • 1
    an array would have to be re-sized each time you add an element to it. Lists are much more dynamic – chancea Feb 18 '15 at 17:55
  • was it only reason, i mean to find element from list would have to go each and every node. – Brijesh Feb 18 '15 at 17:57
  • 5
    Barring an official document talking about this design decision somewhere, answers to this question are going to be entirely opinion based – ControlAltDel Feb 18 '15 at 17:57
  • I don't have Java 8 here at work, but in 7 the data in a `HashMap` *is* an array: `transient Entry[] table;` – azurefrog Feb 18 '15 at 18:00
  • 1
    @azurefrog Each Entry in the array is/was actually a linked list. The question appears to ask about this linked list. – Radiodef Feb 18 '15 at 18:02
  • where exactly did you see `Map.Entry` list ? Is it HashMap ? Also your version would help. As far as I know it's just an Entry[] – Arkantos Feb 18 '15 at 18:02
  • @Radiodef Ah, I misunderstood the OP's question then, I thought he was talking about the `HashMap` backing array. – azurefrog Feb 18 '15 at 18:05
  • Map.Entry class has next pointer, is my understanding correct?. – Brijesh Feb 18 '15 at 18:06
  • The next pointer is to deal with hashing collisions. This allows an arbitrary number of `Entry`s to be stored in a given hash bucket. – azurefrog Feb 18 '15 at 18:10
  • how next pointer is used to detect hash collision?. I think it is done just by flipping lower bits of hash code. – Brijesh Feb 18 '15 at 18:14
  • @Brijesh It's not used to detect a hash collision, but is used when you create an `Entry` for any given index in the backing array. The new `Entry` is created with its `next` pointing at the previous entry (which could be `null`), and then that index populated with the new `Entry`. – azurefrog Feb 18 '15 at 18:17

3 Answers3

2

I think you're talking about the LinkedList in each bucket entry.

Let's say it's an Array, when you add an element to that bucket you have to create an array of some definite size say 10, here you're already allocating memory for 10 entries (of course it's not too much) but the elements in that array are added based on the elements having same hashcode() but different equals(). What if there are only 2 elements in that bucket but we reserved space for 10, you may end up having sparsely filled arrays.

Also you've to deal with re-sizing of these bucket arrays as long as you add elements having same hashcode. And when you need to deal with re-sizing, you usually maintain a counter to check if the number of elements reaches the current array size, create a bigger array, copy all these elements and you have to all these things in a single put call to Map :) The main advantage of arrays is random access, but when you try to get some element from array, it doesn't know which one has matching equals(), so it'll traverse through all the elements of that array loosing the very advantage of arrays.

But if you use a LinkedList, you just keep adding elements, no need to create/re-size an array. Also if you notice, one smart thing they're doing while adding elements to LinkedList is they don't traverse through the entire list to find the last element. They create a new Entry object whose next element is pointing to the existing element stored in bucket index and update the bucket index to point to this new element, that way they don't have to traverse the list every time you add a new element. So it's a gain in memory and speed :)

One more update in jdk8 is that this LinkedList implementation in changed to a Tree once it reaches a threshold(8). This is to facilitate faster look ups, so instead of traversing through all the elements to get some element in O(n) (linear) time, it's now O(logn)

Arkantos
  • 6,530
  • 2
  • 16
  • 36
  • For better understanding of HashMap implementation, read [this](http://javahungry.blogspot.com/2013/08/hashing-how-hash-map-works-in-java-or.html) – Arkantos Feb 18 '15 at 18:31
  • 1
    Noticeably, hardcoded singly-linked lists are really, really efficient for very small n, like 0, 1, or 2 -- which is what you expect for hash table buckets. – Louis Wasserman Feb 18 '15 at 18:37
  • I agree it is the sparse arrays and conserving space argument. – Khanna111 Feb 18 '15 at 19:37
1

Well it would simply have been more difficult to handle, for example re-sizing.

If you look at the code of List classes, you will find out that at the base, most of them are just Array with methods to handle the array easier for developers.

Jean-François Savard
  • 20,626
  • 7
  • 49
  • 76
  • 1
    Yeah i agree with List implementation but Map.Entry has next pointer which which will point to next location in memory and not continuous memory block – Brijesh Feb 18 '15 at 18:00
  • Well not all lists are just Array wrappers.. like linkedlist – chancea Feb 18 '15 at 18:03
  • @Brijesh The next pointer doesn't point to the next location in memory, it points to the previous `Entry` that lived at a given index in the backing array at the time that you create a new `Entry` for that index. – azurefrog Feb 18 '15 at 18:15
  • @azurefrog as per my understanding, entry is array objects but internally each bucket can have list of objects with same hashcode, which is i mean to say list. So it has pointer which points to next location. Is my understanding correct?. – Brijesh Feb 18 '15 at 18:20
  • `Entry` is itself a singly linked list which has 4 properties - key, value, hashcode and a `next` property which is another `Entry` object, so to put it simply, HashMap is an Array of LinkedLists :) – Arkantos Feb 18 '15 at 18:49
1

This below mentioned difference will help you understand why not Map.Entry[]

Main consideration is SIZE(point no 2) but there are other reasons too

Lists(Linked List in this case) are preferable over arrays when:

  1. You need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)
  2. You don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big
  3. you don't need random access to any elements

Arrays are preferable when:

  1. you need indexed/random access to elements

  2. you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

  3. Arrays have O(1) random access, but are really expensive to add stuff onto or remove stuff from.

More Reasons are here , Please Help yourself

Community
  • 1
  • 1
Neeraj Jain
  • 7,643
  • 6
  • 34
  • 62