It's not really an array, it's a hash table. When you insert an item it doesn't simply put it in a previously allocated array, but places it at the end of a linked list in the correct bucket determined by the hash. In order to check if the key has already been used the list must be traversed each time, and so insertion becomes a linear operation.