diff --git a/src/com/android/launcher3/Launcher.java b/src/com/android/launcher3/Launcher.java
index 9989abb..c418758 100644
--- a/src/com/android/launcher3/Launcher.java
+++ b/src/com/android/launcher3/Launcher.java
@@ -93,17 +93,16 @@
 import android.widget.ImageView;
 import android.widget.TextView;
 import android.widget.Toast;
-
 import com.android.launcher3.DropTarget.DragObject;
 import com.android.launcher3.PagedView.PageSwitchListener;
 import com.android.launcher3.allapps.AllAppsContainerView;
-import com.android.launcher3.allapps.AllAppsSearchBarController;
 import com.android.launcher3.compat.AppWidgetManagerCompat;
 import com.android.launcher3.compat.LauncherActivityInfoCompat;
 import com.android.launcher3.compat.LauncherAppsCompat;
 import com.android.launcher3.compat.UserHandleCompat;
 import com.android.launcher3.compat.UserManagerCompat;
 import com.android.launcher3.model.WidgetsModel;
+import com.android.launcher3.util.ComponentKey;
 import com.android.launcher3.util.LongArrayMap;
 import com.android.launcher3.util.Thunk;
 import com.android.launcher3.widget.PendingAddWidgetInfo;
@@ -3436,7 +3435,7 @@
      */
     private void tryAndUpdatePredictedApps() {
         if (mLauncherCallbacks != null) {
-            List<ComponentName> apps = mLauncherCallbacks.getPredictedApps();
+            List<ComponentKey> apps = mLauncherCallbacks.getPredictedApps();
             if (!apps.isEmpty()) {
                 mAppsView.setPredictedApps(apps);
             }
diff --git a/src/com/android/launcher3/LauncherCallbacks.java b/src/com/android/launcher3/LauncherCallbacks.java
index e732754..56db774 100644
--- a/src/com/android/launcher3/LauncherCallbacks.java
+++ b/src/com/android/launcher3/LauncherCallbacks.java
@@ -8,6 +8,7 @@
 import android.view.View;
 import android.view.ViewGroup;
 import com.android.launcher3.allapps.AllAppsSearchBarController;
+import com.android.launcher3.util.ComponentKey;
 
 import java.io.FileDescriptor;
 import java.io.PrintWriter;
@@ -92,7 +93,7 @@
     public boolean overrideWallpaperDimensions();
     public boolean isLauncherPreinstalled();
     public AllAppsSearchBarController getAllAppsSearchBarController();
-    public List<ComponentName> getPredictedApps();
+    public List<ComponentKey> getPredictedApps();
 
     /**
      * Returning true will immediately result in a call to {@link #setLauncherOverlayView(ViewGroup,
diff --git a/src/com/android/launcher3/LauncherExtension.java b/src/com/android/launcher3/LauncherExtension.java
index fafb070..857ec57 100644
--- a/src/com/android/launcher3/LauncherExtension.java
+++ b/src/com/android/launcher3/LauncherExtension.java
@@ -12,6 +12,7 @@
 import android.view.View;
 import android.view.ViewGroup;
 import com.android.launcher3.allapps.AllAppsSearchBarController;
+import com.android.launcher3.util.ComponentKey;
 
 import java.io.FileDescriptor;
 import java.io.PrintWriter;
@@ -253,7 +254,7 @@
         }
 
         @Override
-        public List<ComponentName> getPredictedApps() {
+        public List<ComponentKey> getPredictedApps() {
             return new ArrayList<>();
         }
 
diff --git a/src/com/android/launcher3/allapps/AllAppsContainerView.java b/src/com/android/launcher3/allapps/AllAppsContainerView.java
index 0fbe8e9..d49a06b 100644
--- a/src/com/android/launcher3/allapps/AllAppsContainerView.java
+++ b/src/com/android/launcher3/allapps/AllAppsContainerView.java
@@ -207,7 +207,7 @@
     /**
      * Sets the current set of predicted apps.
      */
-    public void setPredictedApps(List<ComponentName> apps) {
+    public void setPredictedApps(List<ComponentKey> apps) {
         mApps.setPredictedApps(apps);
     }
 
diff --git a/src/com/android/launcher3/allapps/AlphabeticalAppsList.java b/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
index b7b6ed7..aa73c74 100644
--- a/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
+++ b/src/com/android/launcher3/allapps/AlphabeticalAppsList.java
@@ -15,14 +15,14 @@
  */
 package com.android.launcher3.allapps;
 
-import android.content.ComponentName;
 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.compat.UserHandleCompat;
 import com.android.launcher3.model.AppNameComparator;
 import com.android.launcher3.util.ComponentKey;
 
@@ -159,7 +159,7 @@
     // The set of sections that we allow fast-scrolling to (includes non-merged sections)
     private List<FastScrollSectionInfo> mFastScrollerSections = new ArrayList<>();
     // The set of predicted app component names
-    private List<ComponentName> mPredictedAppComponents = new ArrayList<>();
+    private List<ComponentKey> mPredictedAppComponents = new ArrayList<>();
     // 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
@@ -268,7 +268,7 @@
      * Sets the current set of predicted apps.  Since this can be called before we get the full set
      * of applications, we should merge the results only in onAppsUpdated() which is idempotent.
      */
-    public void setPredictedApps(List<ComponentName> apps) {
+    public void setPredictedApps(List<ComponentKey> apps) {
         mPredictedAppComponents.clear();
         mPredictedAppComponents.addAll(apps);
         onAppsUpdated();
@@ -386,21 +386,27 @@
 
         if (DEBUG_PREDICTIONS) {
             if (mPredictedAppComponents.isEmpty() && !mApps.isEmpty()) {
-                mPredictedAppComponents.add(mApps.get(0).componentName);
-                mPredictedAppComponents.add(mApps.get(0).componentName);
-                mPredictedAppComponents.add(mApps.get(0).componentName);
-                mPredictedAppComponents.add(mApps.get(0).componentName);
+                mPredictedAppComponents.add(new ComponentKey(mApps.get(0).componentName,
+                        UserHandleCompat.myUserHandle()));
+                mPredictedAppComponents.add(new ComponentKey(mApps.get(0).componentName,
+                        UserHandleCompat.myUserHandle()));
+                mPredictedAppComponents.add(new ComponentKey(mApps.get(0).componentName,
+                        UserHandleCompat.myUserHandle()));
+                mPredictedAppComponents.add(new ComponentKey(mApps.get(0).componentName,
+                        UserHandleCompat.myUserHandle()));
             }
         }
 
         // Process the predicted app components
         mPredictedApps.clear();
         if (mPredictedAppComponents != null && !mPredictedAppComponents.isEmpty() && !hasFilter()) {
-            for (ComponentName cn : mPredictedAppComponents) {
-                for (AppInfo info : mApps) {
-                    if (cn.equals(info.componentName)) {
-                        mPredictedApps.add(info);
-                        break;
+            for (ComponentKey ck : mPredictedAppComponents) {
+                AppInfo info = mComponentToAppMap.get(ck);
+                if (info != null) {
+                    mPredictedApps.add(info);
+                } else {
+                    if (LauncherAppState.isDogfoodBuild()) {
+                        Log.e(TAG, "Predicted app not found: " + ck.flattenToString(mLauncher));
                     }
                 }
                 // Stop at the number of predicted apps
diff --git a/src/com/android/launcher3/util/ComponentKey.java b/src/com/android/launcher3/util/ComponentKey.java
index 0f17f00..6a7df43 100644
--- a/src/com/android/launcher3/util/ComponentKey.java
+++ b/src/com/android/launcher3/util/ComponentKey.java
@@ -17,8 +17,9 @@
  */
 
 import android.content.ComponentName;
-
+import android.content.Context;
 import com.android.launcher3.compat.UserHandleCompat;
+import com.android.launcher3.compat.UserManagerCompat;
 
 import java.util.Arrays;
 
@@ -38,6 +39,35 @@
 
     }
 
+    /**
+     * Creates a new component key from an encoded component key string in the form of
+     * [flattenedComponentString#userId].  If the userId is not present, then it defaults
+     * to the current user.
+     */
+    public ComponentKey(Context context, String componentKeyStr) {
+        int userDelimiterIndex = componentKeyStr.indexOf("#");
+        if (userDelimiterIndex != -1) {
+            String componentStr = componentKeyStr.substring(0, userDelimiterIndex);
+            Long componentUser = Long.valueOf(componentKeyStr.substring(userDelimiterIndex + 1));
+            componentName = ComponentName.unflattenFromString(componentStr);
+            user = UserManagerCompat.getInstance(context)
+                    .getUserForSerialNumber(componentUser.longValue());
+        } else {
+            // No user provided, default to the current user
+            componentName = ComponentName.unflattenFromString(componentKeyStr);
+            user = UserHandleCompat.myUserHandle();
+        }
+        mHashCode = Arrays.hashCode(new Object[] {componentName, user});
+    }
+
+    /**
+     * Encodes a component key as a string of the form [flattenedComponentString#userId].
+     */
+    public String flattenToString(Context context) {
+        return componentName.flattenToString() + "#" +
+                UserManagerCompat.getInstance(context).getSerialNumberForUser(user);
+    }
+
     @Override
     public int hashCode() {
         return mHashCode;