Re-orderable keyed access structure?

[BrowserUk]

I have a collection of items. They must be accessible by key (which says hash), but also by position (which says array).

This begins to sound like an Tie::( DxHash/IxHash/InsertOrderedHash ), but it's not.

I need to be able to:

1. re-order the items in the array, but retain the keyed access from the hash.
2. alter an items position in the array, having located it by key.
3. discover the items key, having located it through array indices.

  hash               array
+---+---+            +---+
| A |   | -\   /---> |   | 0
+---+---+   \ /      +---+
| B |   | ---/-\ /-> |   | 1
+---+---+   / \ \    +---+
| C |   | -/   / \-> |   | 2
+---+---+     / \    +---+
| D |   | -\ /   \-> |   | 3
+---+---+   \        +---+
| E |   | -/ \-----> |   | 4
+---+---+            +---+

If I use the indices for the array elements as the values of the hash, I fail requirement 1).

If I use references to the array elements as the values of the hash, 1) is satisfied but 2) & 3) aren't.

If I store the data as the value in the hash, and put a copy of the key in the array, then I satisfy 1) & 3), but not 2).

So my question is: Is there some method method of satisfying all 3 requirements without resorting to a linear search of either the array or the hash values?

It feels as though one extra level of indirection is required, but I can't see where to put it.

If it makes a difference, the items themselves are already references to arrays containing several items, and I'd prefer to avoid to many further levels of indirection.