diff --git a/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java b/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
index 6a21522..5b8f0e9 100644
--- a/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
+++ b/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
@@ -18,6 +18,7 @@
 
 import android.test.AndroidTestCase;
 import android.test.suitebuilder.annotation.LargeTest;
+import android.text.TextUtils;
 import android.util.Pair;
 
 import com.android.inputmethod.latin.makedict.CodePointUtils;
@@ -126,7 +127,7 @@
     public void testRandomlyAddUnigramWord() {
         final int wordCount = 1000;
         final int codePointSetSize = 50;
-        final int seed = 123456789;
+        final long seed = System.currentTimeMillis();
 
         File dictFile = null;
         try {
@@ -223,7 +224,8 @@
         final int wordCount = 100;
         final int bigramCount = 1000;
         final int codePointSetSize = 50;
-        final int seed = 11111;
+        final long seed = System.currentTimeMillis();
+        final Random random = new Random(seed);
 
         File dictFile = null;
         try {
@@ -234,43 +236,42 @@
         BinaryDictionary binaryDictionary = new BinaryDictionary(dictFile.getAbsolutePath(),
                 0 /* offset */, dictFile.length(), true /* useFullEditDistance */,
                 Locale.getDefault(), TEST_LOCALE, true /* isUpdatable */);
+
         final ArrayList<String> words = new ArrayList<String>();
-        // Test a word that isn't contained within the dictionary.
-        final Random random = new Random(seed);
+        final ArrayList<Pair<String, String>> bigramWords = new ArrayList<Pair<String,String>>();
         final int[] codePointSet = CodePointUtils.generateCodePointSet(codePointSetSize, random);
-        final int[] unigramProbabilities = new int[wordCount];
+        final HashMap<String, Integer> unigramProbabilities = new HashMap<String, Integer>();
+        final HashMap<Pair<String, String>, Integer> bigramProbabilities =
+                new HashMap<Pair<String, String>, Integer>();
+
         for (int i = 0; i < wordCount; ++i) {
             final String word = CodePointUtils.generateWord(random, codePointSet);
             words.add(word);
             final int unigramProbability = random.nextInt(0xFF);
-            unigramProbabilities[i] = unigramProbability;
+            unigramProbabilities.put(word, unigramProbability);
             binaryDictionary.addUnigramWord(word, unigramProbability);
         }
 
-        final int[][] probabilities = new int[wordCount][wordCount];
-
-        for (int i = 0; i < wordCount; ++i) {
-            for (int j = 0; j < wordCount; ++j) {
-                probabilities[i][j] = Dictionary.NOT_A_PROBABILITY;
-            }
-        }
-
         for (int i = 0; i < bigramCount; i++) {
-            final int word0Index = random.nextInt(wordCount);
-            final int word1Index = random.nextInt(wordCount);
-            final String word0 = words.get(word0Index);
-            final String word1 = words.get(word1Index);
+            final String word0 = words.get(random.nextInt(wordCount));
+            final String word1 = words.get(random.nextInt(wordCount));
+            if (TextUtils.equals(word0, word1)) {
+                continue;
+            }
+            final Pair<String, String> bigram = new Pair<String, String>(word0, word1);
+            bigramWords.add(bigram);
             final int bigramProbability = random.nextInt(0xF);
-            probabilities[word0Index][word1Index] = binaryDictionary.calculateProbability(
-                    unigramProbabilities[word1Index], bigramProbability);
+            bigramProbabilities.put(bigram, bigramProbability);
             binaryDictionary.addBigramWords(word0, word1, bigramProbability);
         }
 
-        for (int i = 0; i < words.size(); i++) {
-            for (int j = 0; j < words.size(); j++) {
-                assertEquals(probabilities[i][j],
-                        binaryDictionary.getBigramProbability(words.get(i), words.get(j)));
-            }
+        for (final Pair<String, String> bigram : bigramWords) {
+            final int unigramProbability = unigramProbabilities.get(bigram.second);
+            final int bigramProbability = bigramProbabilities.get(bigram);
+            final int probability = binaryDictionary.calculateProbability(unigramProbability,
+                    bigramProbability);
+            assertEquals(probability,
+                    binaryDictionary.getBigramProbability(bigram.first, bigram.second));
         }
 
         dictFile.delete();
@@ -419,8 +420,8 @@
         final int wordCount = 100;
         final int bigramCount = 1000;
         final int codePointSetSize = 30;
-        // TODO: Use various seeds such as a current timestamp to make this test more random.
-        final int seed = 314159265;
+        final long seed = System.currentTimeMillis();
+        final Random random = new Random(seed);
 
         File dictFile = null;
         try {
@@ -432,35 +433,32 @@
         BinaryDictionary binaryDictionary = new BinaryDictionary(dictFile.getAbsolutePath(),
                 0 /* offset */, dictFile.length(), true /* useFullEditDistance */,
                 Locale.getDefault(), TEST_LOCALE, true /* isUpdatable */);
+
         final ArrayList<String> words = new ArrayList<String>();
-        // Test a word that isn't contained within the dictionary.
-        final Random random = new Random(seed);
+        final ArrayList<Pair<String, String>> bigramWords = new ArrayList<Pair<String,String>>();
         final int[] codePointSet = CodePointUtils.generateCodePointSet(codePointSetSize, random);
-        final int[] unigramProbabilities = new int[wordCount];
+        final HashMap<String, Integer> unigramProbabilities = new HashMap<String, Integer>();
+        final HashMap<Pair<String, String>, Integer> bigramProbabilities =
+                new HashMap<Pair<String, String>, Integer>();
+
         for (int i = 0; i < wordCount; ++i) {
             final String word = CodePointUtils.generateWord(random, codePointSet);
             words.add(word);
             final int unigramProbability = random.nextInt(0xFF);
-            unigramProbabilities[i] = unigramProbability;
+            unigramProbabilities.put(word, unigramProbability);
             binaryDictionary.addUnigramWord(word, unigramProbability);
         }
 
-        final int[][] probabilities = new int[wordCount][wordCount];
-
-        for (int i = 0; i < wordCount; ++i) {
-            for (int j = 0; j < wordCount; ++j) {
-                probabilities[i][j] = Dictionary.NOT_A_PROBABILITY;
-            }
-        }
-
         for (int i = 0; i < bigramCount; i++) {
-            final int word0Index = random.nextInt(wordCount);
-            final int word1Index = random.nextInt(wordCount);
-            final String word0 = words.get(word0Index);
-            final String word1 = words.get(word1Index);
+            final String word0 = words.get(random.nextInt(wordCount));
+            final String word1 = words.get(random.nextInt(wordCount));
+            if (TextUtils.equals(word0, word1)) {
+                continue;
+            }
+            final Pair<String, String> bigram = new Pair<String, String>(word0, word1);
+            bigramWords.add(bigram);
             final int bigramProbability = random.nextInt(0xF);
-            probabilities[word0Index][word1Index] = binaryDictionary.calculateProbability(
-                    unigramProbabilities[word1Index], bigramProbability);
+            bigramProbabilities.put(bigram, bigramProbability);
             binaryDictionary.addBigramWords(word0, word1, bigramProbability);
         }
 
@@ -470,12 +468,15 @@
                 0 /* offset */, dictFile.length(), true /* useFullEditDistance */,
                 Locale.getDefault(), TEST_LOCALE, true /* isUpdatable */);
 
-        for (int i = 0; i < words.size(); i++) {
-            for (int j = 0; j < words.size(); j++) {
-                assertEquals(probabilities[i][j],
-                        binaryDictionary.getBigramProbability(words.get(i), words.get(j)));
-            }
+        for (final Pair<String, String> bigram : bigramWords) {
+            final int unigramProbability = unigramProbabilities.get(bigram.second);
+            final int bigramProbability = bigramProbabilities.get(bigram);
+            final int probability = binaryDictionary.calculateProbability(unigramProbability,
+                    bigramProbability);
+            assertEquals(probability,
+                    binaryDictionary.getBigramProbability(bigram.first, bigram.second));
         }
+
         dictFile.delete();
     }
 
@@ -487,8 +488,8 @@
         final float addBigramProb = 0.8f;
         final float removeBigramProb = 0.2f;
         final int codePointSetSize = 30;
-        final int seed = 141421356;
 
+        final long seed = System.currentTimeMillis();
         final Random random = new Random(seed);
 
         File dictFile = null;
@@ -539,6 +540,9 @@
                     }
                     final String word0 = words.get(word0Index);
                     final String word1 = words.get(word1Index);
+                    if (TextUtils.equals(word0, word1)) {
+                        continue;
+                    }
                     final int bigramProbability = random.nextInt(0xF);
                     final Pair<String, String> bigram = new Pair<String, String>(word0, word1);
                     bigramWords.add(bigram);
@@ -586,8 +590,8 @@
     public void testAddManyUnigramsAndFlushWithGC() {
         final int flashWithGCIterationCount = 3;
         final int codePointSetSize = 50;
-        final int seed = 22360679;
 
+        final long seed = System.currentTimeMillis();
         final Random random = new Random(seed);
 
         File dictFile = null;
@@ -632,8 +636,7 @@
         final int codePointSetSize = 50;
         final int unigramCountPerIteration = 1000;
         final int bigramCountPerIteration = 2000;
-        final int seed = 1123581321;
-
+        final long seed = System.currentTimeMillis();
         final Random random = new Random(seed);
 
         File dictFile = null;
@@ -661,6 +664,9 @@
             for (int j = 0; j < bigramCountPerIteration; j++) {
                 final String word0 = words.get(random.nextInt(words.size()));
                 final String word1 = words.get(random.nextInt(words.size()));
+                if (TextUtils.equals(word0, word1)) {
+                    continue;
+                }
                 bigrams.add(new Pair<String, String>(word0, word1));
                 final int bigramProbability = random.nextInt(0xF);
                 binaryDictionary.addBigramWords(word0, word1, bigramProbability);