diff --git a/src/com/android/launcher3/AppInfo.java b/src/com/android/launcher3/AppInfo.java
index 9c87ced..c95d558 100644
--- a/src/com/android/launcher3/AppInfo.java
+++ b/src/com/android/launcher3/AppInfo.java
@@ -25,6 +25,7 @@
 import com.android.launcher3.compat.LauncherActivityInfoCompat;
 import com.android.launcher3.compat.UserHandleCompat;
 import com.android.launcher3.compat.UserManagerCompat;
+import com.android.launcher3.util.ComponentKey;
 
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -137,6 +138,10 @@
         return new ShortcutInfo(this);
     }
 
+    public ComponentKey toComponentKey() {
+        return new ComponentKey(componentName, user);
+    }
+
     public static Intent makeLaunchIntent(Context context, LauncherActivityInfoCompat info,
             UserHandleCompat user) {
         long serialNumber = UserManagerCompat.getInstance(context).getSerialNumberForUser(user);
diff --git a/src/com/android/launcher3/allapps/AllAppsContainerView.java b/src/com/android/launcher3/allapps/AllAppsContainerView.java
index 083e3c1..0fbe8e9 100644
--- a/src/com/android/launcher3/allapps/AllAppsContainerView.java
+++ b/src/com/android/launcher3/allapps/AllAppsContainerView.java
@@ -39,6 +39,7 @@
 import android.view.ViewTreeObserver;
 import android.widget.FrameLayout;
 import android.widget.LinearLayout;
+
 import com.android.launcher3.AppInfo;
 import com.android.launcher3.BaseContainerView;
 import com.android.launcher3.BubbleTextView;
@@ -56,6 +57,7 @@
 import com.android.launcher3.Stats;
 import com.android.launcher3.Utilities;
 import com.android.launcher3.Workspace;
+import com.android.launcher3.util.ComponentKey;
 import com.android.launcher3.util.Thunk;
 
 import java.nio.charset.Charset;
@@ -763,7 +765,7 @@
     }
 
     @Override
