Discussion:
VC9: STL: hash_set/map : hash_compare without operator < ???
(too old to reply)
mario semo
2009-05-19 09:59:15 UTC
Permalink
Hello,

I try to implement a hash_set (hash_map - both) for a class which has no
ordering relation (operator < etc), but just has an operator== and !=.

in earlier STL versions the hash_set/map template has arguments for a hash
class and for an equal_to class.

STL in VC9 does not have these arguments, but just has an hash_compare which
expects an instance of class less<Type>.

I do not expect an hash collection to sort the elements, it should just
store the elements based on an hash value and allow fast access.

i read the documentation and the docu says:

================================
In general, the elements need be merely less than comparable to establish
this order: so that, given any two elements, it may be determined either
that they are equivalent (in the sense that neither is less than the other)
or that one is less than the other. This results in an ordering between the
non-equivalent elements. On a more technical note, the comparison function
is a binary predicate that induces a strict weak ordering in the standard
mathematical sense. A binary predicate f(x,y) is a function object that has
two argument objects x and y and a return value of true or false. An
ordering imposed on a hash_set is a strict weak ordering if the binary
predicate is irreflexive, antisymmetric, and transitive and if equivalence
is transitive, where two objects x and y are defined to be equivalent when
both f(x,y) and f(y,x) are false. If the stronger condition of equality
between keys replaces that of equivalence, then the ordering becomes total
(in the sense that all the elements are ordered with respect to each other)
and the keys matched will be indiscernible from each other.
=================================

Do i understand the documentation correctly in the sense, that it is ok to
implement template less<T> simple by returning a!=b ?

i have some problems in the understanding on "antisymetric" :
"Antisymetric of a relation R on a set S, having the property that for any
two distinct elements of S, at least one is not related to the other via R."
(Wiki)
What does this mean in respect to my implementation of template less ?

below i give a small sample. is this correct?

