Какое худшее время работы метода get(key) для ключа, который есть в HashMap?

O(N). Худший случай — это поиск ключа в HashMap, вырожденного в список по причине совпадения ключей по hashCode() и для выяснения хранится ли элемент с определённым ключом может потребоваться перебор всего списка.