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.