Thread: Iterable hash tables

  1. #1
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555

    Iterable hash tables

    Just a thing that's been bugging me lately. I've read a considerable amount of theory on as well as implemented hash tables and for pretty much every implementation of them in different languages as well as similar data types (C++ std::map) you are able to iterate the keys and values, or even get an array of the keys and values. I'm wondering how this is done as I have only seen hash tables in the form of a large array where you hash a key into an index for that array. Iterating such an implementation would require brute force unless you add some additional information that can tell you about the location of things.

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    You could keep a linked list of occupied indexes.

    Insertion = O(1)
    Deletion = O(n)
    Iterating = O(n)

    Depending on your usage scenario and how saturated the hash table is, it may or may not be faster than "brute force".
    Last edited by cyberfish; 07-18-2008 at 07:41 PM.

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Iterating such an implementation would require brute force
    Huh? If you have a bucket hash table, you simply iterate over the buckets in sequence. I don't see what the problem is.

    Nobody ever guaranteed any specific order in the iteration of hash tables.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    You could keep a sorted linked list of occupied indexes.

    Insertion = log(n)
    Deletion = log(n)
    Iterating = n
    Insertion/Deletion into a sorted linked list is O(n). Binary search, which I'm assuming you're suggesting, requires random access into the container.

    You can always look into your STL's implementation and see how it works, if it has them, of std::hash_map or std::hash_set. (MinGW keeps these in an "ext" folder on my machine, but they're in STLPort too.) Additionally, TR1 has unordered_set/map, not sure how much these differ. None of these are standard, yet, I think. Read The Manual, as always.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Ah, my bad. Must have been drunk.

    Thanks for the correction.
    Post above editted. (There is no point in using a sorted list then)

  6. #6
    Registered User OnionKnight's Avatar
    Join Date
    Jan 2005
    Posts
    555
    Quote Originally Posted by CornedBee View Post
    Huh? If you have a bucket hash table, you simply iterate over the buckets in sequence. I don't see what the problem is.

    Nobody ever guaranteed any specific order in the iteration of hash tables.
    I wasn't thinking of order. But I usually envision hash tables to be sparse and that iterating over the whole array would take a lot of time. But I suppose you're right, if you keep your array sized in accommodation to the hash table's load you're not really wasting much time going over lots of empty buckets, and it is just O(n).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. developing hash tables in the C Programming language
    By w108dab in forum C Programming
    Replies: 1
    Last Post: 05-20-2008, 11:20 AM
  2. need help with hash tables with direct chaining
    By agentsmith in forum C Programming
    Replies: 4
    Last Post: 01-05-2008, 04:19 AM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  4. Problems with Hash Tables
    By Zildjian in forum C Programming
    Replies: 6
    Last Post: 11-06-2003, 08:53 PM
  5. Help with beginning hash tables, please.
    By Will in forum C++ Programming
    Replies: 8
    Last Post: 11-17-2002, 09:51 PM