diff --git a/java/src/com/android/inputmethod/keyboard/Key.java b/java/src/com/android/inputmethod/keyboard/Key.java
index 42d1fe1..028e3fd 100644
--- a/java/src/com/android/inputmethod/keyboard/Key.java
+++ b/java/src/com/android/inputmethod/keyboard/Key.java
@@ -37,6 +37,7 @@
 import org.xmlpull.v1.XmlPullParser;
 import org.xmlpull.v1.XmlPullParserException;
 
+import java.util.Arrays;
 import java.util.HashMap;
 import java.util.Map;
 
@@ -116,6 +117,8 @@
     private static final int ACTION_FLAGS_NO_KEY_PREVIEW = 0x02;
     private static final int ACTION_FLAGS_ALT_CODE_WHILE_TYPING = 0x04;
 
+    private final int mHashCode;
+
     /** The current pressed state of this key */
     private boolean mPressed;
     /** If this is a sticky key, is its highlight on? */
@@ -204,6 +207,8 @@
         mX = x + mHorizontalGap / 2;
         mY = y;
         mHitBox.set(x, y, x + width + 1, y + height);
+
+        mHashCode = hashCode(this);
     }
 
     /**
@@ -279,10 +284,6 @@
                 KeyboardIconsSet.ICON_UNDEFINED));
         final int shiftedIconId = style.getInt(keyAttr, R.styleable.Keyboard_Key_keyIconShifted,
                 KeyboardIconsSet.ICON_UNDEFINED);
-        if (shiftedIconId != KeyboardIconsSet.ICON_UNDEFINED) {
-            final Drawable shiftedIcon = iconsSet.getIcon(shiftedIconId);
-            params.addShiftedIcon(this, shiftedIcon);
-        }
         mHintLabel = style.getText(keyAttr, R.styleable.Keyboard_Key_keyHintLabel);
 
         mLabel = style.getText(keyAttr, R.styleable.Keyboard_Key_keyLabel);
@@ -306,8 +307,61 @@
         }
         mAltCode = style.getInt(keyAttr,
                 R.styleable.Keyboard_Key_altCode, Keyboard.CODE_DUMMY);
+        mHashCode = hashCode(this);
 
         keyAttr.recycle();
+
+        if (shiftedIconId != KeyboardIconsSet.ICON_UNDEFINED) {
+            final Drawable shiftedIcon = iconsSet.getIcon(shiftedIconId);
+            params.addShiftedIcon(this, shiftedIcon);
+        }
+    }
+
+    private static int hashCode(Key key) {
+        return Arrays.hashCode(new Object[] {
+                key.mX,
+                key.mY,
+                key.mWidth,
+                key.mHeight,
+                key.mCode,
+                key.mLabel,
+                key.mHintLabel,
+                // Key can be distinguishable without the following members.
+                // key.mAltCode,
+                // key.mOutputText,
+                // key.mActionFlags,
+                // key.mLabelFlags,
+                // key.mIcon,
+                // key.mPreviewIcon,
+                // key.mBackgroundType,
+                // key.mHorizontalGap,
+                // key.mVerticalGap,
+                // key.mVisualInsetLeft,
+                // key.mVisualInsetRight,
+                // Arrays.hashCode(key.mMoreKeys),
+                // key.mMaxMoreKeysColumn,
+        });
+    }
+
+    private boolean equals(Key o) {
+        if (this == o) return true;
+        return o.mX == mX
+                && o.mY == mY
+                && o.mWidth == mWidth
+                && o.mHeight == mHeight
+                && o.mCode == mCode
+                && TextUtils.equals(o.mLabel, mLabel)
+                && TextUtils.equals(o.mHintLabel, mHintLabel);
+    }
+
+    @Override
+    public int hashCode() {
+        return mHashCode;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        return o instanceof Key && equals((Key)o);
     }
 
     public void markAsLeftEdge(KeyboardParams params) {
diff --git a/java/src/com/android/inputmethod/keyboard/Keyboard.java b/java/src/com/android/inputmethod/keyboard/Keyboard.java
index 8a08873..f21d454 100644
--- a/java/src/com/android/inputmethod/keyboard/Keyboard.java
+++ b/java/src/com/android/inputmethod/keyboard/Keyboard.java
@@ -26,7 +26,6 @@
 
 import java.util.Collections;
 import java.util.HashMap;
-import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
@@ -106,8 +105,8 @@
     public final boolean mIsRtlKeyboard;
 
     /** List of keys and icons in this keyboard */
