Hash Table

ArrayList is hashtable. For hash table, you can keep adding elements to it until the total element reach a number. And then, the size will be doubled. So the amortized insertion runtime is O(1).
Remember the hash code.