But even then, the naive solution would just be to pre-size the hash table and be careful about insertion/deletion architcture. Not to chuck it in favor of an AVL tree or whatnot.
Sometimes, a pre-sized hash table is the "best" solution, depending on context, and for some perhaps debatable value of "best." If I was doing hard real time (which is not what I generally do) and I didn't have any good idea of how much space the system would need, then I'd use a largish pre-sized table as a starting point then think about cooking up some sort of incremental growth/rehash code. Start out just using one hash table. When it gets too close to full, you allocate the bigger table and you start moving things to the larger one with each table access. To check for membership in this state, you check both tables. To add a new entry, you add to the larger table. Once you are done, you can throw away the old table. I don't do hard real time, but this is just what comes off the top of my head. (Note that table allocation might have to be done incrementally, if nulling out lots of entries would take too long.)
Yet, if you want to avoid your application occasionally freezing when the user hits a key, then isn't distinguishing worst-case scenarios good? You seem to agree with the article's claim that hash table sometimes give you an O(n) hit. Even if this happens very occasionally, aren't there situations where this could be worse than a constant O(log(N)) hit?
On the other, what keeps the hash algorithm from expanding the buckets little-by-little?