Hash Table / Map -> C++ O(1) by key ?

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Hash Table / Map -> C++ O(1) by key ?

Post by Sedefcho » Wed Feb 04, 2009 8:28 pm

I need a hash table (or hash map in C++) which has constant time access
(given a key). How do I do that in the UVA Judge (with least coding)?

I read about using hash_map from some extension library of
the Standard C++. But that does not work for me
(compilation errors). Maybe I am doing something wrong.

Is it possible to get this working (constant time c++ hash map) without
too much coding or do I need to code a bit more for this? I am asking this
as in Java there's a standard hash table (with constant time
access by key /well, at least in theory it is 'constant time' /).
But in Java everything is quite different - it is interpreted,
each object derives from java.lang.Object and has
hashCode() and equals() methods. But anyway.

So the point is that in C++ the standard map has O(log(N))
access when searching for a key (at least that's what Wikipedia says).
And log(N) is too much for me for a certain problem which I am trying to solve.

For all answers - thanks in advance.
(and yes, I am not a guru in C++, I know my question
is pretty basic :) but I did some search here & on the web
and did not find much information)

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: Hash Table / Map -> C++ O(1) by key ?

Post by Sedefcho » Wed Feb 04, 2009 10:51 pm

I think I found a way to use hash_map but all info
points this usage is not portable and/or standard?!

So if I assume no usage of the GNU compiler I still don't
know how to do it (at least not in a portable/general way).

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Hash Table / Map -> C++ O(1) by key ?

Post by mf » Thu Feb 05, 2009 4:09 am

Yes, gcc's ext/hash_map is not portable. It even uses a very gcc-specific namespace: __gnu_cxx.

TR1 (which will be a part of next C++ standard) has unordered_map container - a hash table, but it's not yet supported by UVa's compiler.

It's actually not hard to code a simple hash table. Here's a linear-probing hash table that I've once used:

Code: Select all

template<class K, class V> struct HashMap {
    vector<pair<K, V> > tab;
    vector<char> used;
    HashMap(int maxsize) : tab(maxsize), used(maxsize, 0) {}
    V *lookup(const K &key, bool insert) {
        for (int i = hash(key) % tab.size();;) {
            if (used[i]) {
                if (tab[i].first == key) return &tab[i].second;
            } else {
                if (!insert) return NULL;
                used[i] = 1;
                tab[i].first = key;
                return &tab[i].second;
            }
            if (++i == tab.size()) i = 0;
        }
    }
    V &operator[](const K &key) { return *lookup(key, true); }
    bool contains(const K &key) { return lookup(key, false) != NULL; }
};

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: Hash Table / Map -> C++ O(1) by key ?

Post by Sedefcho » Thu Feb 05, 2009 8:05 pm

Thanks , I may try it.

I actually was trying to solve problem 10032.
I can do it in Java but it's a bit slow (for the Judge's 3 secs).
And I can do it in C++ but there I am not so good as in Java
so if I get into more complex details I start to lose my way.
That's why I asked this question.

Actually I posted my findings here.
http://acm.uva.es/board/viewtopic.php?f ... eb0#p99978


I will try to get my C++ logic now identical to my Java logic (as my
Java logic is more optimized and correct also). But it happens
sometimes - I have a program in Java - it is just above the edge
so I have to code again the whole program in C++ to get ACC
although the algorithm is identical.

Thanks once again.

SanPuncho
New poster
Posts: 1
Joined: Sun Apr 12, 2009 3:57 am

Re: Hash Table / Map -> C++ O(1) by key ?

Post by SanPuncho » Sun Apr 12, 2009 3:59 am

mf, it work! Thanks a lot. You solved my problem.

jekonaa
New poster
Posts: 1
Joined: Wed Mar 09, 2011 8:07 am

Re: Hash Table / Map -> C++ O(1) by key ?

Post by jekonaa » Fri Mar 11, 2011 7:58 am

Is there any software that will allow me to program in a programming language like C on a PC? I took C programming in college and I want to try my hand at it again. Is there any software that will run a C program or programs in other languages? Also, is there any language that has become very popular since the early 1990s that would be even better to learn than C?

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: Hash Table / Map -> C++ O(1) by key ?

Post by DD » Fri Mar 18, 2011 3:44 am

I just found that we can use the unordered_set and unordered_map in TR1. So we don't need to implement a hash map by our own now :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Post Reply

Return to “C++”