Is it more efficient to use map in apex & call .get(), or use a set and call.contains()?

I ran some benchmark tests based on your two examples. I assumed going into it the difference was going to be slight and the results seem to reflect that. Based on your use case, I don't see a reason to build a map at all since you're most interested in whether the keySet of the map itself contains a value (related, you can call containsKey on a map much like contains on a set). Your most likely performance hit will be in storing all of your map values in memory and not necessarily CPU time in accessing your data structure.

A few notes on my test: I'm using a traditional for-loop so that I can traverse the data set 100,000 times. There are performance differences between this loop syntax and the map in Apex for-in loop syntax. I'm using a map with 100 mock values in it. The size of the map or set shouldn't be a factor in performance where CPU is concerned, only in heap being used. The if statements are copied from your sample code, only I'm never interested in the loop actually exiting early so the conditions are the inverse so that the loop runs all the way through. Using Map.get() shouldn't be a factor in performance where CPU is concerned, only in heap being used. The if statements are copied from your sample code, only I'm never interested in the loop actually exiting early so the conditions are the inverse so that the loop runs all the way through.

Using Map.get()
Map mockMap = new Map{
    'Land iguana' => 'Conolophus subcristatus',
    'Goliath heron' => 'Ardea goliath',
    'Pelican, great white' => 'Pelicans onocrotalus',
    'White-faced whistling duck' => 'Dendrocygna viduata',
    'Bottle-nose dolphin' => 'Tursiops truncatus',
    'Bee-eater, nubian' => 'Merops nubicus',
    'Duck, white-faced whistling' => 'Dendrocygna viduata',
    'Galapagos hawk' => 'Buteo galapagoensis',
    'Egyptian cobra' => 'Naja haje',
    'Snake, carpet' => 'Morelia spilota variegata',
    'Feral rock pigeon' => 'Columba livia',
    'Red-capped cardinal' => 'Paroaria gularis',
    'Eastern boa constrictor' => 'Acrantophis madagascariensis',
    'Eastern grey kangaroo' => 'Macropus giganteus',
    'Bear, grizzly' => 'Ursus arctos',
    'Duck, white-faced whistling' => 'Dendrocygna viduata',
    'Masked booby' => 'Sula dactylatra',
    'Squirrel, grey-footed' => 'Paraxerus cepapi',
    'Mississippi alligator' => 'Alligator mississippiensis',
    'Southern hairy-nosed wombat' => 'Lasiorhinus latifrons',
    'Squirrel, eastern fox' => 'Sciurus niger',
    'Malleefowl' => 'Leipoa ocellata',
    'Heron, giant' => 'Ardea goliath',
    'Great white pelican' => 'Pelecans onocratalus',
    'Ox, musk' => 'Ovibos moschatus',
    'Dusky gull' => 'Larus fuliginosus',
    'Black-throated butcherbird' => 'Cracticus nigrogularis',
    'African buffalo' => 'Syncerus caffer',
    'Palm squirrel' => 'Funambulus pennanti',
    'Lizard, frilled' => 'Chlamydosaurus kingii',
    'Brown capuchin' => 'Cebus apella',
    'Monitor, two-banded' => 'Varanus salvator',
    'American woodcock' => 'Scolopax minor',
    'White-winged dove' => 'Zenaida asiatica',
    'Guanaco' => 'Lama guanicoe',
    'Crowned eagle' => 'Spizaetus coronatus',
    'Long-nosed bandicoot' => 'Perameles nasuta',
    'Adouri (unidentified)' => 'unavailable',
    'Lesser flamingo' => 'Phoeniconaias minor',
    'Wagtail, african pied' => 'Motacilla aguimp',
    'Boa, malagasy ground' => 'Acrantophis madagascariensis',
    'Red and blue macaw' => 'Ara chloroptera',
    'Barbet, crested' => 'Trachyphonus vaillantii',
    'Buffalo, american' => 'Bison bison',
    'Siskin, pine' => 'Carduelis pinus',
    'Boa, columbian rainbow' => 'Epicrates cenchria maurus',
    'Cat, kaffir' => 'Felis silvestris lybica',
    'Monitor, two-banded' => 'Varanus salvator',
    'Swan, trumpeter' => 'Cygnus buccinator',
    'Tsessebe' => 'Damaliscus lunatus',
    'Mocking cliff chat' => 'Thamnolia cinnmomeiventris',
    'European shelduck' => 'Tadorna tadorna',
    'White-tailed jackrabbit' => 'Lepus townsendii',
    'Marmot, yellow-bellied' => 'Marmota flaviventris',
    'Crab (unidentified)' => 'unavailable',
    'Duiker, common' => 'Sylvicapra grimmia',
    'Hyena, spotted' => 'Crocuta crocuta',
    'Pelican, australian' => 'Pelecanus conspicillatus',
    'Bird, magnificent frigate' => 'Fregata magnificens',
    'Mexican wolf' => 'Canis lupus baileyi',
    'Emu' => 'Dromaius novaehollandiae',
    'Barking gecko' => 'Phyllurus milli',
    'Eastern indigo snake' => 'Drymarchon  couperi',
    'Salmon, sockeye' => 'Oncorhynchus nerka',
    'White-fronted bee-eater' => 'Merops bullockoides',
    'Antelope, roan' => 'Hippotragus equinus',
    'Bent-toed gecko' => 'Cyrtodactylus louisiadensis',
    'Sable antelope' => 'Hippotragus niger',
    'Tammar wallaby' => 'Macropus eugenii',
    'American badger' => 'Taxidea taxus',
    'Glider, feathertail' => 'Acrobates pygmaeus',
    'Weeper capuchin' => 'Cebus nigrovittatus',
    'Civet, small-toothed palm' => 'Arctogalidia trivirgata',
    'Coqui partridge' => 'Francolinus coqui',
    'White-lipped peccary' => 'Tayassu pecari',
    'Red-billed toucan' => 'Ramphastos tucanus',
    'Pigeon, wood' => 'Columba palumbus',
    'Cockatoo, red-breasted' => 'Eolophus roseicapillus',
    'Peacock, indian' => 'Pavo cristatus',
    'Carpet python' => 'Morelia spilota variegata',
    'Monkey, black spider' => 'Ateles paniscus',
    'Black-backed jackal' => 'Canis mesomelas',
    'Lesser mouse lemur' => 'Microcebus murinus',
    'Crested barbet' => 'Trachyphonus vaillantii',
    'North American red fox' => ' vulpes',
    'Snake (unidentified)' => 'unavailable',
    'Jackal, silver-backed' => 'Canis mesomelas',
    'Wolf, timber' => 'Canis lupus lycaon',
    'Chuckwalla' => 'Sauromalus obesus',
    'Sugar glider' => 'Petaurus breviceps',
    'Heron, green-backed' => 'Butorides striatus',
    'Blackbird, red-winged' => 'Agelaius phoeniceus',
    'Red meerkat' => 'Cynictis penicillata',
    'Wood pigeon' => 'Columba palumbus',
    'Starling, greater blue-eared' => 'Lamprotornis chalybaeus',
    'Giant otter' => 'Pteronura brasiliensis',
    'Suricate' => 'Suricata suricatta',
    'Flicker, field' => 'Colaptes campestris',
    'Red-cheeked cordon bleu' => 'Uraeginthus bengalus'
};
List commonNames = new List(mockMap.keySet());
Integer commonNamesSize = commonNames.size();
String targetName;
String name;
Integer startTime = Limits.getCpuTime();
for(Integer i = 0; i < 100000 xss=removed xss=removed xss=removed time = ' + String.valueOf(Limits.getCpuTime() - startTime));
Using Set.contains()
// Map instantiation code left out for brevity, see the code block above.
List commonNames = new List(mockMap.keySet());
Set nameSet = mockMap.keySet();
Integer commonNamesSize = commonNames.size();
String targetName;
String name;
Integer startTime = Limits.getCpuTime();
for(Integer i = 0; i < 100000; ++i) {
    name = commonNames[Math.mod(i, commonNamesSize)];
    if(!nameSet.contains(name)) {
        break;
    }
}
System.debug(' xss=removed>