Если не знаю ключей, какие есть подходы, чтобы перебрать всю карту (HashMap) и найти значение?

Если нужен только факт наличия значения, используйте containsValue. Для получения ключа вместе со значением перебирайте entrySet; если ключи не нужны — values.

Поиск по значению обычно требует O(n), поскольку HashMap индексирует ключи, а не значения. При сравнении объектов учитывайте null, например через Objects.equals. Несколько ключей могут иметь одинаковое значение, поэтому заранее определите, нужны все совпадения или любое. Порядок обхода HashMap не гарантирован. Для частых обратных поисков может понадобиться отдельный индекс с корректным обновлением.