diff --git a/sdcard/fuse.cpp b/sdcard/fuse.cpp
index 77f03a9..f371901 100644
--- a/sdcard/fuse.cpp
+++ b/sdcard/fuse.cpp
@@ -281,8 +281,9 @@
     case PERM_ANDROID_DATA:
     case PERM_ANDROID_OBB:
     case PERM_ANDROID_MEDIA:
-        appid = (appid_t) (uintptr_t) hashmapGet(fuse->global->package_to_appid, node->name);
-        if (appid != 0) {
+        const auto& iter = fuse->global->package_to_appid->find(node->name);
+        if (iter != fuse->global->package_to_appid->end()) {
+            appid = iter->second;
             node->uid = multiuser_get_uid(parent->userid, appid);
         }
         break;
diff --git a/sdcard/fuse.h b/sdcard/fuse.h
index d76c664..634fbf1 100644
--- a/sdcard/fuse.h
+++ b/sdcard/fuse.h
@@ -30,14 +30,17 @@
 #include <sys/uio.h>
 #include <unistd.h>
 
+#include <map>
+#include <string>
+
 #include <cutils/fs.h>
-#include <cutils/hashmap.h>
 #include <cutils/log.h>
 #include <cutils/multiuser.h>
 #include <packagelistparser/packagelistparser.h>
 
 #include <private/android_filesystem_config.h>
 
+// TODO(b/30222003): Fix compilation with FUSE_TRACE == 1.
 #define FUSE_TRACE 0
 
 #if FUSE_TRACE
@@ -59,6 +62,16 @@
  * the largest possible data payload. */
 #define MAX_REQUEST_SIZE (sizeof(struct fuse_in_header) + sizeof(struct fuse_write_in) + MAX_WRITE)
 
+namespace {
+struct CaseInsensitiveCompare {
+    bool operator()(const std::string& lhs, const std::string& rhs) const {
+        return strcasecmp(lhs.c_str(), rhs.c_str()) < 0;
+    }
+};
+}
+
+using AppIdMap = std::map<std::string, appid_t, CaseInsensitiveCompare>;
+
 /* Permission mode for a specific node. Controls how file permissions
  * are derived for children nodes. */
 typedef enum {
@@ -135,7 +148,7 @@
     char source_path[PATH_MAX];
     char obb_path[PATH_MAX];
 
-    Hashmap* package_to_appid;
+    AppIdMap* package_to_appid;
 
     __u64 next_generation;
     struct node root;
diff --git a/sdcard/sdcard.cpp b/sdcard/sdcard.cpp
index ba63636..3d7bdc9 100644
--- a/sdcard/sdcard.cpp
+++ b/sdcard/sdcard.cpp
@@ -32,7 +32,6 @@
 #include <android-base/macros.h>
 
 #include <cutils/fs.h>
-#include <cutils/hashmap.h>
 #include <cutils/log.h>
 #include <cutils/multiuser.h>
 #include <packagelistparser/packagelistparser.h>
@@ -78,41 +77,22 @@
 /* Supplementary groups to execute with. */
 static const gid_t kGroups[1] = { AID_PACKAGE_INFO };
 
-static int str_hash(void *key) {
-    return hashmapHash(key, strlen(static_cast<const char*>(key)));
-}
-
-/* Tests if two string keys are equal ignoring case. */
-static bool str_icase_equals(void *keyA, void *keyB) {
-    return strcasecmp(static_cast<const char*>(keyA), static_cast<const char*>(keyB)) == 0;
-}
-
-static bool remove_str_to_int(void *key, void *value, void *context) {
-    Hashmap* map = static_cast<Hashmap*>(context);
-    hashmapRemove(map, key);
-    free(key);
-    return true;
-}
-
 static bool package_parse_callback(pkg_info *info, void *userdata) {
     struct fuse_global *global = (struct fuse_global *)userdata;
-
-    char* name = strdup(info->name);
-    hashmapPut(global->package_to_appid, name, (void*) (uintptr_t) info->uid);
+    bool res = global->package_to_appid->emplace(info->name, info->uid).second;
     packagelist_free(info);
-    return true;
+    return res;
 }
 
 static bool read_package_list(struct fuse_global* global) {
     pthread_mutex_lock(&global->lock);
 
-    hashmapForEach(global->package_to_appid, remove_str_to_int, global->package_to_appid);
-
+    global->package_to_appid->clear();
     bool rc = packagelist_parse(package_parse_callback, global);
     TRACE("read_package_list: found %zu packages\n",
-            hashmapSize(global->package_to_appid));
+            global->package_to_appid->size());
 
-    /* Regenerate ownership details using newly loaded mapping */
+    // Regenerate ownership details using newly loaded mapping.
     derive_permissions_recursive_locked(global->fuse_default, &global->root);
 
     pthread_mutex_unlock(&global->lock);
@@ -245,7 +225,7 @@
     memset(&handler_write, 0, sizeof(handler_write));
 
     pthread_mutex_init(&global.lock, NULL);
-    global.package_to_appid = hashmapCreate(256, str_hash, str_icase_equals);
+    global.package_to_appid = new AppIdMap;
     global.uid = uid;
     global.gid = gid;
     global.multi_user = multi_user;