The linear search/list is only for pending tile entities. Pending TEs are TEs that were created while processing another TE until they get flushed to the regular data structures the next tick. Due to the very temporary nature the list is usually empty and otherwise small. TE queries mostly happens via getChunkFromChunkCoords(...).func_150806_e(...) in the middle of getTileEntity(...).
There may be corner cases where the list intermittently grows to a significant size, but I don't remember having seen anything severe enough to warrant a targeted tweak.
The O(1) map lookups involved in fetching a chunk+te are usually the real problem. Mods with lots of neighbor interaction employ caches to limit the impact, the regular lookup is already optimized by Fastcraft. I however can't/don't want to add local caches to arbitrary mods. TileEntitySteamHeater could check its heaters only every n ticks, which is more powerful than anything I can do in a generic way.