Another thing we ignore in big-O analyses: as a hashtable grows arbitrarily large, the physical media in which it’s data is stored must also take up more and mo

Another thing we ignore in big-O analyses: as a hashtable grows arbitrarily large, the physical media in which it’s data is stored must also take up more and more physical space. Since we live in three-dimensional space, the retrieval time for a hashtable containing n entries must be bounded by the fact that the entries are located a distance of at least O(n^1/3) away. (Not actually purely an academic concern - this physical constraint is what drives the difference in performance between using data in L1cache, RAM, disk, or on remote networked nodes.) So yeah, O(1) hashmap reads are a convenient lie we tell ourselves, which are really only true for ‘small hashmaps’.