[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.

In reply to Re^2: hash and arrays by ikegami
in thread hash and arrays by sandy_1028

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.