--- a/mobile/android/base/java/org/mozilla/gecko/icons/IconDescriptorComparator.java
+++ b/mobile/android/base/java/org/mozilla/gecko/icons/IconDescriptorComparator.java
@@ -11,17 +11,17 @@ import java.util.Comparator;
  * This comparator implementation compares IconDescriptor objects in order to determine which icon
  * to load first.
  *
  * In general this comparator will try touch icons before favicons (they usually have a higher resolution)
  * and prefers larger icons over smaller ones.
  */
 /* package-private */ class IconDescriptorComparator implements Comparator<IconDescriptor> {
     @Override
-    public int compare(IconDescriptor lhs, IconDescriptor rhs) {
+    public int compare(final IconDescriptor lhs, final IconDescriptor rhs) {
         if (lhs.getUrl().equals(rhs.getUrl())) {
             // Two descriptors pointing to the same URL are always referencing the same icon. So treat
             // them as equal.
             return 0;
         }
 
         // First compare the types. We prefer touch icons because they tend to have a higher resolution
         // than ordinary favicons.
@@ -38,18 +38,20 @@ import java.util.Comparator;
         // an image larger than the size given in the <link> tag.
         final boolean lhsContainer = IconsHelper.isContainerType(lhs.getMimeType());
         final boolean rhsContainer = IconsHelper.isContainerType(rhs.getMimeType());
 
         if (lhsContainer != rhsContainer) {
             return lhsContainer ? -1 : 1;
         }
 
-        // There's no way to know which icon might be better. Just pick rhs.
-        return 1;
+        // There's no way to know which icon might be better. However we need to pick a consistent
+        // one to avoid breaking the TreeSet implementation (See Bug 1331808). Therefore we are
+        // picking one by just comparing the URLs.
+        return lhs.getUrl().compareTo(rhs.getUrl());
     }
 
     private int compareType(IconDescriptor lhs, IconDescriptor rhs) {
         if (lhs.getType() > rhs.getType()) {
             return -1;
         } else {
             return 1;
         }

--- a/mobile/android/tests/background/junit4/src/org/mozilla/gecko/icons/TestIconDescriptorComparator.java
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/icons/TestIconDescriptorComparator.java
@@ -4,16 +4,18 @@
 package org.mozilla.gecko.icons;
 
 import org.junit.Assert;
 
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.mozilla.gecko.background.testhelpers.TestRunner;
 
+import java.util.TreeSet;
+
 @RunWith(TestRunner.class)
 public class TestIconDescriptorComparator {
     private static final String TEST_ICON_URL_1 = "http://www.mozilla.org/favicon.ico";
     private static final String TEST_ICON_URL_2 = "http://www.example.org/favicon.ico";
     private static final String TEST_ICON_URL_3 = "http://www.example.com/favicon.ico";
 
     private static final String TEST_MIME_TYPE = "image/png";
     private static final int TEST_SIZE = 32;
@@ -110,9 +112,41 @@ public class TestIconDescriptorComparato
         final IconDescriptor descriptor1 = IconDescriptor.createFavicon(TEST_ICON_URL_1, TEST_SIZE, TEST_MIME_TYPE);
         final IconDescriptor descriptor2 = IconDescriptor.createFavicon(TEST_ICON_URL_2, TEST_SIZE, TEST_MIME_TYPE);
 
         final IconDescriptorComparator comparator = new IconDescriptorComparator();
 
         Assert.assertNotEquals(0, comparator.compare(descriptor1, descriptor2));
         Assert.assertNotEquals(0, comparator.compare(descriptor2, descriptor1));
     }
+
+    @Test
+    public void testWithSameObject() {
+        final IconDescriptor descriptor = IconDescriptor.createTouchicon(TEST_ICON_URL_1, TEST_SIZE, TEST_MIME_TYPE);
+
+        final IconDescriptorComparator comparator = new IconDescriptorComparator();
+        Assert.assertEquals(0, comparator.compare(descriptor, descriptor));
+    }
+
+    /**
+     * This test reconstructs the scenario from bug 1331808. A comparator implementation that does
+     * not return a consistent order can break the implementation of remove() of the TreeSet class.
+     */
+    @Test
+    public void testBug1331808() {
+        TreeSet<IconDescriptor> set = new TreeSet<>(new IconDescriptorComparator());
+
+        set.add(IconDescriptor.createFavicon("http://example.org/new-logo32.jpg", 0, ""));
+        set.add(IconDescriptor.createTouchicon("http://example.org/new-logo57.jpg", 0, ""));
+        set.add(IconDescriptor.createTouchicon("http://example.org/new-logo76.jpg", 76, ""));
+        set.add(IconDescriptor.createTouchicon("http://example.org/new-logo120.jpg", 120, ""));
+        set.add(IconDescriptor.createTouchicon("http://example.org/new-logo152.jpg", 114, ""));
+        set.add(IconDescriptor.createFavicon("http://example.org/02.png", 32, ""));
+        set.add(IconDescriptor.createFavicon("http://example.org/01.png", 192, ""));
+        set.add(IconDescriptor.createTouchicon("http://example.org/03.png", 0, ""));
+
+        for (int i = 8; i > 0; i--) {
+            Assert.assertEquals("items in set before deleting: " + i, i, set.size());
+            Assert.assertTrue("item removed successfully: " + i, set.remove(set.first()));
+            Assert.assertEquals("items in set after deleting: " + i, i - 1, set.size());
+        }
+    }
 }

--- a/mobile/android/tests/background/junit4/src/org/mozilla/gecko/icons/TestIconRequest.java
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/icons/TestIconRequest.java
@@ -34,23 +34,23 @@ public class TestIconRequest {
 
         request.modify()
                 .icon(IconDescriptor.createGenericIcon(TEST_ICON_URL_2))
                 .deferBuild();
 
         Assert.assertEquals(2, request.getIconCount());
         Assert.assertTrue(request.hasIconDescriptors());
 
-        Assert.assertEquals(TEST_ICON_URL_1, request.getBestIcon().getUrl());
+        Assert.assertEquals(TEST_ICON_URL_2, request.getBestIcon().getUrl());
 
         request.moveToNextIcon();
 
         Assert.assertEquals(1, request.getIconCount());
         Assert.assertTrue(request.hasIconDescriptors());
 
-        Assert.assertEquals(TEST_ICON_URL_2, request.getBestIcon().getUrl());
+        Assert.assertEquals(TEST_ICON_URL_1, request.getBestIcon().getUrl());
 
         request.moveToNextIcon();
 
         Assert.assertEquals(0, request.getIconCount());
         Assert.assertFalse(request.hasIconDescriptors());
     }
 }