--- a/toolkit/components/url-classifier/Entries.h
+++ b/toolkit/components/url-classifier/Entries.h
@@ -313,17 +313,16 @@ WriteTArray(nsIOutputStream* aStream, ns
                         aArray.Length() * sizeof(T),
                         &written);
 }
 
 typedef nsClassHashtable<nsUint32HashKey, nsCString> PrefixStringMap;
 
 typedef nsDataHashtable<nsCStringHashKey, int64_t> TableFreshnessMap;
 
-typedef nsCStringHashKey VLHashPrefixString;
 typedef nsCStringHashKey FullHashString;
 
 typedef nsDataHashtable<FullHashString, int64_t> FullHashExpiryCache;
 
 struct CachedFullHashResponse {
   int64_t negativeCacheExpirySec;
 
   // Map contains all matches found in Fullhash response, this field might be empty.
@@ -349,14 +348,14 @@ struct CachedFullHashResponse {
       if (iter.Data() != aOther.fullHashes.Get(iter.Key())) {
         return false;
       }
     }
     return true;
   }
 };
 
-typedef nsClassHashtable<VLHashPrefixString, CachedFullHashResponse> FullHashResponseMap;
+typedef nsClassHashtable<nsUint32HashKey, CachedFullHashResponse> FullHashResponseMap;
 
 } // namespace safebrowsing
 } // namespace mozilla
 
 #endif // SBEntries_h__

