built-in hash is certain the fastest.  Was concerned about its invariance and collision-resistance.  See:  http://stackoverflow.com/questions/793761/built-in-python-hash-function

But we are always feeding it a string, so I think we're ok.  
We might get collisions but your no-negative caching set will only convert a wrong answer to right.  So I think we're ok there too.