C++ map collision resolution as java HashMap

Question

I have already working, good and fast algorithm in java that uses Hashmap.

Hashmap<Point, Float>map; //point object as a key. no nulls objects in key and values

Point class has a following structure

static public class Point {
    private int x;
    private int y;

    int hashCode() {
     int hash = 5;
     hash = 59 * hash + this->x;
     hash = 59 * hash + this->y;
     return hash;
    }
    boolean equals(Point p){
     return x==p.x&&y==p.y;
    }
}

I should reimplement my algorithm in c++. I decided to use c++ stl hashmap.

I just copied Point class with small changes according to c++ syntax, and wrote map in following way:

std::map<long, float>mymap;//key-hashcode of the point
mymap[point.hashcode()]=45;//example of using

But I have found, that sometimes c++ version of algorithm returns wrong result. After a lot of debugging, I found, that some points returns equal hashcodes:

Point(8,89).hashcode()==17966; //x=8,y=89
Point(9,30).hashcode()==17966; //x=9,y=30

java Hashmap resolves this conflict with equals function inside hashmap as a hash conflict resolution, but I do not know, how to implement this in c++... May be I should write better hash function, but I think this will not fully resolve my problem, only remove some collision, but will create new. Can you help me?

UPD:

added to Point class the following code:

bool operator <(const Point& rhs) const
{
    return getX()<rhs.getX()|| (!(rhs.getX()<getX()) && getY()<rhs.getY()); 
}

and declared map as following:

std::map<Point, float>mymap;

and all started to work as intended

`std::map` is in fact a `TreeMap`, what you want if you want a `HashMap` is `std::unordered_map`. So basically the accepted answer is mostly wrong. It is however right in that you should be using point as its key type, not hashcode explicitly. (Or pointer to point and provide custom hashing function, those are just implementation details that depend on what are you trying to achieve) — Xarn, Feb 17 '14 at 11:05
Thank you, Xarn. Now I am understand my mistake.In my task it is not so important to use specifically hashmap I will happily use treemap or another associative array, because I need just fast search inside array of keys, that is why **cyon** answer is worked for me. — Dmitry, Feb 17 '14 at 13:41

cyon · Answer 1 · 2014-02-17T11:16:13.653

4

Like in Java you should use Points as keys not the hashcodes of Points:

std::map<pair<long, long>, float>mymap;
mymap.insert(std::make_pair(8,89), 0.1);

The struct pair is ideal to represent a simple point and it overloads all the comparison operators that map uses to locate keys.

You might want to typedef the pair to make it more clear what is being stored in the map:

typedef pair<long, long> Point;

edited Feb 17 '14 at 11:16

answered Feb 17 '14 at 09:34

cyon

9,340
4
22
26

Thanks. Unfortunately I cannot use pair<> class, because in near future I should add some another fields to Point class(weight...) but when I made Point object as a key, all my problems gone)) – Dmitry Feb 17 '14 at 10:04
when you made point object as key.. how mymap[point.hashcode()]=45; is working then – Connecting life with Android Mar 02 '15 at 14:09
@ConnectinglifewithAndroid When point is key then you update the map using `mymap[point] = 45`. – cyon Mar 02 '15 at 14:28
@ConnectinglifewithAndroid If you use `std::map` then you don't use it because that map uses comparison operators. If you want to use hashcodes look at `unordered_map` – cyon Mar 02 '15 at 15:03
yes I know but i am interested to know how dmity solved this problem – Connecting life with Android Mar 02 '15 at 15:09

score 2 · Accepted Answer · answered May 06 '17 at 06:50

Take a look at https://github.com/DeepFound/deep_platform - deep_platform is a C++ framework with a Java look and Feel. It has a HashMap interface/behavior like that found in Java.

With this framework, a direct mapping can be implemented...

#include "cxx/lang/Float.h"
#include "cxx/util/HashMap.cxx"

using namespace cxx::lang;
using namespace cxx::util;

class Point : public Object {

    private:
            int x;
            int y;

    public:
            Point(int x, int y):
                    x(x), y(y) {
            }

            long hashCode(void) const {
                    long hash = 5;
                    hash = 59 * hash + this->x;
                    hash = 59 * hash + this->y;
                    return hash;
            }

            boolean equals(const Object* obj) const {
                    Point* p = (Point*) obj;
                    return x==p->x&&y==p->y;
            }
};

template class HashMap<Point*,Float*>;

int main(int argc, char** argv) {
    HashMap<Point*, Float*> map;

    // add
    for (int i = 0; i < 5; i++) {
            Point* p = new Point(i,i);
            Float* f = new Float(i);
            map.put(p, f);
    }

    // find
    for (int i = 0; i < 5; i++) {
            Point p(i,i);
            if (map.get(&p) != null) {
                    // found
            }
    }

    return 0;
}

It's best, if moving to C++, to move all the way, and use the C++ library's hash map, which is unordered_map (http://www.cplusplus.com/reference/unordered_map/unordered_map/). — Graham Asher, May 06 '17 at 11:46

score 1 · Answer 3 · edited May 23 '17 at 11:47

1

std::map<> isn't a HashTable map, it's a tree map afair. There's hash_map class, but it's not in the C++ Standard yet. See Is hash_map part of the STL?

edited May 23 '17 at 11:47

Community

1
1

answered Feb 17 '14 at 09:33

user3159253

16,836
3
30
56

marcinj · Answer 4 · 2014-02-17T10:14:21.367

Since c++11, you can use std::unordered_map, below is simple example. Your Java equals method in c++ is bool Point::operator==

http://coliru.stacked-crooked.com/a/1260a66b7f350816

#include <iostream>
#include <unordered_map>

struct Point
{
  Point(int px, int py) : x(px), y(py) {}
  int x,y;

  bool operator==(const Point &other) const
  { return (x == other.x
            && y == other.y);
  }
};

namespace std {
  template <>
  struct hash<Point>
  {
    std::size_t operator()(const Point& k) const
    {
      return (k.x + k.y); // silly function, just to produce equal hashes below
    }
  };
}
int main()
{
   std::unordered_map<Point,std::string> mmap = {
    { {0,1}, "example"},
    { {1,0}, "another"}
   };   
   std::cout << mmap.size() << std::endl;   // outputs 2

   std::unordered_map<Point,std::string> mmap2 = {
    { {0,1}, "example"},
    { {0,1}, "another"}
   };   
   std::cout << mmap2.size() << std::endl;   // outputs 1
   return 0;
}

C++ map collision resolution as java HashMap

4 Answers4