--- a/toolkit/components/url-classifier/HashStore.cpp
+++ b/toolkit/components/url-classifier/HashStore.cpp
@@ -189,21 +189,21 @@ TableUpdateV4::NewRemovalIndices(const u
 
 void
 TableUpdateV4::NewChecksum(const std::string& aChecksum)
 {
   mChecksum.Assign(aChecksum.data(), aChecksum.size());
 }
 
 nsresult
-TableUpdateV4::NewFullHashResponse(const nsACString& aPrefix,
+TableUpdateV4::NewFullHashResponse(const Prefix& aPrefix,
                                    CachedFullHashResponse& aResponse)
 {
   CachedFullHashResponse* response =
-    mFullHashResponseMap.LookupOrAdd(aPrefix);
+    mFullHashResponseMap.LookupOrAdd(aPrefix.ToUint32());
   if (!response) {
     return NS_ERROR_OUT_OF_MEMORY;
   }
   *response = aResponse;
   return NS_OK;
 }
 
 HashStore::HashStore(const nsACString& aTableName,

--- a/toolkit/components/url-classifier/HashStore.h
+++ b/toolkit/components/url-classifier/HashStore.h
@@ -174,17 +174,17 @@ public:
   // For downcasting.
   static const int TAG = 4;
 
   void SetFullUpdate(bool aIsFullUpdate) { mFullUpdate = aIsFullUpdate; }
   void NewPrefixes(int32_t aSize, std::string& aPrefixes);
   void NewRemovalIndices(const uint32_t* aIndices, size_t aNumOfIndices);
   void SetNewClientState(const nsACString& aState) { mClientState = aState; }
   void NewChecksum(const std::string& aChecksum);
-  nsresult NewFullHashResponse(const nsACString& aPrefix,
+  nsresult NewFullHashResponse(const Prefix& aPrefix,
                                CachedFullHashResponse& aResponse);
 
 private:
   virtual int Tag() const override { return TAG; }
 
   bool mFullUpdate;
   PrefixStdStringMap mPrefixesMap;
   RemovalIndiceArray mRemovalIndiceArray;

--- a/toolkit/components/url-classifier/LookupCache.h
+++ b/toolkit/components/url-classifier/LookupCache.h
@@ -114,49 +114,51 @@ public:
 
   template<typename T>
   static T* Cast(CacheResult* aThat) {
     return ((aThat && T::VER == aThat->Ver()) ?
       reinterpret_cast<T*>(aThat) : nullptr);
   }
 
   nsCString table;
+  Prefix prefix;
 };
 
 class CacheResultV2 final : public CacheResult
 {
 public:
   static const int VER;
 
   Completion completion;
   uint32_t addChunk;
 
   bool operator==(const CacheResultV2& aOther) const {
     return table == aOther.table &&
+           prefix == aOther.prefix &&
            completion == aOther.completion &&
            addChunk == aOther.addChunk;
   }
 
   bool findCompletion(const Completion& aCompletion) const override {
     return completion == aCompletion;
   }
 
   virtual int Ver() const override { return VER; }
 };
 
 class CacheResultV4 final : public CacheResult
 {
 public:
   static const int VER;
 
-  nsCString prefix;
   CachedFullHashResponse response;
 
   bool operator==(const CacheResultV4& aOther) const {
-    return prefix == aOther.prefix &&
+    return table == aOther.table &&
+           prefix == aOther.prefix &&
            response == aOther.response;
   }
 
   bool findCompletion(const Completion& aCompletion) const override {
     nsDependentCSubstring completion(
       reinterpret_cast<const char*>(aCompletion.buf), COMPLETE_SIZE);
     return response.fullHashes.Contains(completion);
   }

--- a/toolkit/components/url-classifier/LookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/LookupCacheV4.cpp
@@ -107,19 +107,18 @@ LookupCacheV4::Has(const Completion& aCo
   }
 
   // Check if fullhash match any prefix in the local database
   if (!(*aHas)) {
     return NS_OK;
   }
 
   // We always send 4-bytes for completion(Bug 1323953) so the prefix used to
-  // lookup for cache should be 4-bytes too.
-  nsDependentCSubstring prefix(reinterpret_cast<const char*>(aCompletion.buf),
-                               PREFIX_SIZE);
+  // lookup for cache should be 4-bytes(uint32_t) too.
+  uint32_t prefix = aCompletion.ToUint32();
 
   // Check if prefix can be found in cache.
   CachedFullHashResponse* fullHashResponse = mCache.Get(prefix);
   if (!fullHashResponse) {
     return NS_OK;
   }
 
   *aFromCache = true;
@@ -658,22 +657,19 @@ nsCString GetFormattedTimeString(int64_t
 void
 LookupCacheV4::DumpCache()
 {
   if (!LOG_ENABLED()) {
     return;
   }
 
   for (auto iter = mCache.ConstIter(); !iter.Done(); iter.Next()) {
-    nsAutoCString strPrefix;
-    CStringToHexString(iter.Key(), strPrefix);
-
     CachedFullHashResponse* response = iter.Data();
-    LOG(("Caches prefix: %s, Expire time: %s",
-         strPrefix.get(),
+    LOG(("Caches prefix: %X, Expire time: %s",
+         iter.Key(),
          GetFormattedTimeString(response->negativeCacheExpirySec).get()));
 
     FullHashExpiryCache& fullHashes = response->fullHashes;
     for (auto iter2 = fullHashes.ConstIter(); !iter2.Done(); iter2.Next()) {
       nsAutoCString strFullhash;
       CStringToHexString(iter2.Key(), strFullhash);
       LOG(("  - %s, Expire time: %s", strFullhash.get(),
            GetFormattedTimeString(iter2.Data()).get()));

--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ -1191,16 +1191,17 @@ nsUrlClassifierLookupCallback::Completio
   LOG(("nsUrlClassifierLookupCallback::Completion [%p, %s, %d]",
        this, PromiseFlatCString(aTableName).get(), aChunkId));
 
   MOZ_ASSERT(!StringEndsWith(aTableName, NS_LITERAL_CSTRING("-proto")));
 
   auto result = new CacheResultV2;
 
   result->table = aTableName;
+  result->prefix.Assign(aCompleteHash);
   result->completion.Assign(aCompleteHash);
   result->addChunk = aChunkId;
 
   return ProcessComplete(result);
 }
 
 NS_IMETHODIMP
 nsUrlClassifierLookupCallback::CompletionV4(const nsACString& aPartialHash,
@@ -1223,17 +1224,17 @@ nsUrlClassifierLookupCallback::Completio
     aNegativeCacheDuration = MAXIMUM_NEGATIVE_CACHE_DURATION_SEC;
   }
 
   auto result = new CacheResultV4;
 
   int64_t nowSec = PR_Now() / PR_USEC_PER_SEC;
 
   result->table = aTableName;
-  result->prefix = aPartialHash;
+  result->prefix.Assign(aPartialHash);
   result->response.negativeCacheExpirySec = nowSec + aNegativeCacheDuration;
 
   // Fill in positive cache entries.
   uint32_t fullHashCount = 0;
   nsresult rv = aFullHashes->GetLength(&fullHashCount);
   if (NS_FAILED(rv)) {
     return rv;
   }

--- a/toolkit/components/url-classifier/tests/gtest/TestCachingV4.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/TestCachingV4.cpp
@@ -9,18 +9,22 @@
 
 static void
 SetupCacheEntry(LookupCacheV4* aLookupCache,
                 const nsCString& aCompletion,
                 bool aNegExpired = false,
                 bool aPosExpired = false)
 {
   FullHashResponseMap map;
-  CachedFullHashResponse* response = map.LookupOrAdd(
-    GeneratePrefix(aCompletion, PREFIX_SIZE));
+
+  Prefix prefix;
+  nsCOMPtr<nsICryptoHash> cryptoHash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
+  prefix.FromPlaintext(aCompletion, cryptoHash);
+
+  CachedFullHashResponse* response = map.LookupOrAdd(prefix.ToUint32());
 
   response->negativeCacheExpirySec = aNegExpired ? EXPIRED_TIME_SEC : NOTEXPIRED_TIME_SEC;
   response->fullHashes.Put(GeneratePrefix(aCompletion, COMPLETE_SIZE),
                            aPosExpired ? EXPIRED_TIME_SEC : NOTEXPIRED_TIME_SEC);
 
   aLookupCache->AddFullHashResponseToCache(map);
 }
 
@@ -193,40 +197,24 @@ TEST(CachingV4, InvalidateExpiredCacheEn
 // and it doesn't have any postive cache entries in it, it should be removed
 // from cache after calling |Has|.
 TEST(CachingV4, NegativeCacheExpire)
 {
   _PrefixArray array = { GeneratePrefix(NEG_CACHE_EXPIRED_URL, 8) };
   UniquePtr<LookupCacheV4> cache = SetupLookupCacheV4(array);
 
   FullHashResponseMap map;
-  CachedFullHashResponse* response = map.LookupOrAdd(
-    GeneratePrefix(NEG_CACHE_EXPIRED_URL, PREFIX_SIZE));
+  Prefix prefix;
+  nsCOMPtr<nsICryptoHash> cryptoHash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
+  prefix.FromPlaintext(NEG_CACHE_EXPIRED_URL, cryptoHash);
+  CachedFullHashResponse* response = map.LookupOrAdd(prefix.ToUint32());
 
   response->negativeCacheExpirySec = EXPIRED_TIME_SEC;
 
   cache->AddFullHashResponseToCache(map);
 
   // The first time we should found it in the cache but the result is not
   // confirmed(because it is expired).
   TestCache(NEG_CACHE_EXPIRED_URL, true, false, true, cache.get());
 
   // The second time it should not be found in the cache again
   TestCache(NEG_CACHE_EXPIRED_URL, true, false, false, cache.get());
 }
-
-// This testcase check we only lookup cache with 4-bytes prefix
-TEST(CachingV4, Ensure4BytesLookup)
-{
-  _PrefixArray array = { GeneratePrefix(CACHED_URL, 8) };
-  UniquePtr<LookupCacheV4> cache = SetupLookupCacheV4(array);
-
-  FullHashResponseMap map;
-  CachedFullHashResponse* response = map.LookupOrAdd(
-    GeneratePrefix(CACHED_URL, 5));
-
-  response->negativeCacheExpirySec = NOTEXPIRED_TIME_SEC;
-  response->fullHashes.Put(GeneratePrefix(CACHED_URL, COMPLETE_SIZE),
-                                          NOTEXPIRED_TIME_SEC);
-  cache->AddFullHashResponseToCache(map);
-
-  TestCache(CACHED_URL, true, false, false, cache.get());
-}