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

[Sedefcho]

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)

[Sedefcho]

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]

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; }
};

[Sedefcho]

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]

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

[jekonaa]

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]

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