Guaranteed ordering of a collection / collections backed table

I am trying to do the following. I want to back a table with a collection. Specifically, I'm thinking of using Hashtable (although I'm open to most any collection). I choose Hashtable, because of the following constaints:
1) The number of rows will vary with time. (It might be fast enough to do it with arrays, since I'm not sure how fast things will vary, but I would rather not risk it if I can avoid it.)
2) I will regularly have to look up specific rows to update them. Each row has a unique long associated with it. I index each row in the Hashtable off of the Long (wrapper) class. This allows O(1) searching so I can quickly update the rows--which will occur very rapidly.
The catch is with Hashtables, I get no ordering guarantees on the iterator. I can't guarantee that this row will always come before that row. Or can I? The sorted collections have iterators which have ordered iterators, right? Of course, these are log(N) search time, becaue they are tree based.
Any ideas how to back a table with a collection? (Maybe a SortedSet or some combination of SortedSet and HashMap.)
--Mark
[ February 03, 2003: Message edited by: Mark Herschberg ]

Mark,
A HashMap does not have an ordering guarantee, and when the array backing the map is resized the order in which keys are iterated through will change.

You could use a SortedMap (TreeMap) but would pay the price of O(log N) performance.

Depending on what type of ordering you want, a JDK 1.4 LinkedHashMap gives you a guaranteed ordering without the cost. The order is basically insertion order.

Finally, if the above doesn't suit you, you can implement your own data structure backed by both a HashMap and a SortedSet. Retrieving and updating can be O(1) but adding and removing are O(log N). Two approaches worth exploring are a SortedSet of keys and a SortedSet of Map.Entry objects.

- Peter
[ February 04, 2003: Message edited by: Peter den Haan ]

You could use a SortedMap (TreeMap) but would pay the price of O(log N) performance.

I'm willing to pay this penalty, but I need to be able to do a get(i) access on it, and I don't think either of those can do it. Do you have any more information on how to do this?

Depending on what type of ordering you want, a JDK 1.4 LinkedHashMap gives you a guaranteed ordering without the cost. The order is basically insertion order.

I hadn't seent his class before. It's what I want, but again I can't do a get(i).

Finally, if the above doesn't suit you, you can implement your own data structure backed by both a HashMap and a SortedSet. Retrieving and updating can be O(1) but adding and removing are O(log N). Two approaches worth exploring are a SortedSet of keys and a SortedSet of Map.Entry objects.

Yeah, I this is what I had been doing--something like it anyway. I guess I'll just have to bite the bullet.
--Mark

Originally posted by Mark Herschberg:
[...] I need to be able to do a get(i) access on it [...]

Is there any way that can be revised? -- you can iterate, you can access via your Long id; is there a way around having get(i) access as well?
- Peter

Originally posted by Peter den Haan:
Is there any way that can be revised? -- you can iterate, you can access via your Long id; is there a way around having get(i) access as well?

Well, I want this data structure to back a table. the table model must support get(row, col). The col comes from mapping the fields of the objects into columns. The row, however, comes from its position in the data set.
I guess I could convert the collection into an array, and whenver I structurally modify the collction, reproduce the array, but that seems highly inefficent.
Any other ideas?
--Mark

Mark,
As I understand it (and please correct me if I'm wrong) You want a list that can be accessed by constant order iteration, a row number or a long identifier. If this is the case, there is no single class in the collections framework that will work for you. My best advice would be either revise the requirements or write your own storage class that uses a HashMap to store the data keyed on the Long identifier, and an ArrayList to map those long identifiers to row numbers.

Mark: Why can't you use AbstractTableModel with a Comparator on it? I know that AbstractTableModel is most often used by JTable. However, I did a project awhile back that does similar to what you want, and AbstractTableModel worked beautifully.

Originally posted by Adrian Yan:
Mark: Why can't you use AbstractTableModel with a Comparator on it? I know that AbstractTableModel is most often used by JTable. However, I did a project awhile back that does similar to what you want, and AbstractTableModel worked beautifully.

Comparing on AbstractTableModels? I don't want models comapred, I want their data compared.

Originally posted by Pete Harris:
As I understand it (and please correct me if I'm wrong) You want a list that can be accessed by constant order iteration, a row number or a long identifier. If this is the case, there is no single class in the collections framework that will work for you.

Yeah, I ended up creating my own class...

package com.hbs.simtrade.client.util;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
 *  This class provides a hybrid data set used to back rapidly changing tables.
 *  It stores the data in both a HashMap and an ArrayList.  This allows for
 *  O(1) lookups for modifying the data.  Structural changes (e.g. adding and
 *  removing) takes O(N) time as it has t modify both data structures.
 *
 *  @author Mark A. Herschberg
 *  @version 1.0
 */
public class HashList {
   private HashMap    m_map;
   private ArrayList  m_list;
   public HashList() {
      m_map = new HashMap();
      m_list = new ArrayList();
   }

public void add(Object key, Object value) {
      m_map.put(key, value);
      m_list.add(value);
      System.err.println("Add 1: " + value.toString());
   }
   public void add(Object key, Object value, int index) {
      m_map.put(key, value);
      m_list.add(index, value);
      System.err.println("Add 2: " + value.toString());
   }
   public void remove(Object key) {
      Object value = m_map.remove(key);
      m_list.remove(value);
   }
   public Object get(int index) {
      return m_list.get(index);
   }
   public Object get(Object key) {
      return m_map.get(key);
   }
   public int size() {
      return m_list.size();
   }
   public Collection values() {
      return m_map.values();
   }
}