Algorithm to compare two data sets I have two data sets of a particular structure:
User 1:
  Salad1: Tuna, Mayo, Lettuce
  ...
  Breakfast1: Egg, Avocado, Toast 

User 2:
  Salad1: Tuna, Mayo
  ...
  Breakfast1: Egg, Toast, Sausage 

There are thousands of dishes, and the goal is to ensure that all the ingredients from User 1 dish are present in the corresponding recipe of User 2 data set.
We can't overwrite the recipe in User 2 data set, removing their additions - we only need to ensure that the ingredients from the corresponding User 1 dishes are present, and add them in if they are absent.
My solution:
Create a list of hashes for each recipe from each User:
Salad1|Tuna~Mayo~Lettuce
Breakfast1|Egg~Avocado~Toast

Perform a 'difference' operation on the two string arrays and end up with a list of those recipies that don't match. Break away the dish identifier from each resulting string, find the dish in the second data set and append the missing ingridient.
Benefits of my solution
As you can see, once we add the 'Lettuce' to the Salad1 recipe of User2, the relevant dish will stop coming up in the 'Difference of hashes' output, and the consequent synchronisations will take much less time.
Problems with my solution
Sadly, the Breakfast1 recipe of User2 will keep flagging up the difference even after we add the 'Toast' entry to it, because here the user has added 'Sausage' to the list.
This way, if User2 chooses to add a 'special ingridient' to each recipe we will end up evaluating every single dish in his database for having ingridients of the corresponding dish in User1 data set.
Essentially: my approach reduces the amount of individual dishes that I need to evaluate (iterate over ingridients to see if the ingridients from the User1 dataset are present), but I still need to evaluate those where extra ingridients were added.
The challenge
Is there any established algorithm that would take the two datasets above, and return only 'dishes' from the second data set that need 'ingridients' added to them?
I think you are asking about how to implement a set difference operation. Specifically, if user 1's recipe for salad 1 is viewed as a set of ingredients A, and user 2's recipe for salad 1 is viewed as a set of ingredients B, then the the set difference A \ B is exactly the set of ingredients that are in A but not in B.
One well-known and particularly simple algorithm goes like this:

Sort each list of ingredients (let's say in ascending order).
At the start, the first element of each list is the current element.
Repeatedly compare the current elements of the lists. Calling the current elements of A and B by the names a and b, respectively, there are three cases:

a &lt; b Ingredient a is in A and not in B, so make a note of it. Advance the current element for A, but keep the same current element in B.
a = b Ingredient a is in both, so nothing special need be done. Advance both current elements.
a &gt; b Ingredient b is in B and not in A. We don't need to do anything special to rectify this situation. Advance the current element in B.



When you reach the end of both sorted lists, you will have a record of the ingredients that must be added to B's recipe.
There are more complicated algorithms that exploit the fact that strings support more interesting observations than just comparison, or which can take advantage of situations where there's only a small collection of possible ingredients, but I recommend you start here until you're confident that this algorithm doesn't meet your performance needs.