General discussion

Locked

Hashes

By troylh ·
What sets the order that the keys go into a hashes example: Read from a HTML form:

name="name"
name="email"
name="age"
name="favorite_color"

then when I get them from a hashes they come out in this order:

email, name, age, favorite_color

WHY email first? Want the name first, the email etc.

This conversation is currently closed to new comments.

5 total posts (Page 1 of 1)  
| Thread display: Collapse - | Expand +

All Comments

Collapse -

Hashes

by GeoffreyC In reply to Hashes

Unfortunately you haven't specified the language you are using the hashes in. In the current version of Perl hashes have no internal order.
To get them into the order you want you can put the hash names into an array in the order you want them and iterate over the array, retrieving the value from the hash using the array member as the key.

Collapse -

Hashes

by troylh In reply to Hashes

The question was auto-closed by TechRepublic

Collapse -

Hashes

by epepke In reply to Hashes

Hashes are implemented as hash tables, which by definition have no order, or at least none that is obvious.

Unlike trees, linked lists, ordered lists, etc., hash tables do not primarily use comparisons to find keys. They use calculations.

First, a number is calculated from the key. An old CS prof of mine said that everybody's favorite hash nunber was made by summing the ASCII values of the characters in the string. So, the key for "email" would be 'e' + 'm' + 'a' + 'i' + 'l'. Then thehash key is taken by dividing the number by the size of the hash table and taking the remainder. The key/value pair is put at that location in the array.

For all intents and purposes, the closer the order is to random, the better.

Comparisonshappen only when two keys have the same hash value. That is called a collision. There are various strategies for this. My personal favorite is the add-the-hash rehash, which produces two numbers (an initial hash key and an increment) from the key. It makes use of prime numbers to reduce collisions. Gonnet and Munro proved that this algorithm produced an average of a bit more than four comparisons for a 50% loaded hash table regardless of the size of the table.

This is the strength of a hash table: no matter how many entries you have, it remains just as fast to look up any individual entry. This is provably not true of any lookup method based primarily on comparisons, which at best grows in time as the logarithm of the number of elements.

Adding an element to a hash table is also O(k) (constant) provided that the hash table was originally big enough. If, however, the hash table is too small, it must sometimes be rehashed, which can make the average time O(log n). This is why hash tables in Java allow you to specify an initial size when creating the table. If you know beforehand approximately how many entries you will need, it's very fast.

Collapse -

Hashes

by troylh In reply to Hashes

The question was auto-closed by TechRepublic

Collapse -

Hashes

by troylh In reply to Hashes

This question was auto closed due to inactivity

Back to Web Development Forum
5 total posts (Page 1 of 1)  

Related Forums