hash table?

Hi all,

As a small part of a project I am currently working on, I need some way to do the following.

Keep adding new entries to a list, each of these new entries has an identity (double number) unique to itself. The list needs to be variable in size so an array is out of the question (I don't want to bodge it by making a massive array and hoping its OK - unless this is the best option in your opinions).
I only want each identity to have 3 entries in the list, any more and I don't want them added. The most important aspect of this is that it is fast and low on memory requirements.

Here are my ideas on how to implement:

1) Use a hash table - no good as this requires a set size of the list from the beginning.

2) Use a linked list where each element contains an array of 3 containing the details of each entry with the same identity.

I think the linked list idea (2) is the only way of doing it due to the variable size, but this means that each time I want to add a new entry to the list I have to search through the whole list to check for previous identical entries - unlike the hash table where I can key straight to it.

Basically, I would like some advice on what's the best option, or if there's a better way of doing this?

Thank you all for your time,

Ben

The linked list idea sounds good to me. If you add new links in a sorted manner (e.g. if you're adding ID 57 it would go after 43 but before 62) then you only have to look through the list until the ID of the current node is greater than or equal to the ID you're adding. Coincidentally, where your search ends is also where you need to insert the new node if the ID doesn't already exist in the list.

Quote:

---

Originally Posted by bennyboy

Keep adding new entries to a list, each of these new entries has an identity (double number) unique to itself. The list needs to be variable in size so an array is out of the question

---

No it isn't. In fact a C++ vector is implemented as an array, and yet can hold a variable number of items. It simply creates a larger vector when the original one fills to capacity, and copies everything over to the new larger one.

Quote:

---

(I don't want to bodge it by making a massive array and hoping its OK - unless this is the best option in your opinions).

---

No need to declare a static array and 'bodge' it when you can use a dynamic array.

Quote:

---

I only want each identity to have 3 entries in the list, any more and I don't want them added. The most important aspect of this is that it is fast and low on memory requirements.

---

The above technique used by a vector has zero per item memory usage overhead, and has amortised constant time overhead per insertion, meaning that it is indeed very fast.

Quote:

---

Here are my ideas on how to implement:

1) Use a hash table - no good as this requires a set size of the list from the beginning.

---

No it doesn't, for the same reasons as mentioned earlier. A std::tr1::hashmap uses a hash table, and yet can hold a variable number of items.

Quote:

---

2) Use a linked list where each element contains an array of 3 containing the details of each entry with the same identity.

I think the linked list idea (2) is the only way of doing it due to the variable size,

---

In that case you have a very limited knowledge of data structures. For starters, as binary tree might be a sensible option. There are many different kinds of binary trees too, and there are other structures such as skip-lists, that would be appropriate.

Quote:

---

but this means that each time I want to add a new entry to the list I have to search through the whole list to check for previous identical entries - unlike the hash table where I can key straight to it.

Basically, I would like some advice on what's the best option, or if there's a better way of doing this?

---

Use a self-balancing binary-tree of small 3-item lists or arrays.

Even better, if you're programming in Windows, look into the VirtualAlloc function.