Cache misses are expensive yes. And when you have an interned string to be searched on - you always have to calculate it's hash-sum as key before looking for i

Cache misses are expensive yes. And when you have an interned string to be searched on - you always have to calculate it's hash-sum as key before looking for it in a hash-table, and you don't have to do that for a linear search (it's an interned symbol that's why). This means you might have to read one, two or more cache lines (if the cache line is 64, then it's strlen(yourstring)/8) You can't use the pointer itself as a key - either the distribution is not good, or the language would not allow you (you can't do it in Common Lisp which Erik Naggum was talking about). That calculation of the key might read one two or more cache lines - depending on how big the string is. Off course it would be better for the hash-table the smaller key is, and worse if not. And then, there are still CPUs without cache still in popular use - for example PS3's CELL SPE (spu). And one more thing - in the linear search you always read the same cache lines, while in the hash-table you have to read everytime different memory (the strings to be searched upon). But in both cases, there are instructions to prefetch, but again - you would be wasting less cache with the assoc table if you are looking a lot (e.g. you'll warm always from the begining and keep that in the L1), while for hash-table you would warm all the keys. It's really hard to compare, but I hope you get the picture.