News for hackers. Stuff that matters.
Re:Problems with Hash Tables by tyler on Friday January 08, 2010 @04:28PM (#1040475)
The part I find particularly silly is where he writes:

  For example, assume that the hash table implementation
  shrinks the table if the number of full buckets drops
  below half, and grows the table if it becomes over full.
  If the table starts out with 100 buckets, and the number 
  of buckets falls to 49, the size is shrunk to 50.
I've never seen a hashtable that actually works this way. It's common knowledge that performance of hashtables degrades long before the "full" point. (I particularly like the explanation of that here: http://eigenclass.org/R2/writings/separate-chaining-vs-doubl...)
Re:Problems with Hash Tables by barrkel on Friday January 08, 2010 @09:52PM (#1040938)
However, even if you are using a load factor like .72 or so to decide to grow, such a decision is still sensitive to flip-flopping if you use a very similar boundary for shrinking.
Re:Problems with Hash Tables by ajross on Friday January 08, 2010 @10:39PM (#1040978)
And this is trivially avoided by any simple hysteresis protection scheme. Use a different factor for shrinking or growing, or a different threshold.