В среднем O(1). В худшем случае при множестве коллизий - O(n) по количеству элементов в цепочке. На практике хеш-функция и рост таблицы дают почти константное время доступа.