People thinking that hashtables or hashmaps work like magic is nonsense. It is unpredictable and varies based on the hash function. A very good hash function will have a same number of hashes as the number of input values. So in this case if your input array is filled with numbers from all over the range, you might be allocating a big amount of memory based on how your hashtable is implemented.
I try not to use hash table as much as possible, the give and illusion of constant time, but what is the benefit if that constant time is a long time. And at the same time memory consumption is not guaranteed.
I would stick with the more predictable O(n x n) solution as it is predictable and runs in a constant memory.