permaculture playing cards*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes HashSet Magic Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "HashSet Magic" Watch "HashSet Magic" New topic
Author

HashSet Magic

Cole Tarbet
Ranch Hand

Joined: Aug 02, 2011
Posts: 30
Apparently, the unsorted unordered HashSet (pg. 562 K&B) comes with a bit of magical sorting after all. The initial capacity of a HashSet is 16 so adding more numbers ruins the magic. http://download.oracle.com/javase/6/docs/api/java/util/HashSet.html

After reading up on hashing, I realized that this must be caused by the hashing algorithm doing (key % tableSize) which produces pseudo-sorting up to initial capacity. Am I correct?



[15]
[14, 15]
[13, 14, 15]
[12, 13, 14, 15]
[11, 12, 13, 14, 15]
[10, 11, 12, 13, 14, 15]
[9, 10, 11, 12, 13, 14, 15]
[8, 9, 10, 11, 12, 13, 14, 15]
[7, 8, 9, 10, 11, 12, 13, 14, 15]
[6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Cole Tarbet wrote: I realized that this must be caused by the hashing algorithm doing (key % tableSize) which produces pseudo-sorting up to initial capacity. Am I correct?

You are right! from HashSet[again it is nothing but HashMap] source code :
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: HashSet Magic
 
Similar Threads
Regular expression - Greedy and Reluctant quantifiers
Why am able to pass a Set (non-generic) to a method expecting Set<Number>?
shift operators
Boolean Question