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

Question

Prelude

I did a couple of interwebs searches, and I used the following search terms here on SFSE...

apex map get set contains
apex map vs set
apex map set efficien*

...then looked through a number of Qs & As and some links within some of the As. If I missed the answer, please forgive and point me to it.

---

Background

I know just enough of Apex and other coding to be dangerous. Adhering to best practices as much as possible is preferable, but I don't know all the best practices. I also know that some debates are akin to "Toilet paper over or under?", in that there are lots of opinions but not often is there a real better answer. (There is a correct answer to the toilet paper question, btw.)

Item at hand

I was sent an Apex class with an invocable method which a different team had created and our team needs to use. One bit of functionality that it was supposed to be doing was not working as stated, and some parts seemed to me that they could use some improvement. So I modified the code, and it was sent back to the code owners for their consideration. They kept most of my changes, but a blanket statement was made that I want to know whether it is true. Not (necessarily) so that I can say that I am correct (if I am), but just to know as part of the aforementioned best practices.

Statement

Maps are more efficient [than Sets] when doing a lookup.

---

Question

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

---

Code Comparison

Showing only the pertinent code (and changing names to protect the [not so] innocent), here is the original:

List<Group> groups = [SELECT Id, Name FROM Group WHERE Name LIKE :queryString];
Map<String, Group> groupMap = new Map<String, Group>();

for (Group g: groups) {
    groupMap.put(g.Name, g);
}

Group targetGroup;
String targetGroupName;

for (...) {
    targetGroupName = <something different every loop iteration>
    targetGroup = groupMap.get(targetGroupName);
    if(targetGroup != null){
        // Found the only one we're looking for, so set the output
        break;
    }
}

My suggested changes:

List<Group> groups = [SELECT Name FROM Group WHERE Name LIKE :queryString];
Set<String> groupNameSet = new Set<String>();

for (Group g: groups) {
    groupNameSet.add(g.Name);
}

String targetGroupName;

for (...) {
    targetGroupName = <something different every loop iteration>
    if (groupNameSet.contains(targetGroupName)) 
        // Found the only one we're looking for, so set the output
        break;
    }
}

---

UPDATES

After the first three answers, I just have to say that I love y'all here at SFSE.

2021.11.12 Normally I would choose an answer, because I don't like seeing questions with answers that clearly do answer the question and one is not accepted. However, all four of these answers are awesome, and helpful, and each contributes something different from the others. So if y'all don't mind, I'm not going to accept just one.

Answer 1

In pretty much every concievable scenario, the number of records (or data in general) that we can work with in Salesforce in a single transaction means that any difference between approaches is likely to be immeasurable.

Things like this (using a set vs using a map) is something I would say falls under the category of micro-optimization. Micro-optimizations are a waste of time (to be clear, this is aimed at the performance assertion of this other team). If you are looking to optimize something, you should do two things:

