NSOrderedSet seems to be able to give O(1) lookup speed of hash-tables and array like ordering of objects? What is the data structure used to achieve this? Is it a combination of two, e.g: Hashtable and a separate Array where index i has the key corresponding to it's object in the Hashtable?
We don't know how Apple chose to implement this data structure. The only way to find out would be to reverse-engineer the Foundation framework. But this is not an useful thing to do, Apple could change the implementation and underlying data structure with every update. So relying on this for a production app would be very stupid since it could break the app at any time.
If you wanted to implement this yourself your approach with a hash table and an array will work. The best way would be to store the objects in the array and have the hash map store the array indices keyed by objects.
Of course there are other possible ways how this could be implemented with different performance characteristics. It could be just an array making the containsObject: test O(n), or it could just be a hash table (with the object as key and index as value) making the objectAtIndex: operation O(n).