class my_hash_compare
: public hash_compare<A,less<A>>
{
......
bool operator()(const A& _Keyval1, const A& _Keyval2) const
{
// ?????????
return _Keyval1 != _Keyval2;
}

Is this correct?

what happens with this less<A> which i pass as argument? i do not have an
operator < for objects of type A so how is this less<A> be instantiated?


Here is the complete sample:

#include <stdio.h>
#include <hash_set>
#include <hash_map>
using namespace stdext;
using namespace std;

class A
{
public:

A(int p=0) : val(p){}
virtual ~A() {};

bool operator==(A const &x) const {return val==x.val;}
bool operator!=(A const &x) const {return val!=x.val;}

void dump()
{
printf("...%p...%d...\n",this,val);
}

// assume not available!
#if 0
friend bool operator < ( const A &string1,const A &string2 )
{
return string1.val < string2.val;
}
#endif

int val;

};

class my_hash_compare
: public hash_compare<A,less<A>>
{
public:
size_t operator()(const A & _Keyval) const
{
int v = _Keyval.val;
return hash_value(v);

}
bool operator()(const A& _Keyval1, const A& _Keyval2) const
{
// ?????????
return _Keyval1 != _Keyval2;
}

};

int main(int argc,char *argv[])
{
A aA(123);
A aB(456);
A aC(99);


typedef hash_set<A,my_hash_compare > HashSet2;

HashSet2 inthashset2;

inthashset2.insert(aC);
inthashset2.insert(aB);
inthashset2.insert(aA);

HashSet2::iterator lCursor2;
HashSet2::iterator lEnd2 = inthashset2.end();
for (lCursor2 = inthashset2.begin();lCursor2!=lEnd2;lCursor2++)
{
(*lCursor2).dump();
}

return 0;
}

cl -W4 -nologo -D__WINDOWS__ -DIC_WIN -D_USE_32BIT_TIME_T /J /EHa
hash_coll1.cpp user32.lib
--
mit freundlichen Grüßen

mario semo
Ulrich Eckhardt
2009-05-19 10:37:00 UTC
Permalink
Post by mario semo
I try to implement a hash_set (hash_map - both) for a class which has no
ordering relation (operator < etc), but just has an operator== and !=.
in earlier STL versions the hash_set/map template has arguments for a
hash class and for an equal_to class.
FYI: You mean the C++ standard library, not the STL.
Post by mario semo
STL in VC9 does not have these arguments, but just has an hash_compare
which expects an instance of class less<Type>.
I do not expect an hash collection to sort the elements, it should just
store the elements based on an hash value and allow fast access.
If two values have the same hash, the container must still be able to tell
them apart. The hash containers primarily work with a hash to speed up
things but at the second level use normal comparisons to provide guarantees
that are not given by hashes.
Post by mario semo
================================
In general, the elements need be merely less than comparable to establish
this order: so that, given any two elements, it may be determined either
that they are equivalent (in the sense that neither is less than the
other) or that one is less than the other. This results in an ordering
between the non-equivalent elements. On a more technical note, the
comparison function is a binary predicate that induces a strict weak
ordering in the standard mathematical sense. A binary predicate f(x,y) is
a function object that has two argument objects x and y and a return value
of true or false. An ordering imposed on a hash_set is a strict weak
ordering if the binary predicate is irreflexive, antisymmetric, and
transitive and if equivalence is transitive, where two objects x and y are
defined to be equivalent when both f(x,y) and f(y,x) are false. If the
stronger condition of equality between keys replaces that of equivalence,
then the ordering becomes total (in the sense that all the elements are
ordered with respect to each other) and the keys matched will be
indiscernible from each other. =================================
Do i understand the documentation correctly in the sense, that it is ok to
implement template less<T> simple by returning a!=b ?
No. You can not derive an ordering from the existing comparison operators.
You could do the reverse though, because '!(a<b) and !(b<a)'
implies 'a==b'.
Post by mario semo
class my_hash_compare
: public hash_compare<A,less<A>>
{
......
bool operator()(const A& _Keyval1, const A& _Keyval2) const
{
// ?????????
return _Keyval1 != _Keyval2;
}
Is this correct?
No, see above. In addition you are not allowed to use names like _Keyval,
those are reserved.
Post by mario semo
what happens with this less<A> which i pass as argument? i do not have an
operator < for objects of type A so how is this less<A> be instantiated?
std::less<T> per default uses operator<. You can therefore simply provide
operator< to make std::less work as is. Alternatively, if T is not a type
where a less-than comparison makes sense, you can provide a functor like
std::less, though the hash_compare interface requires some additional
things, if I understand correctly.

Suggestion: as a first step, use std::set or std::map instead of hash_set or
hash_map. If you manage to provide a suitable comparator to those (and it
is easier to locate good examples on the web), adapting them to the hash
containers will be a breeze.
Post by mario semo
class my_hash_compare
: public hash_compare<A,less<A>>
{
size_t operator()(const A & _Keyval) const
{
int v = _Keyval.val;
return hash_value(v);
}
bool operator()(const A& _Keyval1, const A& _Keyval2) const
{
// ?????????
return _Keyval1 != _Keyval2;
return _Keyval1.val < _Keyval2.val;
Post by mario semo
}
};
Uli
--
C++ FAQ: http://parashift.com/c++-faq-lite

Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
mario semo
2009-05-19 12:46:20 UTC
Permalink
Hello,

first thanks for your feedback.
Post by Ulrich Eckhardt
Post by mario semo
in earlier STL versions the hash_set/map template has arguments for a
hash class and for an equal_to class.
FYI: You mean the C++ standard library, not the STL.
mh. STL=Standard Template Library, isnt it? i used Dinkumware's STL in the
last 10 years, so i thought these are equal. sft.
Note: hash_map and hash_set are not in std:: anymore, but now are in
stdext:: namespace.
Post by Ulrich Eckhardt
If two values have the same hash, the container must still be able to tell
them apart.
definitly, but therefore not an ordering relation is required. just an
equivalence relation would be necessary.
Post by Ulrich Eckhardt
Post by mario semo
Do i understand the documentation correctly in the sense, that it is ok to
implement template less<T> simple by returning a!=b ?
No. You can not derive an ordering from the existing comparison operators.
You could do the reverse though, because '!(a<b) and !(b<a)'
implies 'a==b'.
yes and no
first : i am not interested in a strong ordered set of elements. i am just
interested in a hash based mapping of elements.
2nd :
let less(a,b) == a!=b
then:
case a) a==b : less(a,b)==less(b,a)==false so: !less(a,b) && !less(b,a)
is true and so (see your comment) : implies a==b which is correct.
case b) a!=b : less(a,b)==less(b,a)==true so !less(a,b) && !less(b,a)
is false and so a!=b which is correct.
q.e.d
so, based on this implementation of less(a,b) you still can determine if
a==b or a!=b and this should be enough for a hash collection!
Post by Ulrich Eckhardt
Post by mario semo
In general, the elements need be merely less than comparable to establish
this order: so that, given any two elements, it may be determined either
that they are equivalent (in the sense that neither is less than the
other) or that one is less than the other
mh.
Post by Ulrich Eckhardt
Post by mario semo
An ordering imposed on a hash_set is a strict weak
ordering if the binary predicate is irreflexive, antisymmetric, and
transitive and if equivalence is transitive, where two objects x and y are
defined to be equivalent when both f(x,y) and f(y,x) are false
which of the relation rules are not fullfilled with my implementation?
irreflexive : yes, it is. (foreach(x): f(x,x)=false) is true.
antisymetric : yes. (forany (x,y with x!=y) f(x,y) or f(y,x) is false. )
is true
transitive in the above sense : yes. (x==y <==> f(x,y)==false &
f(y,x)==false ) is true.
Post by Ulrich Eckhardt
No, see above. In addition you are not allowed to use names like _Keyval,
those are reserved.
i always forget about this restriction. the reason was, that i copied the
implementation from <xhash> and derived my class by adding my
implementation.
Post by Ulrich Eckhardt
std::less<T> per default uses operator<. You can therefore simply provide
operator< to make std::less work as is. Alternatively, if T is not a type
where a less-than comparison makes sense, you can provide a functor like
std::less, though the hash_compare interface requires some additional
things, if I understand correctly.
thats the question.
Post by Ulrich Eckhardt
Suggestion: as a first step, use std::set or std::map instead of hash_set or
hash_map. If you manage to provide a suitable comparator to those (and it
i have to port about 100 collections from old STL to new C++ lib.and i dont
want change the application.

but even changeing from hash_map to map would not improve the situation:
from <map>:

template<class _Kty,
class _Ty,
class _Pr = less<_Kty>,
class _Alloc = allocator<pair<const _Kty, _Ty> > >
class map

i still need an instantiation of less<> my type but my objects are not
compareable.

thx.
mario.
Post by Ulrich Eckhardt
C++ FAQ: http://parashift.com/c++-faq-lite
Ulrich Eckhardt
2009-05-19 15:13:55 UTC
Permalink
Post by mario semo
Post by Ulrich Eckhardt
Post by mario semo
in earlier STL versions the hash_set/map template has arguments for a
hash class and for an equal_to class.
FYI: You mean the C++ standard library, not the STL.
mh. STL=Standard Template Library, isnt it?
It is.
Post by mario semo
i used Dinkumware's STL in the last 10 years, so i thought these are
equal.
No, you used Dinkumware's implementation of the C++ standard library. The
STL is really only the collection of containers, iterators and algorithms,
most of which have been incorporated into the C++ standard. It doesn't
include IOStreams but a rope class for large texts, for example. Also, the
two are only 99% compatible, there are small differences even in things
that exist in both.
Post by mario semo
Note: hash_map and hash_set are not in std:: anymore, but now are in
stdext:: namespace.
Right, since they are not yet part of the C++ standard, they shouldn't be
in 'std' (yet, that is...).
Post by mario semo
Post by Ulrich Eckhardt
If two values have the same hash, the container must still be able to
tell them apart.
definitly, but therefore not an ordering relation is required. just an
equivalence relation would be necessary.
Post by Ulrich Eckhardt
Post by mario semo
Do i understand the documentation correctly in the sense, that it is ok to
implement template less<T> simple by returning a!=b ?
No. You can not derive an ordering from the existing comparison
operators. You could do the reverse though, because '!(a<b) and !(b<a)'
implies 'a==b'.
yes and no
first : i am not interested in a strong ordered set of elements. i am just
interested in a hash based mapping of elements.
I'm afraid hash_map won't let you do that. It makes some assumption (as per
documentation) about the means it is given for comparison and hashing. The
fact that you don't need the ordering is irrelevant, I'm afraid.
Post by mario semo
Post by Ulrich Eckhardt
Post by mario semo
An ordering imposed on a hash_set is a strict weak
ordering if the binary predicate is irreflexive, antisymmetric, and
transitive and if equivalence is transitive, where two objects x and y are
defined to be equivalent when both f(x,y) and f(y,x) are false
which of the relation rules are not fullfilled with my implementation?
irreflexive : yes, it is. (foreach(x): f(x,x)=false) is true.
antisymetric : yes. (forany (x,y with x!=y) f(x,y) or f(y,x) is false. )
is true
Stop, I think you're missing one thing here:

forany (x,y with x!=y) f(x,y) or f(y,x) is false.
forany (x,y with x!=y) f(x,y) or f(y,x) is true.

The point is that either x<y or y<x, i.e. one comparison must yield true
while the other must yield false, provided that the elements are not equal.
Post by mario semo
i still need an instantiation of less<> my type but my objects are not
compareable.
I'm afraid that this won't be easy then. There is one thing you could try
though, but I'm not really sure if it will work: just implement operator<
to always return false. This requires that the container can store multiple
elements that compare equal (effectively it makes all elements equal to the
container, so only hashing will be used). This presents the problem that
searching for an element will yield any element, because they all look
equal to the container, even if operator== says something different.

Good luck!

Uli
--
C++ FAQ: http://parashift.com/c++-faq-lite

Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
Stephan T. Lavavej (MSFT)
2009-05-20 22:49:04 UTC
Permalink
Use VC9 SP1's unordered_set/unordered_map, which needs only hashing and
equality. It's powered by the same machinery as hash_set/hash_map, but has
a superior modern interface.

STL
Post by Ulrich Eckhardt
Post by mario semo
Post by Ulrich Eckhardt
Post by mario semo
in earlier STL versions the hash_set/map template has arguments for a
hash class and for an equal_to class.
FYI: You mean the C++ standard library, not the STL.
mh. STL=Standard Template Library, isnt it?
It is.
Post by mario semo
i used Dinkumware's STL in the last 10 years, so i thought these are
equal.
No, you used Dinkumware's implementation of the C++ standard library. The
STL is really only the collection of containers, iterators and algorithms,
most of which have been incorporated into the C++ standard. It doesn't
include IOStreams but a rope class for large texts, for example. Also, the
two are only 99% compatible, there are small differences even in things
that exist in both.
Post by mario semo
Note: hash_map and hash_set are not in std:: anymore, but now are in
stdext:: namespace.
Right, since they are not yet part of the C++ standard, they shouldn't be
in 'std' (yet, that is...).
Post by mario semo
Post by Ulrich Eckhardt
If two values have the same hash, the container must still be able to
tell them apart.
definitly, but therefore not an ordering relation is required. just an
equivalence relation would be necessary.
Post by Ulrich Eckhardt
Post by mario semo
Do i understand the documentation correctly in the sense, that it is ok to
implement template less<T> simple by returning a!=b ?
No. You can not derive an ordering from the existing comparison
operators. You could do the reverse though, because '!(a<b) and !(b<a)'
implies 'a==b'.
yes and no
first : i am not interested in a strong ordered set of elements. i am just
interested in a hash based mapping of elements.
I'm afraid hash_map won't let you do that. It makes some assumption (as per
documentation) about the means it is given for comparison and hashing. The
fact that you don't need the ordering is irrelevant, I'm afraid.
Post by mario semo
Post by Ulrich Eckhardt
Post by mario semo
An ordering imposed on a hash_set is a strict weak
ordering if the binary predicate is irreflexive, antisymmetric, and
transitive and if equivalence is transitive, where two objects x and y are
defined to be equivalent when both f(x,y) and f(y,x) are false
which of the relation rules are not fullfilled with my implementation?
irreflexive : yes, it is. (foreach(x): f(x,x)=false) is true.
antisymetric : yes. (forany (x,y with x!=y) f(x,y) or f(y,x) is false. )
is true
forany (x,y with x!=y) f(x,y) or f(y,x) is false.
forany (x,y with x!=y) f(x,y) or f(y,x) is true.
The point is that either x<y or y<x, i.e. one comparison must yield true
while the other must yield false, provided that the elements are not equal.
Post by mario semo
i still need an instantiation of less<> my type but my objects are not
compareable.
I'm afraid that this won't be easy then. There is one thing you could try
though, but I'm not really sure if it will work: just implement operator<
to always return false. This requires that the container can store multiple
elements that compare equal (effectively it makes all elements equal to the
container, so only hashing will be used). This presents the problem that
searching for an element will yield any element, because they all look
equal to the container, even if operator== says something different.
Good luck!
Uli
--
C++ FAQ: http://parashift.com/c++-faq-lite
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932
Ben Voigt [C++ MVP]
2009-05-21 14:53:32 UTC
Permalink
Post by Stephan T. Lavavej (MSFT)
Use VC9 SP1's unordered_set/unordered_map, which needs only hashing
and equality. It's powered by the same machinery as
hash_set/hash_map, but has a superior modern interface.
STL
Do what STL said.

You'll never go wrong following STL's advice unless you really messed up
describing your problem.
Scot T Brennecke
2009-05-22 06:32:08 UTC
Permalink
Well, unless he tells you to put fluffy kittens in your map, and you prefer dogs. :)
Post by Ben Voigt [C++ MVP]
Post by Stephan T. Lavavej (MSFT)
Use VC9 SP1's unordered_set/unordered_map, which needs only hashing
and equality. It's powered by the same machinery as
hash_set/hash_map, but has a superior modern interface.
STL
Do what STL said.
You'll never go wrong following STL's advice unless you really messed up describing your problem.
Ben Voigt [C++ MVP]
2009-05-22 17:07:11 UTC
Permalink
Post by Scot T Brennecke
Post by Ben Voigt [C++ MVP]
Do what STL said.
You'll never go wrong following STL's advice unless you really messed up
describing your problem.
Well, unless he tells you to put fluffy kittens in your map, and you prefer dogs. :)
But he'd never do that. C++ is a strictly no-fluff language :)
Ben Voigt [C++ MVP]
2009-05-20 16:20:58 UTC
Permalink
Post by mario semo
which of the relation rules are not fullfilled with my implementation?
irreflexive : yes, it is. (foreach(x): f(x,x)=false) is true.
antisymetric : yes. (forany (x,y with x!=y) f(x,y) or f(y,x) is
false. ) is true
You might double check on that antisymmetric one.
Post by mario semo
transitive in the above sense : yes. (x==y <==> f(x,y)==false &
f(y,x)==false ) is true.
mario semo
2009-05-20 23:17:12 UTC
Permalink
Post by Ben Voigt [C++ MVP]
Post by mario semo
which of the relation rules are not fullfilled with my implementation?
irreflexive : yes, it is. (foreach(x): f(x,x)=false) is true.
antisymetric : yes. (forany (x,y with x!=y) f(x,y) or f(y,x) is
false. ) is true
You might double check on that antisymmetric one.
Ben, Ulrich. , yes, i see. definitly my f(x,y) is symetric. f(x,y)==f(y,x)
always.

