diff --git a/bikeshed/src/com/google/gwt/bikeshed/list/client/Column.java b/bikeshed/src/com/google/gwt/bikeshed/list/client/Column.java
index f296f4f..42b522a 100644
--- a/bikeshed/src/com/google/gwt/bikeshed/list/client/Column.java
+++ b/bikeshed/src/com/google/gwt/bikeshed/list/client/Column.java
@@ -54,6 +54,15 @@
     return cell.consumesEvents();
   }
 
+  /**
+   * Returns true if the contents of the column may depend on the current
+   * state of the selection model associated with the table that is displaying
+   * this column.  The default implementation returns false.
+   */
+  public boolean dependsOnSelection() {
+    return false;
+  }
+
   public Cell<C, V> getCell() {
     return cell;
   }
diff --git a/bikeshed/src/com/google/gwt/bikeshed/list/client/PagingTableListView.java b/bikeshed/src/com/google/gwt/bikeshed/list/client/PagingTableListView.java
index 1124b75..d24666b 100644
--- a/bikeshed/src/com/google/gwt/bikeshed/list/client/PagingTableListView.java
+++ b/bikeshed/src/com/google/gwt/bikeshed/list/client/PagingTableListView.java
@@ -196,6 +196,17 @@
         row.setClassName("pagingTableListView "
             + ((indexOnPage & 0x1) == 0 ? "evenRow" : "oddRow"));
       }
+
+      int numCols = columns.size();
+      for (int c = 0; c < numCols; ++c) {
+        TableCellElement cell = row.getCells().getItem(c);
+        StringBuilder sb = new StringBuilder();
+        Column<T, ?, ?> column = columns.get(c);
+        if (column.dependsOnSelection()) {
+          columns.get(c).render(q, sb);
+          cell.setInnerHTML(sb.toString());
+        }
+      }
     }
   }
 
