Andrew,
You're absolutely right - the semantics matter, as they always do. There are significant choices in the Java ecosystem because of this. If we are preserving insertion order, vs a comparator based ordering, skip lists and the specific ConcurrentSkipListMap implementation will not work.
As often the case, it's good to try things out. I looked at PyPy 2.5.0 this morning, and both set and dict are insertion order preserving. Interestingly, when creating a set:
>>> x = {1,2,3,4,5,6,7}
the resulting set is the reverse of its input, which I find surprising:
>>>> x
set([7, 6, 5, 4, 3, 2, 1])
Note that this is not the case if initializing from a sequence:
>>>> set([1,2,3,4,5,6,7])
set([1, 2, 3, 4, 5, 6, 7])
Using LinkedHashSet from Jython also does what is expected:
>>> from java.util import LinkedHashSet as LHS
>>> LHS([1,2,3,4,5,6,7])
[1, 2, 3, 4, 5, 6, 7]
(Iterators, etc, are consistent with the representations that are printed in these cases from PyPy and Jython.)
But there's one more important thing we have to consider. Jython needs ConcurrentMap semantics, so that we can support our interpretation of the Python memory model (sequential consistency, plus weakly consistent iteration is also depended on, see also
http://www.jython.org/jythonbook/en/1.0/Concurrency.html#python-memory-model). There's some interesting work out there to support a ConcurrentLinkedHashMap implementation (
https://code.google.com/p/concurrentlinkedhashmap/), the design of which was used as the basis of the design of the LRU cache in Google Guava, but it would require some further investigation to see how this would impact Jython.
Trying out an alternative implementation in Jython would still be on the order of a few lines of code changes, however :), which gives us a nice low cost for such experiments.
- Jim