First the easy question: hashes are a kind of associative array.
The hash code can be found in hv.c in the perl distribution. The routine
HV *
Perl_newHV(pTHX)
{
register HV *hv;
register XPVHV* xhv;
hv = (HV*)NEWSV(502,0);
sv_upgrade((SV *)hv, SVt_PVHV);
xhv = (XPVHV*)SvANY(hv);
SvPOK_off(hv);
SvNOK_off(hv);
#ifndef NODEFAULT_SHAREKEYS
HvSHAREKEYS_on(hv); /* key-sharing on by default */
#endif
xhv->xhv_max = 7; /* HvMAX(hv) = 7 (start with 8 buckets
+) */
xhv->xhv_fill = 0; /* HvFILL(hv) = 0 */
xhv->xhv_pmroot = 0; /* HvPMROOT(hv) = 0 */
(void)hv_iterinit(hv); /* so each() will start off right */
return hv;
}
creates a new hash. We can see that the basic memory needed is 502 bytes and intially, 8 buckets are created.
For growing a hash as elements are added, the hashing algorithm is a one-at-a-time method. To grow the hash, I think the relevant routine is
STATIC void
S_more_he(pTHX)
{
register HE* he;
register HE* heend;
XPV *ptr;
New(54, ptr, 1008/sizeof(XPV), XPV);
ptr->xpv_pv = (char*)PL_he_arenaroot;
PL_he_arenaroot = ptr;
he = (HE*)ptr;
heend = &he[1008 / sizeof(HE) - 1];
PL_he_root = ++he;
while (he < heend) {
HeNEXT(he) = (HE*)(he + 1);
he++;
}
HeNEXT(he) = 0;
}
which looks like a linear algorithm to me.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.