1. Define a specific thing to be improved that can be measured (requests per second, heap space, cpu time, # of queries, etc...)
2. Measure that thing before your change, make your change, then measure it again

Personally, given the information you've provided, I'd prefer using a Set here because it requires less typing.

Ok, but for real, which is faster?

My gut says the Set approach, and I think it'd take less heap space too. This should be a fairly simple thing to test, just a bit tedious to set up.

Here's my anon apex:

DateTime beforeDTControl, beforeDT1, beforeDT2, afterDTControl, afterDT1, afterDT2;
Long dtControl;
Integer beforeCPUControl, beforeCPU1, beforeCPU2, afterCPUControl, afterCPU1, afterCPU2, cpuControl;
Integer beforeHeap1, beforeHeap2, afterHeap1, afterHeap2;

Integer iterations = 100000;

// Set up benchmark data
Map<String, Account> acctMap = new Map<String, Account>();
Set<String> acctNameSet = new Set<String>();
List<Integer> randomIndex = new List<Integer>();
Long heapBefore = Limits.getHeapSize();
for(Integer i = 0; i < iterations; i++){    
    String name = 'testAcct' + i;
    acctMap.put(name, new Account(Name = name));
    randomIndex.add((Math.random() * 499).intValue());
}
Long heapAfter = Limits.getHeapSize();
acctNameSet = acctMap.keySet();
Long heapAfter2 = Limits.getHeapSize();

system.debug(heapAfter - heapBefore);
system.debug(heapAfter2 - heapAfter);
Set<String> randomNamesSet = new Set<String>();
for(Integer i = 0; i < 500; i++){
    Integer rand = (Math.random() * 10000000).intValue();
    randomNamesSet.add('testAcct' + rand);
}
List<String> randomNamesList = new List<String>(randomNamesSet);

// Timing our common loop so that we can remove its effect on the results
beforeDTControl = DateTime.now();
beforeCPUControl = Limits.getCpuTime();
for(Integer i = 0; i < iterations; i++){
    String name = randomNamesList[randomIndex[i]];
}
afterCPUControl = Limits.getCpuTime();
afterDTControl = DateTime.now();

dtControl = afterDTControl.getTime() - beforeDTControl.getTime();
cpuControl = afterCPUControl - beforeCPUControl;

beforeDT1 = DateTime.now();
beforeCPU1 = Limits.getCpuTime();
for(Integer i = 0; i < iterations; i++){
    String name = randomNamesList[randomIndex[i]];
    Account acct = acctMap.get(name);
    Boolean contained = acct != null;
}
afterCPU1 = Limits.getCpuTime();
afterDT1 = DateTime.now();

beforeDT2 = DateTime.now();
beforeCPU2 = Limits.getCpuTime();
for(Integer i = 0; i < iterations; i++){
    String name = randomNamesList[randomIndex[i]];
    Boolean contained = acctNameSet.contains(name);
}
afterCPU2 = Limits.getCpuTime();
afterDT2 = DateTime.now();
    
system.debug(String.format('map.get approach:\nClock Time elapsed: {0}\nCPU Time used: {1}', new List<String>{
    String.valueOf(afterDT1.getTime() - beforeDT1.getTime() - dtControl),
    String.valueOf(afterCPU1 - beforeCPU1 - cpuControl)
}));
             
system.debug(String.format('set.contains approach:\nReal Time elapsed: {0}\nCPU Time used: {1}', new List<String>{
    String.valueOf(afterDT2.getTime() - beforeDT2.getTime() - dtControl),
    String.valueOf(afterCPU2 - beforeCPU2 - cpuControl)
}));

The results of 5 runs (100k operations) are as follows:

-	run 1	run 2	run 3	run 4	run 5
map.get()	315ms clock, 297 CPU	354ms clock, 279 CPU	280ms clock, 257 CPU	355ms clock, 275 CPU	302ms clock, 294 CPU
set.contains()	346ms clock, 274 CPU	391ms clock, 312 CPU	230ms clock, 231 CPU	292ms clock, 274 CPU	338ms clock, 257 CPU

Conclusion

The run-to-run variance within each approach is on par with the difference between them, so there is no significant performance difference between the two approaches.

I was slightly kind to the map.get() approach in my measured runs by having the .get() and the comparison to null evaluated in a single expression (saving one assignment operation), but this difference is insignificant.

In either approach, you're looking at a cost of around 0.00275 CPU units per call. Like I said, this is a micro-optimization. The biggest difference here would be in characters typed.

The Set approach also takes less heap space (since you aren't storing the value as well as the key like you are with the Map approach). The Set approach takes roughly 57% of the heap space that the Map approach does in my test, and that would likely be even more in favor of the Set approach in real usage. Even if your query returns a single field, you automatically get the Id (and recordTypeId if you have a custom record type for the object).

Answer 2

I'd come at this from a different direction. I don't think the performance aspect is that interesting - it essentially falls into Premature Optimization and I presume the difference is negligible between the two methods.

sfdcfox has a good answer here that compares, not your situation, but containsKey() and get() within Map and makes the following statement

If you write code that ever only uses containsKey and doesn't use get, you should be using a Set, not a Map

It seems your code falls into the above as, from what you showed:

• it seems to be using get() to accomplish the same thing as containsKey()
• never uses the value of the map it stores except to check if it exists

Why bother with the storing a map/value if it's not going to be used? Not to mention the extra variable initialized to store the map's value to check if it's null. Technically, you could get rid of storing the value from the get() like so

if((groupMap.get(targetGroupName) != null)){

}

But, the point remains, there doesn't seem to be a use case for a map if you're not going to use the value. Those are the kinds of details/decisions you can bring up in discussions that are easier to grasp (less heap, confusing to readers, etc) rather than necessarily running large performance tests and arguing milliseconds if performance isn't already the concern.

The last interesting aspect, that I hinted above, is readability which I believe is more important in these types of reviews/questions. What is more readable? Different teams may come to different conclusions - but, I'd argue a contains() in Set or containsKey() in Map makes more sense if that's the only purpose you're doing (checking if it exists) versus a Map.get() which tends to imply you'll be utilizing whatever you're getting.

Answer 3

The important thing isn't which method you use, but rather how many times you use them. All of the methods (get/put/add/remove/contains/containsAll) all essentially have to call a method to identify the correct "slot" first. That looks something like this:

Map<Integer, List<Object>> internalStorage = new Map<Integer, List<Object>>();
public Object findObject(Object source) {
  Integer hashCode = source.hashCode();
  if(!internalStorage.containsKey(hashCode)) {
    internalStorage.put(hashCode, new List<Object>());
  }
  Object[] possibleMatches = internalStorage.get(hashCode);
  for(Object possibleMatch: possibleMatches) {
    if(possibleMatch.equals(source)) {
      return possibleMatch;
    }
  }
  return null;
}

Obviously, it is not written like this literally, but you can imagine that's how it works. The actual implementation is, I believe, a b-tree structure, meaning that it uses O(log(2)) search time efficiency.

It takes longer for every power of two storage of hash codes (2, 4, 8, 16, 32, etc), meaning it can handle searching and storing hashes very efficiently exponentially better than using a List. And, of course, there's two different versions of this method; one for just searching (e.g. returns early if no hashCode is found) and one for storing potentially new values.

It first calls .hashCode, sees if there's an existing "bucket"; if not, a new one is created. Then for each item in the bucket, we call .equals to find a match.

This process can be expensive. Therefore, it is safe to say that calling .containsKey and .get is twice as expensive as just .get, whatever that means based on the incoming data.

So, given that, both versions are essentially the same, as far as performance is concerned. However, note that the Map will, by definition, use more Heap (memory) than just a Set, since you need to store the key and value.

In other words, I'd choose the Set if it makes sense, which it appears to. Heap is very easy to run out of, even compared to CPU time, so if you can save significant amount of bytes, I'd go for it. Also, you might be interested in reading more about heap, which I like to talk about time, and time, and time again (and probably more, I love speaking geek and technical details when I can).

Answer 4

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:

1. 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 Apex for-in loop syntax.
2. 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.
3. 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<String, String> mockMap = new Map<String, String>{
    'Land iguana' => 'Conolophus subcristatus',
    'Goliath heron' => 'Ardea golieth',
    'Pelican, great white' => 'Pelecans onocratalus',
    '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 spilotes 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 golieth',
    'Great white pelican' => 'Pelecans onocratalus',
    'Ox, musk' => 'Ovibos moschatus',
    'Dusky gull' => 'Larus fuliginosus',
    'Black-throated butcher bird' => 'Cracticus nigroagularis',
    'African buffalo' => 'Snycerus caffer',
    'Palm squirrel' => 'Funambulus pennati',
    '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 cliffchat' => 'Thamnolaea cinnmomeiventris',
    'European shelduck' => 'Tadorna tadorna',
    'White-tailed jackrabbit' => 'Lepus townsendii',
    'Marmot, yellow-bellied' => 'Marmota flaviventris',
    'Crab (unidentified)' => 'unavailable',
    'Duiker, common' => 'Sylvicapra grimma',
    'Hyena, spotted' => 'Crocuta crocuta',
    'Pelican, australian' => 'Pelecanus conspicillatus',
    'Bird, magnificent frigate' => 'Fregata magnificans',
    'Mexican wolf' => 'Canis lupus baileyi',
    'Emu' => 'Dromaeus novaehollandiae',
    'Barking gecko' => 'Phylurus milli',
    'Eastern indigo snake' => 'Drymarchon corias 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 nigrivittatus',
    '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 spilotes 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 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 campestroides',
    'Red-cheeked cordon bleu' => 'Uraeginthus bengalus'
};

List<String> commonNames = new List<String>(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)];
    targetName = mockMap.get(name);
    
    if(targetName == null) {
        break;
    }
}

System.debug('Elapsed CPU time = ' + String.valueOf(Limits.getCpuTime() - startTime));

Using Set.contains()

// Map instantiation code left out for brevity, see the code block above.

List<String> commonNames = new List<String>(mockMap.keySet());
Set<String> 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('Elapsed CPU time = ' + String.valueOf(Limits.getCpuTime() - startTime));

Results

These code blocks were run in execute anonymous 5 times each.

╔═════╦════════════╦══════════╗
║ Run ║ Map (ms)   ║ Set (ms) ║
╠═════╬════════════╬══════════╣
║ 1   ║       1,238║     1,234║
║ 2   ║       1,344║     1,314║
║ 3   ║       1,267║     1,277║
║ 4   ║       1,481║     1,242║
║ 5   ║       1,376║     1,414║
╠═════╬════════════╬══════════╣
║ Avg ║       1,341║     1,296║
╚═════╩════════════╩══════════╝

Set.contains() wins by about 45ms.