I get the Θ(1) part is the time that uses to calculate hash table, but I don't understand the Θ(α) part.
In my view, the time complexity is Θ(n). Assume α is the expected length and the table has m slots. To ensure the key is not in the table, we need to search each slot, and each slot has α excepted length, so the total time is α times m, then it's Θ(n).
Could anyone tell me which part I didn't understand correctly?
Testing if a given key is in the hash table doesn't need to test all slots. You simply calculate the hash value for the given key (1). This hash value identifies which slot the key has to be in, if it is in the hash table. So, you simply need to compare all entries (α) in that slot with the given key, yielding Θ(1+α). You don't need to look at the other slots because the key cannot be stored in any of the other slots.