-    public void onSearchResult(String query, ArrayList<ComponentName> apps) {
+    public void onSearchResult(String query, ArrayList<ComponentKey> apps) {
         if (apps != null) {
             if (apps.isEmpty()) {
                 String formatStr = getResources().getString(R.string.all_apps_no_search_results);
diff --git a/src/com/android/launcher3/allapps/AllAppsSearchBarController.java b/src/com/android/launcher3/allapps/AllAppsSearchBarController.java
index 3cacd9d..341539c 100644
--- a/src/com/android/launcher3/allapps/AllAppsSearchBarController.java
+++ b/src/com/android/launcher3/allapps/AllAppsSearchBarController.java
@@ -20,6 +20,8 @@
 import android.view.View;
 import android.view.ViewGroup;
 
+import com.android.launcher3.util.ComponentKey;
+
 import java.util.ArrayList;
 
 /**
@@ -87,7 +89,7 @@
          *
          * @param apps sorted list of matching components or null if in case of failure.
          */
-        void onSearchResult(String query, ArrayList<ComponentName> apps);
+        void onSearchResult(String query, ArrayList<ComponentKey> apps);
 
         /**
          * Called when the search results should be cleared.
diff --git a/src/com/android/launcher3/allapps/AlphabeticalAppsList.java b/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
index 4f29e0c..b7b6ed7 100644
--- a/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
+++ b/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
@@ -19,12 +19,12 @@
 import android.content.Context;
 import android.support.v7.widget.RecyclerView;
 import android.util.Log;
+
 import com.android.launcher3.AppInfo;
 import com.android.launcher3.Launcher;
-import com.android.launcher3.LauncherAppState;
 import com.android.launcher3.compat.AlphabeticIndexCompat;
-import com.android.launcher3.model.AbstractUserComparator;
 import com.android.launcher3.model.AppNameComparator;
+import com.android.launcher3.util.ComponentKey;
 
 import java.util.ArrayList;
 import java.util.Collections;
@@ -148,6 +148,8 @@
 
     // The set of apps from the system not including predictions
     private final List<AppInfo> mApps = new ArrayList<>();
+    private final HashMap<ComponentKey, AppInfo> mComponentToAppMap = new HashMap<>();
+
     // The set of filtered apps with the current filter
     private List<AppInfo> mFilteredApps = new ArrayList<>();
     // The current set of adapter items
@@ -161,7 +163,7 @@
     // The set of predicted apps resolved from the component names and the current set of apps
     private List<AppInfo> mPredictedApps = new ArrayList<>();
     // The of ordered component names as a result of a search query
-    private ArrayList<ComponentName> mSearchResults;
+    private ArrayList<ComponentKey> mSearchResults;
     private HashMap<CharSequence, String> mCachedSectionNames = new HashMap<>();
     private RecyclerView.Adapter mAdapter;
     private AlphabeticIndexCompat mIndexer;
@@ -255,7 +257,7 @@
     /**
      * Sets the sorted list of filtered components.
      */
-    public void setOrderedFilter(ArrayList<ComponentName> f) {
+    public void setOrderedFilter(ArrayList<ComponentKey> f) {
         if (mSearchResults != f) {
             mSearchResults = f;
             updateAdapterItems();
@@ -283,33 +285,23 @@
      * Sets the current set of apps.
      */
     public void setApps(List<AppInfo> apps) {
-        mApps.clear();
-        mApps.addAll(apps);
-        onAppsUpdated();
+        mComponentToAppMap.clear();
+        addApps(apps);
     }
 
     /**
      * Adds new apps to the list.
      */
     public void addApps(List<AppInfo> apps) {
-        // We add it in place, in alphabetical order
-        for (AppInfo info : apps) {
-            mApps.add(info);
-        }
-        onAppsUpdated();
+        updateApps(apps);
     }
 
     /**
      * Updates existing apps in the list
      */
     public void updateApps(List<AppInfo> apps) {
-        for (AppInfo info : apps) {
-            int index = mApps.indexOf(info);
-            if (index != -1) {
-                mApps.set(index, info);
-            } else {
-                mApps.add(info);
-            }
+        for (AppInfo app : apps) {
+            mComponentToAppMap.put(app.toComponentKey(), app);
         }
         onAppsUpdated();
     }
@@ -318,36 +310,19 @@
      * Removes some apps from the list.
      */
     public void removeApps(List<AppInfo> apps) {
-        for (AppInfo info : apps) {
-            int removeIndex = findAppByComponent(mApps, info);
-            if (removeIndex != -1) {
-                mApps.remove(removeIndex);
-            }
+        for (AppInfo app : apps) {
+            mComponentToAppMap.remove(app.toComponentKey());
         }
         onAppsUpdated();
     }
 
     /**
-     * Finds the index of an app given a target AppInfo.
-     */
-    private int findAppByComponent(List<AppInfo> apps, AppInfo targetInfo) {
-        ComponentName targetComponent = targetInfo.intent.getComponent();
-        int length = apps.size();
-        for (int i = 0; i < length; ++i) {
-            AppInfo info = apps.get(i);
-            if (info.user.equals(targetInfo.user)
-                    && info.intent.getComponent().equals(targetComponent)) {
-                return i;
-            }
-        }
-        return -1;
-    }
-
-    /**
      * Updates internals when the set of apps are updated.
      */
     private void onAppsUpdated() {
         // Sort the list of apps
+        mApps.clear();
+        mApps.addAll(mComponentToAppMap.values());
         Collections.sort(mApps, mAppNameComparator.getAppInfoComparator());
 
         // As a special case for some languages (currently only Simplified Chinese), we may need to
@@ -494,33 +469,13 @@
             return mApps;
         }
 
-        int total = mSearchResults.size();
-        final HashMap<ComponentName, Integer> sortOrder = new HashMap<>(total);
-        for (int i = 0; i < total; i++) {
-            sortOrder.put(mSearchResults.get(i), i);
-        }
-
         ArrayList<AppInfo> result = new ArrayList<>();
-        for (AppInfo info : mApps) {
-            if (sortOrder.containsKey(info.componentName)) {
-                result.add(info);
+        for (ComponentKey key : mSearchResults) {
+            AppInfo match = mComponentToAppMap.get(key);
+            if (match != null) {
+                result.add(match);
             }
         }
-
-        Collections.sort(result, new AbstractUserComparator<AppInfo>(
-                LauncherAppState.getInstance().getContext()) {
-
-            @Override
-            public int compare(AppInfo lhs, AppInfo rhs) {
-                Integer indexA = sortOrder.get(lhs.componentName);
-                int result = indexA.compareTo(sortOrder.get(rhs.componentName));
-                if (result == 0) {
-                    return super.compare(lhs, rhs);
-                } else {
-                    return result;
-                }
-            }
-        });
         return result;
     }
 
diff --git a/src/com/android/launcher3/allapps/DefaultAppSearchAlgorithm.java b/src/com/android/launcher3/allapps/DefaultAppSearchAlgorithm.java
index 28854be..9ca5ccd 100644
--- a/src/com/android/launcher3/allapps/DefaultAppSearchAlgorithm.java
+++ b/src/com/android/launcher3/allapps/DefaultAppSearchAlgorithm.java
@@ -15,9 +15,10 @@
  */
 package com.android.launcher3.allapps;
 
-import android.content.ComponentName;
 import android.os.Handler;
+
 import com.android.launcher3.AppInfo;
+import com.android.launcher3.util.ComponentKey;
 
 import java.util.ArrayList;
 import java.util.List;
@@ -46,19 +47,7 @@
 
     public void doSearch(final String query,
             final AllAppsSearchBarController.Callbacks callback) {
-        // Do an intersection of the words in the query and each title, and filter out all the
-        // apps that don't match all of the words in the query.
-        final String queryTextLower = query.toLowerCase();
-        final String[] queryWords = SPLIT_PATTERN.split(queryTextLower);
-        final ArrayList<ComponentName> result = new ArrayList<>();
-        int total = mApps.size();
-
-        for (int i = 0; i < total; i++) {
-            AppInfo info = mApps.get(i);
-            if (!result.contains(info.componentName) && matches(info, queryWords)) {
-                result.add(info.componentName);
-            }
-        }
+        final ArrayList<ComponentKey> result = getTitleMatchResult(query);
         mResultHandler.post(new Runnable() {
 
             @Override
@@ -68,7 +57,22 @@
         });
     }
 
-    private boolean matches(AppInfo info, String[] queryWords) {
+    protected ArrayList<ComponentKey> getTitleMatchResult(String query) {
+        // Do an intersection of the words in the query and each title, and filter out all the
+        // apps that don't match all of the words in the query.
+        final String queryTextLower = query.toLowerCase();
+        final String[] queryWords = SPLIT_PATTERN.split(queryTextLower);
+
+        final ArrayList<ComponentKey> result = new ArrayList<>();
+        for (AppInfo info : mApps) {
+            if (matches(info, queryWords)) {
+                result.add(info.toComponentKey());
+            }
+        }
+        return result;
+    }
+
+    protected boolean matches(AppInfo info, String[] queryWords) {
         String title = info.title.toString();
         String[] words = SPLIT_PATTERN.split(title.toLowerCase());
         for (int qi = 0; qi < queryWords.length; qi++) {
@@ -87,5 +91,4 @@
         }
         return true;
     }
-
 }