Earlier versions of (STL or Template Lib) didnt need a less(x,y) function,
but just an equal_to() function.

is there any collection in the STL (or whatever it is called) of MSVC++
which can be used for elements which does not implement an ordering? i can
compare all my elements (equal or not equal) but i cannot say which object
is less than the other object.

it looks as i still have to use my own hash table implementations :-(

mario.
Scot T Brennecke
2009-05-21 02:46:21 UTC
Permalink
If you don't care about ordering, then you don't care if you implement one arbitrarily right? Just
make up something that will be consistent and symmetric, even if you won't use it.
Post by Ben Voigt [C++ MVP]
Post by mario semo
which of the relation rules are not fullfilled with my implementation?
irreflexive : yes, it is. (foreach(x): f(x,x)=false) is true.
antisymetric : yes. (forany (x,y with x!=y) f(x,y) or f(y,x) is
false. ) is true
You might double check on that antisymmetric one.
Ben, Ulrich. , yes, i see. definitly my f(x,y) is symetric. f(x,y)==f(y,x) always.
Earlier versions of (STL or Template Lib) didnt need a less(x,y) function, but just an equal_to()
function.
is there any collection in the STL (or whatever it is called) of MSVC++ which can be used for
elements which does not implement an ordering? i can compare all my elements (equal or not equal)
but i cannot say which object is less than the other object.
it looks as i still have to use my own hash table implementations :-(
mario.
Wenwei Peng
2015-04-22 08:07:28 UTC
Permalink
在 2009年5月19日星期二 UTC+8下午5:59:15，mario semo写道：
Post by mario semo
Hello,
I try to implement a hash_set (hash_map - both) for a class which has no
ordering relation (operator < etc), but just has an operator== and !=.
in earlier STL versions the hash_set/map template has arguments for a hash
class and for an equal_to class.
STL in VC9 does not have these arguments, but just has an hash_compare which
expects an instance of class less<Type>.
I do not expect an hash collection to sort the elements, it should just
store the elements based on an hash value and allow fast access.
================================
In general, the elements need be merely less than comparable to establish
this order: so that, given any two elements, it may be determined either
that they are equivalent (in the sense that neither is less than the other)
or that one is less than the other. This results in an ordering between the
non-equivalent elements. On a more technical note, the comparison function
is a binary predicate that induces a strict weak ordering in the standard
mathematical sense. A binary predicate f(x,y) is a function object that has
two argument objects x and y and a return value of true or false. An
ordering imposed on a hash_set is a strict weak ordering if the binary
predicate is irreflexive, antisymmetric, and transitive and if equivalence
is transitive, where two objects x and y are defined to be equivalent when
both f(x,y) and f(y,x) are false. If the stronger condition of equality
between keys replaces that of equivalence, then the ordering becomes total
(in the sense that all the elements are ordered with respect to each other)
and the keys matched will be indiscernible from each other.
=================================
Do i understand the documentation correctly in the sense, that it is ok to
implement template less<T> simple by returning a!=b ?
"Antisymetric of a relation R on a set S, having the property that for any
two distinct elements of S, at least one is not related to the other via R."
(Wiki)
What does this mean in respect to my implementation of template less ?
below i give a small sample. is this correct?
class my_hash_compare
: public hash_compare<A,less<A>>
{
......
bool operator()(const A& _Keyval1, const A& _Keyval2) const
{
// ?????????
return _Keyval1 != _Keyval2;
}
Is this correct?
what happens with this less<A> which i pass as argument? i do not have an
operator < for objects of type A so how is this less<A> be instantiated?
#include <stdio.h>
#include <hash_set>
#include <hash_map>
using namespace stdext;
using namespace std;
class A
{
A(int p=0) : val(p){}
virtual ~A() {};
bool operator==(A const &x) const {return val==x.val;}
bool operator!=(A const &x) const {return val!=x.val;}
void dump()
{
printf("...%p...%d...\n",this,val);
}
// assume not available!
#if 0
friend bool operator < ( const A &string1,const A &string2 )
{
return string1.val < string2.val;
}
#endif
int val;
};
class my_hash_compare
: public hash_compare<A,less<A>>
{
size_t operator()(const A & _Keyval) const
{
int v = _Keyval.val;
return hash_value(v);
}
bool operator()(const A& _Keyval1, const A& _Keyval2) const
{
// ?????????
return _Keyval1 != _Keyval2;
}
};
int main(int argc,char *argv[])
{
A aA(123);
A aB(456);
A aC(99);
typedef hash_set<A,my_hash_compare > HashSet2;
HashSet2 inthashset2;
inthashset2.insert(aC);
inthashset2.insert(aB);
inthashset2.insert(aA);
HashSet2::iterator lCursor2;
HashSet2::iterator lEnd2 = inthashset2.end();
for (lCursor2 = inthashset2.begin();lCursor2!=lEnd2;lCursor2++)
{
(*lCursor2).dump();
}
return 0;
}
cl -W4 -nologo -D__WINDOWS__ -DIC_WIN -D_USE_32BIT_TIME_T /J /EHa
hash_coll1.cpp user32.lib
--
mit freundlichen Gr��en
mario semo
Title: The core of the core of the big data solutions -- Map
Author: pengwenwei
Email:
Language: c++
Platform: Windows, linux
Technology: Perfect hash algorithm
Level: Advanced
Description: Map algorithm with high performance
Section MFC c++ map stl
SubSection c++ algorithm
License: (GPLv3)

Download demo project - 1070 Kb
Download source - 1070 Kb

Introduction:
For the c++ program, map is used everywhere.And bottleneck of program performance is often the performance of map.Especially in the case of large data,and the business association closely and unable to realize the data distribution and parallel processing condition.So the performance of map becomes the key technology.

In the work experience with telecommunications industry and the information security industry, I was dealing with the big bottom data,especially the most complex information security industry data,all can’t do without map.

For example, IP table, MAC table, telephone number list, domain name resolution table, ID number table query, the Trojan horse virus characteristic code of cloud killing etc..

The map of STL library using binary chop, its has the worst performance.Google Hash map has the optimal performance and memory at present, but it has repeated collision probability.Now the big data rarely use a collision probability map,especially relating to fees, can’t be wrong.

Now I put my algorithms out here,there are three kinds of map,after the build is Hash map.We can test the comparison,my algorithm has the zero probability of collision,but its performance is also better than the hash algorithm, even its ordinary performance has no much difference with Google.

My algorithm is perfect hash algorithm,its key index and the principle of compression algorithm is out of the ordinary,the most important is a completely different structure,so the key index compression is fundamentally different.The most direct benefit for program is that for the original map need ten servers for solutions but now I only need one server.
Declare: the code can not be used for commercial purposes, if for commercial applications,you can contact me with QQ 75293192.
Download:
https://sourceforge.net/projects/pwwhashmap/files

Applications:
First,modern warfare can’t be without the mass of information query, if the query of enemy target information slows down a second, it could lead to the delaying fighter, leading to failure of the entire war. Information retrieval is inseparable from the map, if military products use pwwhashMap instead of the traditional map,you must be the winner.

Scond,the performance of the router determines the surfing speed, just replace open source router code map for pwwHashMap, its speed can increase ten times.
There are many tables to query and set in the router DHCP ptotocol,such as IP,Mac ,and all these are completed by map.But until now,all map are using STL liabrary,its performance is very low,and using the Hash map has error probability,so it can only use multi router packet dispersion treatment.If using pwwHashMap, you can save at least ten sets of equipment.

Third,Hadoop is recognized as the big data solutions at present,and its most fundamental thing is super heavy use of the map,instead of SQL and table.Hadoop assumes the huge amounts of data so that the data is completely unable to move, people must carry on the data analysis in the local.But as long as the open source Hadoop code of the map changes into pwwHashMap, the performance will increase hundredfold without any problems.


Background to this article that may be useful such as an introduction to the basic ideas presented:
http://blog.csdn.net/chixinmuzi/article/details/1727195

Loading...