Results 1 to 10 of 10

Thread: How do you make an associative array in C?

  1. #1
    Join Date
    Feb 2010
    Location
    Sweden
    Beans
    227
    Distro
    Ubuntu

    Question How do you make an associative array in C?

    I know the theory: "Hash the value you want to store and use the hash-th place in the array to store it".

    That gives me some problems though. I have a hash function that hashes any string to a number between 1 and 20,158,268,676. So for example:

    Code:
    "Athens" -> 8407130567
    "Sparta" -> 597153027
    Now if I follow the theory I would need an array of size at least 8407130567 to save my values. Then I would save with:

    Code:
    array[8407130567]="Athens"
    array[597153027]="Sparta"
    That ofcourse is not practical as it needs an enormous array. So how do we implement this? Is there some flaw in my thinking?

  2. #2
    Join Date
    Mar 2009
    Location
    Western Hemisphere.
    Beans
    136
    Distro
    Ubuntu

    Re: How do you make an associative array in C?

    While in theory it would be best to have an array as large as your space of all possible hashes, generally you choose a fixed length for the hash array, then map the hashes to indices in the array, and deal with collisions if they happen.

    So, one possible approach is to choose the array to be of size s, take all your hash values modulo s so that the index is in range, then instead of storing just the values, store a linked list of pointers to key-value pairs, and when you want to do a lookup, first lookup by hash key, and then compare the looked up keys to your key until you get a match.

    Obviously, the larger s is, the less often you'll have collisions, which will speed up lookup times, but cost memory.

    For more info, check out the wiki page.

  3. #3
    Join Date
    May 2008
    Location
    UK
    Beans
    1,450
    Distro
    Ubuntu 8.04 Hardy Heron

    Re: How do you make an associative array in C?

    why not have a binary tree or your hash's ? Relatively cheap to search and insert, and is as sparesley populated as you need it to be.
    Tony - Happy to try to help.
    Unless otherwise stated - all code posted by me is untested. Remember to Mark the Thread as Solved.
    Ubuntu user number # 24044 Projects : TimeWarp - on the fly Backups

  4. #4
    Join Date
    Feb 2010
    Location
    Sweden
    Beans
    227
    Distro
    Ubuntu

    Re: How do you make an associative array in C?

    Quote Originally Posted by Tony Flury View Post
    why not have a binary tree or your hash's ? Relatively cheap to search and insert, and is as sparesley populated as you need it to be.
    Well I never implemented a binary tree before so I am unsure if I will manage. Should it be implemented as a linked list where each node points to 2 other nodes?

  5. #5
    Join Date
    Oct 2005
    Beans
    36

    Re: How do you make an associative array in C?

    I'd probably just use a map, with the hash being a key.

    http://en.wikipedia.org/wiki/Std::map)

    *Whoops didn't realize this was for C and not C++.
    Last edited by DuneSoldier; March 16th, 2011 at 07:25 PM. Reason: Oops

  6. #6
    Join Date
    Nov 2009
    Location
    The Netherlands
    Beans
    239
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: How do you make an associative array in C?

    Quote Originally Posted by DuneSoldier View Post
    I'd probably just use a map, with the hash being a key.
    The question was about C, not C++

    I agree with Tony, a binary tree would probably be best.
    For a simple tutorial on how to implement one, se here http://www.ehow.com/how_2056293_crea...ry-tree-c.html

  7. #7
    Join Date
    Nov 2010
    Beans
    29

    Wink Re: How do you make an associative array in C?

    Code:
    array[8407130567]="Athens"
    array[597153027]="Sparta"
    With this algorithm, you'll need an array with the size 20,158,268,676 for the worst case. So, it'd be really ridiculous. Try binary tree.

  8. #8
    Join Date
    Nov 2009
    Beans
    1,081

    Re: How do you make an associative array in C?

    Quote Originally Posted by Pithikos View Post
    That ofcourse is not practical as it needs an enormous array. So how do we implement this? Is there some flaw in my thinking?
    Yes. Choose your hash size; let each space in the hash array be a pointer to a linked list (either the values themselves, if equality testing is slow pair of hash and value, if equality testing is expensive, since comparing hash values is a faster first pass); and simply do the obvious modulo arithmetic.

  9. #9
    Join Date
    Apr 2006
    Location
    Atlanta, USA
    Beans
    427

    Re: How do you make an associative array in C?

    Quote Originally Posted by Pithikos View Post
    Code:
    array[8407130567]="Athens"
    array[597153027]="Sparta"
    That ofcourse is not practical as it needs an enormous array. So how do we implement this? Is there some flaw in my thinking?
    Choose your array size first, and perform all hash calculations modulo array_size.

    When the number of items in your hashtable reaches a certain limit (75% is a common percentage), you grow your hashtable (usually by creating a new larger hash table, re-hashing all the elements in your original into the new, and then discarding the old). Similarly, when the load in your table drops below a certain percentage (e.g 25%), shrink the hashtable in a similar manner.
    Here we are, trapped in the amber of the moment. There is no why.

  10. #10
    Join Date
    Apr 2009
    Location
    Germany
    Beans
    2,134
    Distro
    Ubuntu Development Release

    Re: How do you make an associative array in C?

    Quote Originally Posted by johnl View Post
    Choose your array size first, and perform all hash calculations modulo array_size.

    When the number of items in your hashtable reaches a certain limit (75% is a common percentage), you grow your hashtable (usually by creating a new larger hash table, re-hashing all the elements in your original into the new, and then discarding the old). Similarly, when the load in your table drops below a certain percentage (e.g 25%), shrink the hashtable in a similar manner.
    you forgot to mention the most important part of this method: collision handling

    here are a few implementations you could use (along with a detailed description of the container):
    http://en.wikipedia.org/wiki/Hash_table#Implementations

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •