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$
  • $\begingroup$ How did you implement it? $\endgroup$ – Karolis Juodelė Dec 18 '13 at 21:15
  • $\begingroup$ Here is an implementation in Ruby: gist.github.com/kajic/7981533 $\endgroup$ – kajic Dec 18 '13 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$ – Karolis Juodelė Dec 18 '13 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 '13 at 22:40
  • $\begingroup$ If there is only one array then this is like python's ordered dictionary. $\endgroup$ – Yuval Filmus Dec 19 '13 at 5:51
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, privacy policy and cookie policy

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