--- a/toolkit/components/url-classifier/nsUrlClassifierHashCompleter.js
+++ b/toolkit/components/url-classifier/nsUrlClassifierHashCompleter.js
@@ -465,19 +465,21 @@ HashCompleterRequest.prototype = {
       // We skip the table which is not associated with a state.
       if (state) {
         tableNameArray.push(name);
         stateArray.push(state);
       }
     });
 
     // Build the "distinct" prefix array.
+    // The array is sorted to make sure the entries are arbitrary mixed in a
+    // deterministic way
     let prefixSet = new Set();
     this._requests.forEach(r => prefixSet.add(btoa(r.partialHash)));
-    let prefixArray = Array.from(prefixSet);
+    let prefixArray = Array.from(prefixSet).sort();
 
     log("Build v4 gethash request with " + JSON.stringify(tableNameArray) + ', '
                                          + JSON.stringify(stateArray) + ', '
                                          + JSON.stringify(prefixArray));
 
     return gUrlUtil.makeFindFullHashRequestV4(tableNameArray,
                                               stateArray,
                                               prefixArray,
@@ -494,25 +496,18 @@ HashCompleterRequest.prototype = {
 
     for (let i = 0; i < this._requests.length; i++) {
       let request = this._requests[i];
       if (prefixes.indexOf(request.partialHash) == -1) {
         prefixes.push(request.partialHash);
       }
     }
 
-    // Randomize the order to obscure the original request from noise
-    // unbiased Fisher-Yates shuffle
-    let i = prefixes.length;
-    while (i--) {
-      let j = Math.floor(Math.random() * (i + 1));
-      let temp = prefixes[i];
-      prefixes[i] = prefixes[j];
-      prefixes[j] = temp;
-    }
+    // Sort to make sure the entries are arbitrary mixed in a deterministic way
+    prefixes.sort();
 
     let body;
     body = PARTIAL_LENGTH + ":" + (PARTIAL_LENGTH * prefixes.length) +
            "\n" + prefixes.join("");
 
     log('Requesting completions for ' + prefixes.length + ' ' + PARTIAL_LENGTH + '-byte prefixes: ' + body);
     return body;
   },

--- a/toolkit/components/url-classifier/tests/unit/test_hashcompleter_v4.js
+++ b/toolkit/components/url-classifier/tests/unit/test_hashcompleter_v4.js
@@ -78,17 +78,17 @@ add_test(function test_update_v4() {
   // Force table update.
   prefBranch.setCharPref(PREF_NEXTUPDATETIME_V4, "1");
   gListManager.maybeToggleUpdateChecking();
 });
 
 add_test(function test_getHashRequestV4() {
   let request = gUrlUtil.makeFindFullHashRequestV4([TEST_TABLE_DATA_V4.tableName],
                                                    [btoa(NEW_CLIENT_STATE)],
-                                                   [btoa("0123"), btoa("1234567"), btoa("1111")],
+                                                   [btoa("0123"), btoa("1234567"), btoa("1111")].sort(),
                                                    1,
                                                    3);
   registerHandlerGethashV4("&$req=" + request);
   let completeFinishedCnt = 0;
 
   gCompleter.complete("0123", TEST_TABLE_DATA_V4.gethashUrl, TEST_TABLE_DATA_V4.tableName, {
     completionV4(hash, table, duration, fullhashes) {
       equal(hash, "0123");