Given that the depth of the page table tree is fixed at 3/4/5 depending on the architecture and kernel, I think most people would be confused if asked whether the average complexity of a hash table lookup is always really O(1).

Even senior developers that understand the TLB would likely think of it as "O(1), but with a big constant factor".

On a side note, one thing that the article doesn't mention is the possibility of using a Bloom filter. It trades an extra scan of a file for smaller hash tables/smaller set to sort with external sort.