How do OS's handle /etc/hosts algorithmically?

Question

I have a huge /etc/hosts file with 18,000 lines. I use it to block adservers and such. My browsing performance seems to be fine, but I wonder if there's some size at which I'll start slowing myself down? How do OS's store the hosts file during operation? I can think of lots of ways, from slow to fast, and my a priori assumption is that it is handled efficiently since it is so central to networking. Here are some ways I can think of from simple to more complex:

• Read from file each time it's needed.
• Read once
  • linear search
  • sort, then binary search
  • use a trie
  • use a hash, but how does it minimize collisions

There's lots of ways that seem reasonable. What's actually used?

It seems like this question must have been answered somewhere, so pointers to an existing resource are welcome. I did look, but maybe not in the right place.

Answer 1

You should tell what OS you are using but anyway, a usual method to improve name resolution performance with Unix and Unix-like system is to use a daemon (commonly nscd) which caches positive and negative resolutions and quickly answers most requests. When /etc/hosts is modified, at least under Solaris, this cache is invalidated.