Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

HashSet Magic

 
Cole Tarbet
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 :
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic