--- a/mobile/android/base/java/org/mozilla/gecko/AddonUICache.java
+++ b/mobile/android/base/java/org/mozilla/gecko/AddonUICache.java
@@ -11,18 +11,18 @@ import android.util.Log;
 import android.view.Menu;
 import android.view.MenuItem;
 import android.view.SubMenu;
 
 import org.mozilla.gecko.util.BundleEventListener;
 import org.mozilla.gecko.util.EventCallback;
 import org.mozilla.gecko.util.GeckoBundle;
 
-import java.util.ArrayList;
-import java.util.List;
+import java.util.LinkedHashMap;
+import java.util.Map;
 
 /**
  * For certain UI items added by add-ons or other JS/Gecko code, Gecko notifies us whenever an item
  * is added, changed or removed. Since we must not miss any of these notifications and need to re-
  * member the current list of active UI items even if e.g. we're in background and our activities
  * have been destroyed, we need a class whose lifetime matches (or even exceeds) that of Gecko.
  *
  * This class fulfills this purpose - it will be initialised early during app startup and just like
@@ -50,17 +50,17 @@ public class AddonUICache implements Bun
         public boolean checked;
         public boolean enabled = true;
         public boolean visible = true;
         public int parent;
     }
 
     private static final AddonUICache instance = new AddonUICache();
 
-    private final List<MenuItemInfo> mAddonMenuItemsCache = new ArrayList<>();
+    private final Map<String, MenuItemInfo> mAddonMenuItemsCache = new LinkedHashMap<>();
     private int mAddonMenuNextID = ADDON_MENU_OFFSET;
     private Menu mMenu;
 
     private boolean mInitialized;
 
     public static AddonUICache getInstance() {
         return instance;
     }
@@ -96,21 +96,19 @@ public class AddonUICache implements Bun
                 info.checked = message.getBoolean("checked", false);
                 info.enabled = message.getBoolean("enabled", true);
                 info.visible = message.getBoolean("visible", true);
                 info.checkable = message.getBoolean("checkable", false);
                 final String parentUUID = message.getString("parent");
                 if (GECKO_TOOLS_MENU_UUID.equals(parentUUID)) {
                     info.parent = GECKO_TOOLS_MENU_ID;
                 } else if (!TextUtils.isEmpty(parentUUID)) {
-                    for (MenuItemInfo item : mAddonMenuItemsCache) {
-                        if (item.uuid.equals(parentUUID)) {
-                            info.parent = item.id;
-                            break;
-                        }
+                    MenuItemInfo parent = mAddonMenuItemsCache.get(parentUUID);
+                    if (parent != null) {
+                        info.parent = parent.id;
                     }
                 }
                 addAddonMenuItem(info);
                 break;
 
             case "Menu:Remove":
                 removeAddonMenuItem(message.getString("uuid"));
                 break;
@@ -126,17 +124,17 @@ public class AddonUICache implements Bun
      * Starts handling add-on menu items for the given {@link Menu} and also adds any
      * menu items that have already been cached.
      */
     public void onCreateOptionsMenu(Menu menu) {
         mMenu = menu;
 
         // Add add-on menu items, if any exist.
         if (mMenu != null) {
-            for (MenuItemInfo item : mAddonMenuItemsCache) {
+            for (MenuItemInfo item : mAddonMenuItemsCache.values()) {
                 addAddonMenuItemToMenu(mMenu, item);
             }
         }
     }
 
     /**
      * Clears the reference to the Menu passed in {@link AddonUICache#onCreateOptionsMenu}.
      * <p>
@@ -145,74 +143,61 @@ public class AddonUICache implements Bun
     public void onDestroyOptionsMenu() {
         mMenu = null;
     }
 
     /**
      * Adds an addon menu item/webextension browser action to the menu.
      */
     private void addAddonMenuItem(final MenuItemInfo info) {
-        mAddonMenuItemsCache.add(info);
+        mAddonMenuItemsCache.put(info.uuid, info);
 
         if (mMenu == null) {
             return;
         }
 
         addAddonMenuItemToMenu(mMenu, info);
     }
 
     /**
      * Removes an addon menu item/webextension browser action from the menu by its UUID.
      */
     private void removeAddonMenuItem(String uuid) {
-        int id = -1;
+        // Remove add-on menu item from cache, if available.
+        final MenuItemInfo item = mAddonMenuItemsCache.remove(uuid);
 
-        // Remove add-on menu item from cache, if available.
-        for (MenuItemInfo item : mAddonMenuItemsCache) {
-            if (item.uuid.equals(uuid)) {
-                id = item.id;
-                mAddonMenuItemsCache.remove(item);
-                break;
-            }
-        }
-
-        if (mMenu == null || id == -1) {
+        if (mMenu == null || item == null) {
             return;
         }
 
-        final MenuItem menuItem = mMenu.findItem(id);
+        final MenuItem menuItem = mMenu.findItem(item.id);
         if (menuItem != null) {
-            mMenu.removeItem(id);
+            mMenu.removeItem(item.id);
         }
     }
 
     /**
      * Updates the addon menu/webextension browser action with the specified UUID.
      */
     private void updateAddonMenuItem(String uuid, final GeckoBundle options) {
-        int id = -1;
-
         // Set attribute for the menu item in cache, if available
-        for (MenuItemInfo item : mAddonMenuItemsCache) {
-            if (item.uuid.equals(uuid)) {
-                id = item.id;
-                item.label = options.getString("name", item.label);
-                item.checkable = options.getBoolean("checkable", item.checkable);
-                item.checked = options.getBoolean("checked", item.checked);
-                item.enabled = options.getBoolean("enabled", item.enabled);
-                item.visible = options.getBoolean("visible", item.visible);
-                break;
-            }
+        final MenuItemInfo item = mAddonMenuItemsCache.get(uuid);
+        if (item != null) {
+            item.label = options.getString("name", item.label);
+            item.checkable = options.getBoolean("checkable", item.checkable);
+            item.checked = options.getBoolean("checked", item.checked);
+            item.enabled = options.getBoolean("enabled", item.enabled);
+            item.visible = options.getBoolean("visible", item.visible);
         }
 
-        if (mMenu == null || id == -1) {
+        if (mMenu == null || item == null) {
             return;
         }
 
-        final MenuItem menuItem = mMenu.findItem(id);
+        final MenuItem menuItem = mMenu.findItem(item.id);
         if (menuItem != null) {
             menuItem.setTitle(options.getString("name", menuItem.getTitle().toString()));
             menuItem.setCheckable(options.getBoolean("checkable", menuItem.isCheckable()));
             menuItem.setChecked(options.getBoolean("checked", menuItem.isChecked()));
             menuItem.setEnabled(options.getBoolean("enabled", menuItem.isEnabled()));
             menuItem.setVisible(options.getBoolean("visible", menuItem.isVisible()));
         }
     }