12

When constructing a HashSetand a LinkedHashSet from a collection, the initialCapacity is set to different values in the default implementation.

HashSet:

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

LinkedHashSet:

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

I'm sure there is a perfectly valid reason for this, but I fail to see it.

7
  • Please read the docs before you post questions here: A linked hash set has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashSet. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashSet, as iteration times for this class are unaffected by capacity. -- docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html Jan 17, 2017 at 8:31
  • @TimBiegeleisen I didn't realize I couldn't press Enter in comments. Jan 17, 2017 at 8:32
  • Info: HashSet uses the greater of 4/3 the size or 16, while LinkedHashSet uses the greater of twice the size, or 11. Both use a load factor of 0.75f Jan 17, 2017 at 8:33
  • I won't post this as a formal answer, but off the top of my head, it is probably more costly to rehash a LinkedHashSet than a plain HashSet, as the former has a linked list running through it, which might also have to be refactored/recalculated. By making the initial capacity greater, we might avoid exceeding the initial capacity for some typical use cases. Jan 17, 2017 at 8:38
  • @TimBiegeleisen Exactly what I was thinking about, I think it's actually an answer.
    – Maroun
    Jan 17, 2017 at 8:39

2 Answers 2

4

From the code you showed us, here are the specs for HashSet and LinkedHashSet:

data structure | initial capacity      | load factor
HashSet        | max(1.333 * size, 16) | 0.75
LinkedHashSet  | max(2 * size, 11)     | 0.75

Off the top of my head, it is probably more costly to rehash a LinkedHashSet than a plain HashSet, as the former has a linked list running through it, which might also have to be refactored/recalculated. By making the initial capacity greater, we might avoid exceeding the initial capacity for some typical use cases.

When the initial capacity of a hashtable data structure is exceeded in Java, it needs to be expanded. This requires, among other things, that every entry in the table needs to be rehashed to a new bucket. The cost of doing this should be roughly the same in both LinkedHashSet and plain HashSet. However, a LinkedHashSet has an additional requirement when expanding the capacity, because it maintains a linked list running through the entries. This list might also need to be refactored in the process. Hence, I would expect the cost of expanding capacity to be higher in LinkedHashSet than plain HashSet. By giving LinkedHashSet a greater initial capacity, we can avoid this costly expansion of capacity for a longer time.

LinkedHashSet Javadoc

3
  • That sounds reasonable. But if that assumption is correct, I should not rely on the defaults when constructing a LinkedHashSet from a Collection for read-only purposes, especially if the Collection is very large. Jan 17, 2017 at 8:46
  • Can you update your question with the use case(s) you have in mind regarding "read-only" usage? Jan 17, 2017 at 8:48
  • Isn't that just a side note? Given that I actually wondered about this, it's far from obvious that the read-only purpose is a valid piece of information :) Jan 17, 2017 at 8:55
0

I have roughly looked at the source code here. LinkedHashSet and HashSet are maintained by LinkedHashMap and HashMap, and the essence of the data structure of LinkedHashMap is that the same set of data uses different arrangements, which can be understood as:

5, 3, 2, 4, 1 is the arrangement of the array, 1, 2, 3, 4, 5 is the arrangement of the linked list. The parameter initialCapacity is related to the array, the linked list does not need to be expanded, it will only increase with more data. So it is concluded that the linked list has nothing to do with the size that affects the initialCapacity parameter. As for this question, I think it's two different ideas, **map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); The idea is to not put the value after the collection is full. The most used scenario is the get value, because it can be found that the HashMap will expand again when the value is set again with this parameter. **

**super(Math.max(2*c.size(), 11), .75f, true); is the opposite of the idea, it has reserved space after the filled value is put in, so that The put value will not automatically expand immediately. So why 2x? The answer is that the underlying principle of hashMap expansion is to expand by 2 times. **

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.