Hash tables All three operation can be performed in almost constant time Most frequently in practice, best choice Main idea An array of entries(called buckets), indexed by an Integer range a hash function turns the search key into an integer hash value in the index range and the item corresponding to the search key is stored in the bucket at this index The efficiency greatly depends on the design of the hash function Main problem Collision resolution: two keys are mapped to the same index by the hash function• Hash tables – All three operation can be performed in almost constant time – Most frequently in practice, best choice • Main idea – An array of entries (called buckets), indexed by an integer range – A hash function turns the search key into an integer hash value in the index range – And the item corresponding to the search key is stored in the bucket at this index – The efficiency greatly depends on the design of the hash function • Main problem – Collision resolution: two keys are mapped to the same index by the hash function