HashTable

Discussion in 'C++' started by carl, Nov 28, 2009.

  1. carl

    carl Guest

    I have found various hash_table implementation in c++ on the net. But I have
    not found any that returns the chain of objects associated with a hased
    index.

    When more that one object hash to the same index it gets added to a chain of
    elements. Are there any implmentations that returns the whole chain based on
    a hashed index?

    Its pretty much the functionality of a std::map that for each key contains a
    list (or std::vector) of the stored objects. But I would like the constant
    time lookup of the hash-table instead of the lg n time of a map.
    carl, Nov 28, 2009
    #1
    1. Advertising

  2. "carl" <carl@.com> wrote in message
    news:4b119ed2$0$275$...
    >I have found various hash_table implementation in c++ on the net. But I
    >have not found any that returns the chain of objects associated with a
    >hased index.
    >
    > When more that one object hash to the same index it gets added to a chain
    > of elements.


    Sometimes.




    > Are there any implmentations that returns the whole chain based on a
    > hashed index?


    Perhaps. It would be trivial to create one yourself. Just create a static
    hash table with a container per-bucket. Add a lookup function which returns
    a reference to the hashed container.




    > Its pretty much the functionality of a std::map that for each key contains
    > a list (or std::vector) of the stored objects. But I would like the
    > constant time lookup of the hash-table instead of the lg n time of a map.
    Chris M. Thomasson, Nov 29, 2009
    #2
    1. Advertising

  3. carl

    Pavel Guest

    carl wrote:
    > I have found various hash_table implementation in c++ on the net. But I
    > have not found any that returns the chain of objects associated with a
    > hased index.
    >
    > When more that one object hash to the same index it gets added to a
    > chain of elements. Are there any implmentations that returns the whole
    > chain based on a hashed index?
    >
    > Its pretty much the functionality of a std::map that for each key
    > contains a list (or std::vector) of the stored objects. But I would like
    > the constant time lookup of the hash-table instead of the lg n time of a
    > map.

    The functionality in std::map is actually slightly different and it *is*
    available in hash maps:

    You can iterate a sequence of objects with keys "Equal" or more
    precisely, equivalent, to your given key using equal_range() methods of
    both std::[multi]map and unordered_[multi]map (available in many current
    C++ implementations in std::tr1 namespace or you can use
    boost::unordered_map that provides the identical functionality).
    (unordered_map is a hash table).

    Additionaly to equal_range(), the following hash table-specific
    functionality is available in unordered_map: you can retrieve a bucket
    with bucket(key) call and iterate through the bucket but, if my reading
    of C++0x specs is correct, you may encounter more than one hashcode in
    the bucket (although it is guaranteed that you you will receive all
    objects with the hash value equal to the one of your key in one bucket
    and that the *average* length of the bucket is not greater than a
    reasonably low constant).

    If neither of the above alternatives is right for you, you may have to
    implement your own hash table (or use the existing one and somehow
    support the list or vector of elements with the equal hash codes on your
    own). I am not aware of an implementation that does exactly what you
    described (this certainly does not mean it is not available).

    Hope this will help
    -Pavel
    Pavel, Nov 29, 2009
    #3
  4. carl

    Stefan Ram Guest

    "carl" <carl@.com> writes:
    >When more that one object hash to the same index it gets added to a chain of
    >elements. Are there any implmentations that returns the whole chain based on
    >a hashed index?


    Welcome to the world of "object-oriented programming" (or,
    should I say just: "good practices of software engineering"?
    or "abstract data types"?), here: "encapsulation" and
    "information hiding"!

    A "map" is defined as an object with an interface that
    specifically does /not/ reveal this information. (For example,
    so that it might change. In fact, a hash map might rehash its
    entries sometimes so that also this chain will change.)
    Stefan Ram, Nov 29, 2009
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Guillermo

    Problem with hashTable

    Guillermo, Mar 4, 2004, in forum: Perl
    Replies:
    1
    Views:
    598
    Gunnar Hjalmarsson
    Mar 4, 2004
  2. Jonathan Wolfson

    vbc compilation fails when using Hashtable

    Jonathan Wolfson, Jun 27, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    537
    Tu-Thach
    Jun 27, 2003
  3. John E

    Get Hashtable Object Directly

    John E, Oct 8, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    2,310
    Nicholas Paldino [.NET/C# MVP]
    Oct 8, 2003
  4. diya

    Type Hashtable not defined

    diya, Oct 31, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    1,751
    Nicole Calinoiu
    Oct 31, 2003
  5. D. Shane Fowlkes

    ArrayList versus HashTable

    D. Shane Fowlkes, Feb 12, 2004, in forum: ASP .Net
    Replies:
    2
    Views:
    17,764
    Kevin Spencer
    Feb 12, 2004
Loading...

Share This Page