Looking through the FASM source code it appears to use the FNV hash algorithm and then a hash tree of depth 32. Each node in the hash tree uses 8 bytes and is potentially a cache-miss. I'm curious as to why this choice was made, and what other methods were tested?

Ideally, a hash should be a single cache miss - which easily offsets the costs of calculating the hash code. Why waste memory and time with a hash tree? Only real benefit being that it is adaptive in terms of memory use?

See this thread to see what tests were done (there were even some graphs done):
http://board.flatassembler.net/topic.php?t=854

The cache miss is just a constant coefficient, so it doesn't affect the algorithm complexity (the O() notation) - which becomes more important when dealing with so huge amounts of symbols.

So, you improved the hash function after adding the hash tree - that makes sense. Very enlightening thread, thank you.