I remember reading a bit on how the kernel stores the hosts list, but I stopped before finding how it scales. All I remember is that it seemed like a linear list. If it was a trie it would be alright.