Re: hash and arrays

Both are basically a way to store data. Arrays are listed in numerical order, 0.. size_of_array. You retreive an element with

my $val = $array[$number];
[download]

It is often desired to retreive the data by a name, instead of a number, so hashes are used. They are often called linked-lists in c. There are 2 lists, the keys and the values, so you can access data with $hash{$key_name}. Hashes are very convenient, but are slower. That is it in a nutshell.

I'm not really a human, but I play one on earth Remember How Lucky You Are

Comment on Re: hash and arrays Download Code

Replies are listed 'Best First'.
Re^2: hash and arrays by ikegami (Patriarch) on Nov 08, 2008 at 19:44 UTC
[Hashes] are often called linked-lists in c. Hashes aren't linked lists. Not even close. Hashes are completely different than linked lists. A hash is an array of vectors of key-value pairs. The array is indexed by a hash of the key. Hash functions return a as-unique-as-possible number for a string, but always the same number for equivalent strings. The array grows as elements are added to the hash. This keeps the vectors very short if an appropriate hashing algorithm is used. The vectors could very well be implemented as linked lists, but each list contains only the elements that hash to the same bucket (array element). Hashes are much more efficient than linked lists. Since the first step to add, delete or fetch an element from the data structure is to locate the element in the data structure, let's consider how long that takes. With a linked list, every key needs to be compared against the searched key if the element is absent ( `O(N)`* ), or half that on average if the element is present ( Avg case `O(N)`* ). With a hash, only the keys that hash to the same bucket are compared. With a properly working hashing algorithm, that should be a tiny number no matter how many elements are in the data structure. ( Avg case `O(1)`* ) * — Treats the keys length as bounded, as usual.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^2: hash and arrays
by ikegami (Patriarch) on Nov 08, 2008 at 19:44 UTC

[Hashes] are often called linked-lists in c.

Hashes aren't linked lists. Not even close.

Hashes are completely different than linked lists. A hash is an array of vectors of key-value pairs. The array is indexed by a hash of the key. Hash functions return a as-unique-as-possible number for a string, but always the same number for equivalent strings. The array grows as elements are added to the hash. This keeps the vectors very short if an appropriate hashing algorithm is used. The vectors could very well be implemented as linked lists, but each list contains only the elements that hash to the same bucket (array element).

Hashes are much more efficient than linked lists. Since the first step to add, delete or fetch an element from the data structure is to locate the element in the data structure, let's consider how long that takes. With a linked list, every key needs to be compared against the searched key if the element is absent ( O(N)* ), or half that on average if the element is present ( Avg case O(N)* ). With a hash, only the keys that hash to the same bucket are compared. With a properly working hashing algorithm, that should be a tiny number no matter how many elements are in the data structure. ( Avg case O(1)* )

* — Treats the keys length as bounded, as usual.

[reply]
[d/l]
[select]