Thread: hash table?

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    12

    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

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by bennyboy View Post
    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.
    (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.
    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.

    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.
    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.
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 09:23 PM
  2. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 05:06 PM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  4. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 07:54 PM
  5. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 09:00 PM