3
$\begingroup$

I've created a data structure that is a hash of arrays with a special property: the hash keeps track of the combined order in which items are appended to its arrays.

For example (pseudocode):

h = HashOfArray()

h["a"].append(1) // accessing an unset key returns an empty array
h["b"].append(2)
h["a"].append(3)
h["b"].append(4)

h["a"]
>>> [1, 3]

h["b"]
>>> [2, 4]

h.items()
>>> [1, 2, 3, 4]

I'm struggling with coming up with a good name for this data structure. Does it have a commonly used name? I've called it HashOfArray but that fails to convey its main property: that it maintains the combined append order of the arrays.

Example implementation in Ruby: https://gist.github.com/kajic/7981533

$\endgroup$
6
  • $\begingroup$ How did you implement it? $\endgroup$ Dec 18, 2013 at 21:15
  • $\begingroup$ Here is an implementation in Ruby: gist.github.com/kajic/7981533 $\endgroup$
    – kajic
    Dec 18, 2013 at 21:42
  • $\begingroup$ I don't know Ruby, but it looks as though you just keep a parent array, and insert into in whenever you insert into a child... $\endgroup$ Dec 18, 2013 at 22:20
  • $\begingroup$ The parent variable is a reference to the parent hash which contains the arrays. Every time an object is appended to any one of the hashes, a reference to the object is also appended to the items array on the parent. The items array therefore has the combined append order of the objects inserted into all the arrays. $\endgroup$
    – kajic
    Dec 18, 2013 at 22:40
  • $\begingroup$ If there is only one array then this is like python's ordered dictionary. $\endgroup$ Dec 19, 2013 at 5:51

2 Answers 2

1
$\begingroup$

No, this data structure does not have a commonly-used name. It so similar to a hash table that it is very unlikely to have been the subject of a peer-reviewed publication.

$\endgroup$
0
$\begingroup$

I am not familiar with a name that will describe your entire data structure, but to simplify it you can name it: HashQueue as your arrays are Queue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.