diff --git a/bikeshed/src/com/google/gwt/bikeshed/list/shared/DefaultSelectionModel.java b/bikeshed/src/com/google/gwt/bikeshed/list/shared/DefaultSelectionModel.java
index 31046a0..30e5f7a 100644
--- a/bikeshed/src/com/google/gwt/bikeshed/list/shared/DefaultSelectionModel.java
+++ b/bikeshed/src/com/google/gwt/bikeshed/list/shared/DefaultSelectionModel.java
@@ -29,7 +29,9 @@
 public abstract class DefaultSelectionModel<T> extends
     AbstractSelectionModel<T> {
 
-  private final Map<T, Boolean> exceptions = new HashMap<T, Boolean>();
+  private final Map<Object, Boolean> exceptions = new HashMap<Object, Boolean>();
+
+  private final ProvidesKey<T> keyProvider = getKeyProvider();
 
   /**
    * Removes all exceptions.
@@ -53,7 +55,8 @@
    */
   public boolean isSelected(T object) {
     // Check exceptions first
-    Boolean exception = exceptions.get(object);
+    Object key = getKey(object);
+    Boolean exception = exceptions.get(key);
     if (exception != null) {
       return exception.booleanValue();
     }
@@ -69,12 +72,13 @@
    * selected state.
    */
   public void setSelected(T object, boolean selected) {
-    Boolean currentlySelected = exceptions.get(object);
+    Object key = getKey(object);
+    Boolean currentlySelected = exceptions.get(key);
     if (currentlySelected != null
         && currentlySelected.booleanValue() != selected) {
-      exceptions.remove(object);
+      exceptions.remove(key);
     } else {
-      exceptions.put(object, selected);
+      exceptions.put(key, selected);
     }
 
     scheduleSelectionChangeEvent();
@@ -83,8 +87,15 @@
   /**
    * Copies the exceptions map into a user-supplied map.
    */
-  protected void getExceptions(Map<T, Boolean> output) {
+  protected void getExceptions(Map<Object, Boolean> output) {
     output.clear();
     output.putAll(exceptions);
   }
+
+  private Object getKey(T object) {
+    if (keyProvider == null) {
+      return object;
+    }
+    return keyProvider.getKey(object);
+  }
 }
diff --git a/bikeshed/src/com/google/gwt/bikeshed/list/shared/SelectionModel.java b/bikeshed/src/com/google/gwt/bikeshed/list/shared/SelectionModel.java
index 9fe4548..8bc91bf 100644
--- a/bikeshed/src/com/google/gwt/bikeshed/list/shared/SelectionModel.java
+++ b/bikeshed/src/com/google/gwt/bikeshed/list/shared/SelectionModel.java
@@ -111,6 +111,8 @@
      */
     private boolean isEventScheduled;
 
+    private ProvidesKey<T> keyProvider;
+
     public HandlerRegistration addSelectionChangeHandler(
         SelectionChangeHandler handler) {
       return handlerManager.addHandler(SelectionChangeEvent.getType(), handler);
@@ -121,6 +123,20 @@
     }
 
     /**
+     * Returns a ProvidesKey instance that simply returns the input data item.
+     */
+    public ProvidesKey<T> getKeyProvider() {
+      if (keyProvider == null) {
+        keyProvider  = new ProvidesKey<T>() {
+          public Object getKey(T item) {
+            return item;
+          }
+        };
+      }
+      return keyProvider;
+    }
+
+    /**
      * Schedules a {@link SelectionModel.SelectionChangeEvent} to fire at the
      * end of the current event loop.
      */
@@ -146,6 +162,12 @@
   HandlerRegistration addSelectionChangeHandler(SelectionChangeHandler handler);
 
   /**
+   * Returns a ProvidesKey instance that may be used to provide a unique
+   * key for each record.
+   */
+  ProvidesKey<T> getKeyProvider();
+
+  /**
    * Check if an object is selected.
    *
    * @param object the object
diff --git a/bikeshed/src/com/google/gwt/sample/bikeshed/mail/client/MailSample.java b/bikeshed/src/com/google/gwt/sample/bikeshed/mail/client/MailSample.java
index fa30a91..d4d9cea 100644
--- a/bikeshed/src/com/google/gwt/sample/bikeshed/mail/client/MailSample.java
+++ b/bikeshed/src/com/google/gwt/sample/bikeshed/mail/client/MailSample.java
@@ -23,6 +23,7 @@
 import com.google.gwt.bikeshed.list.client.TextColumn;
 import com.google.gwt.bikeshed.list.shared.DefaultSelectionModel;
 import com.google.gwt.bikeshed.list.shared.ListListModel;
+import com.google.gwt.bikeshed.list.shared.ProvidesKey;
 import com.google.gwt.core.client.EntryPoint;
 import com.google.gwt.event.dom.client.ClickEvent;
 import com.google.gwt.event.dom.client.ClickHandler;
@@ -55,6 +56,13 @@
       }
     }
 
+    private static ProvidesKey<Message> keyProvider =
+      new ProvidesKey<Message>() {
+        public Object getKey(Message item) {
+          return Integer.valueOf(item.id);
+        }
+    };
+
     // A map from enum names to their values
     private static Map<String, Type> typeMap = new HashMap<String, Type>();
 
@@ -62,6 +70,11 @@
     private Type type = Type.NONE;
 
     @Override
+    public ProvidesKey<Message> getKeyProvider() {
+      return keyProvider;
+    }
+
+    @Override
     public boolean isDefaultSelected(Message object) {
       switch (type) {
         case NONE:
@@ -109,7 +122,7 @@
       }
 
       // Copy the exceptions into a TreeMap in order to sort by message id
-      TreeMap<Message, Boolean> exceptions = new TreeMap<Message, Boolean>();
+      TreeMap<Object, Boolean> exceptions = new TreeMap<Object, Boolean>();
       getExceptions(exceptions);
 
       appendExceptions(sb, exceptions, true);
@@ -124,10 +137,10 @@
     }
 
     private void appendExceptions(StringBuilder sb,
-        Map<Message, Boolean> exceptions, boolean selected) {
+        Map<Object, Boolean> exceptions, boolean selected) {
       boolean first = true;
-      for (Message message : exceptions.keySet()) {
-        if (exceptions.get(message) != selected) {
+      for (Object messageId : exceptions.keySet()) {
+        if (exceptions.get(messageId) != selected) {
           continue;
         }
 
@@ -136,7 +149,7 @@
           sb.append(selected ? '+' : '-');
           sb.append("msg(s) ");
         }
-        sb.append(message.id);
+        sb.append(messageId);
         sb.append(' ');
       }
     }
@@ -257,6 +270,11 @@
     SimpleColumn<Message, Boolean> selectedColumn = new SimpleColumn<Message, Boolean>(
         new CheckboxCell()) {
       @Override
+      public boolean dependsOnSelection() {
+        return true;
+      }
+
+      @Override
       public Boolean getValue(Message object) {
         return selectionModel.isSelected(object);
       }
@@ -269,6 +287,14 @@
     });
     table.addColumn(selectedColumn, "Selected");
 
+    TextColumn<Message> idColumn = new TextColumn<Message>() {
+      @Override
+      public String getValue(Message object) {
+        return "" + object.id;
+      }
+    };
+    table.addColumn(idColumn, "ID");
+
     TextColumn<Message> isReadColumn = new TextColumn<Message>() {
       @Override
       public String getValue(Message object) {