-    public final List<Key> mKeys;
-    public final List<Key> mShiftKeys;
+    public final Set<Key> mKeys;
+    public final Set<Key> mShiftKeys;
     public final Set<Key> mShiftLockKeys;
     public final Map<Key, Drawable> mShiftedIcons;
     public final Map<Key, Drawable> mUnshiftedIcons;
@@ -134,8 +133,8 @@
         mTopPadding = params.mTopPadding;
         mVerticalGap = params.mVerticalGap;
 
-        mKeys = Collections.unmodifiableList(params.mKeys);
-        mShiftKeys = Collections.unmodifiableList(params.mShiftKeys);
+        mKeys = Collections.unmodifiableSet(params.mKeys);
+        mShiftKeys = Collections.unmodifiableSet(params.mShiftKeys);
         mShiftLockKeys = Collections.unmodifiableSet(params.mShiftLockKeys);
         mShiftedIcons = Collections.unmodifiableMap(params.mShiftedIcons);
         mUnshiftedIcons = Collections.unmodifiableMap(params.mUnshiftedIcons);
@@ -170,12 +169,12 @@
     }
 
     // TODO: Remove this method.
-    public boolean hasShiftLockKey() {
+    boolean hasShiftLockKey() {
         return !mShiftLockKeys.isEmpty();
     }
 
     // TODO: Remove this method.
-    public void setShiftLocked(boolean newShiftLockState) {
+    void setShiftLocked(boolean newShiftLockState) {
         for (final Key key : mShiftLockKeys) {
             // To represent "shift locked" state. The highlight is handled by background image that
             // might be a StateListDrawable.
@@ -191,7 +190,7 @@
     }
 
     // TODO: Remove this method.
-    public void setShifted(boolean newShiftState) {
+    void setShifted(boolean newShiftState) {
         if (!mShiftState.isShiftLocked()) {
             for (final Key key : mShiftKeys) {
                 key.setIcon(newShiftState ? mShiftedIcons.get(key) : mUnshiftedIcons.get(key));
@@ -206,7 +205,7 @@
     }
 
     // TODO: Remove this method
-    public void setAutomaticTemporaryUpperCase() {
+    void setAutomaticTemporaryUpperCase() {
         mShiftState.setAutomaticTemporaryUpperCase();
     }
 
diff --git a/java/src/com/android/inputmethod/keyboard/PointerTracker.java b/java/src/com/android/inputmethod/keyboard/PointerTracker.java
index 3a07cdf..7c14b58 100644
--- a/java/src/com/android/inputmethod/keyboard/PointerTracker.java
+++ b/java/src/com/android/inputmethod/keyboard/PointerTracker.java
@@ -29,6 +29,7 @@
 
 import java.util.ArrayList;
 import java.util.List;
+import java.util.Set;
 
 public class PointerTracker {
     private static final String TAG = PointerTracker.class.getSimpleName();
@@ -118,7 +119,7 @@
     private KeyboardActionListener mListener = EMPTY_LISTENER;
 
     private Keyboard mKeyboard;
-    private List<Key> mKeys;
+    private Set<Key> mKeys;
     private int mKeyQuarterWidthSquared;
     private final TextView mKeyPreviewText;
 
diff --git a/java/src/com/android/inputmethod/keyboard/ProximityInfo.java b/java/src/com/android/inputmethod/keyboard/ProximityInfo.java
index 7f7f9cb..b6178d9 100644
--- a/java/src/com/android/inputmethod/keyboard/ProximityInfo.java
+++ b/java/src/com/android/inputmethod/keyboard/ProximityInfo.java
@@ -24,7 +24,7 @@
 
 import java.util.Arrays;
 import java.util.Collections;
-import java.util.List;
+import java.util.Set;
 
 public class ProximityInfo {
     public static final int MAX_PROXIMITY_CHARS_SIZE = 16;
@@ -44,7 +44,7 @@
     private final Key[][] mGridNeighbors;
 
     ProximityInfo(int gridWidth, int gridHeight, int minWidth, int height, int keyWidth,
-            int keyHeight, List<Key> keys, TouchPositionCorrection touchPositionCorrection) {
+            int keyHeight, Set<Key> keys, TouchPositionCorrection touchPositionCorrection) {
         mGridWidth = gridWidth;
         mGridHeight = gridHeight;
         mGridSize = mGridWidth * mGridHeight;
@@ -62,7 +62,7 @@
     }
 
     public static ProximityInfo createDummyProximityInfo() {
-        return new ProximityInfo(1, 1, 1, 1, 1, 1, Collections.<Key>emptyList(), null);
+        return new ProximityInfo(1, 1, 1, 1, 1, 1, Collections.<Key>emptySet(), null);
     }
 
     public static ProximityInfo createSpellCheckerProximityInfo(final int[] proximity) {
@@ -87,9 +87,9 @@
     private native void releaseProximityInfoNative(long nativeProximityInfo);
 
     private final void setProximityInfo(Key[][] gridNeighborKeys, int keyboardWidth,
-            int keyboardHeight, List<Key> keys,
+            int keyboardHeight, Set<Key> keys,
             TouchPositionCorrection touchPositionCorrection) {
-        int[] proximityCharsArray = new int[mGridSize * MAX_PROXIMITY_CHARS_SIZE];
+        final int[] proximityCharsArray = new int[mGridSize * MAX_PROXIMITY_CHARS_SIZE];
         Arrays.fill(proximityCharsArray, KeyDetector.NOT_A_CODE);
         for (int i = 0; i < mGridSize; ++i) {
             final int proximityCharsLength = gridNeighborKeys[i].length;
@@ -118,8 +118,8 @@
             calculateSweetSpotParams = false;
         }
 
-        for (int i = 0; i < keyCount; ++i) {
-            final Key key = keys.get(i);
+        int i = 0;
+        for (final Key key : keys) {
             keyXCoordinates[i] = key.mX;
             keyYCoordinates[i] = key.mY;
             keyWidths[i] = key.mWidth;
@@ -142,6 +142,7 @@
                             hitBoxWidth * hitBoxWidth + hitBoxHeight * hitBoxHeight);
                 }
             }
+            i++;
         }
 
         mNativeProximityInfo = setProximityInfoNative(MAX_PROXIMITY_CHARS_SIZE,
@@ -166,7 +167,7 @@
         }
     }
 
-    private void computeNearestNeighbors(int defaultWidth, List<Key> keys,
+    private void computeNearestNeighbors(int defaultWidth, Set<Key> keys,
             TouchPositionCorrection touchPositionCorrection) {
         final int thresholdBase = (int) (defaultWidth * SEARCH_DISTANCE);
         final int threshold = thresholdBase * thresholdBase;
diff --git a/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java b/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
index 64cd37c..5248016 100644
--- a/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
+++ b/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
@@ -23,10 +23,8 @@
 import com.android.inputmethod.keyboard.KeyboardId;
 import com.android.inputmethod.latin.LatinImeLogger;
 
-import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.HashSet;
-import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
@@ -59,8 +57,8 @@
     public int GRID_WIDTH;
     public int GRID_HEIGHT;
 
-    public final List<Key> mKeys = new ArrayList<Key>();
-    public final List<Key> mShiftKeys = new ArrayList<Key>();
+    public final Set<Key> mKeys = new HashSet<Key>();
+    public final Set<Key> mShiftKeys = new HashSet<Key>();
     public final Set<Key> mShiftLockKeys = new HashSet<Key>();
     public final Map<Key, Drawable> mShiftedIcons = new HashMap<Key, Drawable>();
     public final Map<Key, Drawable> mUnshiftedIcons = new HashMap<Key, Drawable>();