PowerShell - Why are keys in Hashtables sorted randomly?

PowerShell guru and Admin-extraordinare Jeff Hicks asked a great question that many a Windows administrator has probably asked themselves when working with Hashtables in PowerShell: Why do the key/values come out in a different order than put in? This is a great question and the answer lies in computer science theory, particularly computational complexity theory. Rather than bore you with a ton of nonsense about O(1), O(n) and other propeller-head dribble, I figure I could explain it in terms everyone should be able to understand.

Hashtables, Buckets and HashCodes = Rolodex, Index Cards and Surnamescard-index

Yes, if the light hasn’t gone on yet, it will soon. Every .NET object includes a method called GetHashCode. This method returns a number that represents the identity of the object in a kind of fuzzy way. I say “fuzzy” because the hash code for a given instance of an object can be different on different platforms (xp, vista, 2003 etc) or on different bitness (64 vs 32 bit.) This method is used by hashtable to get the “surname” of an object. Instead of Index Cards, a Hashtable uses “buckets” to separate groups of objects. Any given Hashcode will naturally fall into a particular bucket as the function (result) of a high-speed optimized algorithm, much like any given surname naturally falls under a particular letter of the alphabet. Finally, it should be clear to you that using index cards [Hashtable buckets] is way faster than flicking through an unsorted folder [randomized list.]

Just like a Rolodex, the order you add names to it doesn’t dictate the order they are in as you flip through the cards sequentially, which is analogous to sending a Hashtable to out-default.

blog comments powered by Disqus

About the author

Irish, PowerShell MVP, .NET/ASP.NET/SharePoint Developer, Budding Architect. Developer. Montrealer. Opinionated. Montreal, Quebec.

Month List

Page List