<div class="gmail_quote">On Mon, Sep 19, 2011 at 23:29, Mark F. Adams <span dir="ltr"><<a href="mailto:mark.adams@columbia.edu">mark.adams@columbia.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div style="word-wrap:break-word">An alternative to a virtual function is changing the hash table code:<div><br></div><div><div>#define HASH_FACT 79943</div><div>#define HASHT(ta,x) ((unsigned long)((HASH_FACT*(unsigned long)x)%ta->tablesize))</div>
<div><br></div><div>and make HASH_FACT a variable.  Set HASH_FACT  to 1 if you want an array (and thus the index (x) is less than the table size tablesize).  The index x is one based so the hash function should modified:</div>
<div><br></div><div>#define HASHT(ta,x) ((unsigned long)((HASH_FACT*(unsigned long)(x-1))%ta->tablesize))</div><div></div></div></div></blockquote></div><br><div>This is an interesting idea. Storage is still double the array, but I think the cases where we want a dense array will generally not be so space limited.</div>
<div><br></div><div>As for very bad behavior shown earlier, I wonder if those problems were causing clustering of some sort so that the linear probing was having problems. It would be interesting for diagnostic purposes to record collision statistics.</div>