一、数据结构:hash_map原理
hash_map基于hash table(哈希表)。哈希表最大的长处,就是把数据的存储和查找消耗的时间大大减少,差点儿能够看成是常数时间;而代价不过消耗比較多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比較easy也是它的特点之中的一个。
其基本原理是:使用一个下标范围比較大的数组来存储元素。能够设计一个函数(哈希函数,也叫做散列函数)。使得每个元素的keyword都与一个函数值(即数组下标。hash值)相相应,于是用这个数组单元来存储这个元素;也能够简单的理解为。依照keyword为每个元素“分类”,然后将这个元素存储在相应“类”所相应的地方。称为桶。
可是,不可以保证每一个元素的keyword与函数值是一一相应的。因此极有可能出现对于不同的元素,却计算出了同样的函数值。这样就产生了“冲突”,换句话说,就是把不同的元素分在了同样的“类”之中。 总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。
hash_map。首先分配一大片内存,形成很多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。
其插入过程是:
1. 得到key
2. 通过hash函数得到hash值
3. 得到桶号(一般都为hash值对桶数求模)
4. 存放key和value在桶内。
其取值过程是:
1. 得到key
2. 通过hash函数得到hash值
3. 得到桶号(一般都为hash值对桶数求模)
4. 比較桶的内部元素是否与key相等,若都不相等,则没有找到。
5. 取出相等的记录的value。
hash_map中直接地址用hash函数生成,解决冲突,用比較函数解决。这里能够看出,假设每一个桶内部仅仅有一个元素,那么查找的时候仅仅有一次比較。当很多桶内没有值时。很多查询就会更快了(指查不到的时候).
由此可见,要实现哈希表, 和用户相关的是:hash函数(hashcode)和比較函数(equals)。
假定哈希函数将元素正确分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。
迭代集合视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)的和成比例。
所以,假设迭代性能非常重要。则不要将初始容量设置得太高(或将载入因子设置得太低)。
HashMap 的实例有两个參数影响其性能:初始容量
载入因子
假设多个线程同一时候訪问此映射。而当中至少一个线程从结构上改动了该映射,则它必须
(结构上的改动是指加入或删除一个或多个映射关系的操作。仅改变与实例已经包括的键关联的值不是结构上的改动。)这一般通过对自然封装该映射的对象进行同步操作来完毕。假设不存在这种对象,则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
最好在创建时完毕这一操作。以防止对映射进行意外的不同步訪问。例如以下所看到的: Map m = Collections.synchronizedMap(new HashMap(...));
二、 C++中的hashMap今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比較的问题。在网上查找对应的文章可惜没有找到,但找到了http://www.stlchina.org/twiki/bin/view.pl/Main/STLDetailHashMap和http://www.cppblog.com/guojingjia2006/archive/2008/01/12/41037.aspx两篇文章对解决我的问题帮了大忙,特将其内容贴出。
hash_map类在头文件hash_map中,和全部其他的C++标准库一样,头文件没有扩展名。
例如以下声明:
#include
using namespace std;
using namespace stdext;
hash_map是一个聚合类,它继承自_Hash类,包含一个vector,一个list和一个pair,当中vector用于保存桶。list用于进行冲突处理。pair用于保存key->value结构,简要地伪码例如以下:
class hash_map
{
private:
typedef pair<_Tkey, _Tval> hash_pair;
typedef list
typedef vector
};
当然,这仅仅是一个简单模型,C++标准库的泛型模版一向以嵌套复杂而闻名。初学时看类库,无疑天书啊。微软的hash_map类还聚合了hash_compare仿函数类,hash_compare类里有聚合了less仿函数类。乱七八糟的。
以下说说用法:
一、简单变量作为索引:整形、实性、指针型
事实上指针型也就是整形,算法一样。
可是hash_map会对char, const char, wchar_t, const wchar_t做特殊处理。
这样的情况最简单。以下代码是整形演示样例:
hash_map
IntHash[1] = 123;
IntHash[2] = 456;
int val = IntHash[1];
int val = IntHash[2];
实型和指针型使用方法和整形一样,原理例如以下:
1、使用简单类型作索引声明hash_map的时候,不须要声明模版的后两个參数(最后一个參数指名hash_map节点的存储方式,默觉得pair,我觉得这就挺好。不是必需改动)。使用默认值就好。
2、对于除过字符串的其他简单类型,hash_map使用模版函数 size_t hash_value(const _Kty& _Keyval) 计算hash值,计算方法是经典的掩码异或法,自己主动溢出得到索引hash值。
微软的project师或许开了一个玩笑,这个掩码被定义为0xdeadbeef(死牛肉,抑或是某个程序猿的绰号)。
3、对于字符串指针作索引的时候,使用定类型函数inline size_t hash_value(const char _Str)或inline size_t hash_value(const wchar_t _Str)计算hash值。计算方法是取出每个字符求和。自己主动溢出得到hash值。
对于字符串型的hash索引。要注意须要自己定义less仿函数。
由于我们有理由觉得。人们使用hash表进行高速查找的预期成本要比在hash表中插入的预期成本低得多。所以插入可以比查找昂贵些;基于这个如果,hash_map在有冲突时,插入链表是进行排序插入的。这样在进行查询冲突解决的时候就行更快捷的找到须要的索引。
可是,基于泛型编程的原则,hash_map也有理由觉得每一种类型都支持使用"<"来判别两个类型值的大小,这样的设计恰好让字符串类型无所适从,众所周知。两个字符串指针的大小并不代表字符串值的大小。
见例如以下代码:
hash_map
CharHash["a"] = 123;
CharHash["b"] = 456;
char szInput[64] = "";
scanf("%s", szInput);
int val = CharHash[szInput];
终于的结果就是不管输入不论什么字符串,都无法找到相应的整数值。由于输入的字符串指针是szInput指针。和"a"或"b"字符串常量指针的大小是绝对不会同样。解决方法例如以下:
首先写一个仿函数CharLess。继承自仿函数基类binary_function(当然也能够不继承。这样写仅仅是符合标准,并且写起来比較方便,不用被类似于指针的指针和指针的引用搞晕。
struct CharLess : public binary_function
{
public:
result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
{
return(stricmp(_Left, _Right) < 0 ?
true : false);
}
};
非常好,有了这个仿函数,就能够正确的使用字符串指针型hash_map了。例如以下:
hash_map
CharHash["a"] = 123;
CharHash["b"] = 456;
char szInput[64] = "";
scanf("%s", szInput);
int val = CharHash[szInput];
如今就能够正常工作了。至此,简单类型的用法介绍完成。
二、用户自己定义类型:比方对象类型,结构体。
这样的情况比价复杂。我们先说简单的,对于C++标准库的string类。
庆幸的是。微软为basic_string(string类的基类)提供了hash方法,这使得使用string对象做索引简单了很多。
值得注意(也值得郁闷)的是。尽管支持string的hash,string类却没有重载比較运算符。所以标准的hash_compare仿函数依然无法工作。
我们继续重写less仿函数。
struct string_less : public binary_function
{
public:
result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
{
return(_Left.compare(_Right) < 0 ? true : fase);
}
};
好了,我们能够书写例如以下代码:
hash_map
StringHash["a"] = 123;
StringHash["b"] = 456;
string strKey = "a";
int val = CharHash[strKey];
这样就能够了。
对于另外的一个经常使用的字符串类CString(我觉得微软的CString比标准库的string设计要洒脱一些)更加复杂一些。非常显然,标准库里不包括对于CString的支持,但CString却重载了比較运算符(郁闷)。我们必须重写hash_compare仿函数。值得一提的是。在Virtual Stdio 2003中。CString不再是MFC的成员。而成为ATL的成员,使用#include
我没有採用重写hash_compare仿函数的策略,而不过继承了它。在模版库中的继承是没有性能损耗的,并且能让我偷一点懒。
首先重写一个hash_value函数:
inline size_t CString_hash_value(const CString& str)
{
size_t value = _HASH_SEED;
size_t size = str.GetLength();
if (size > 0) {
size_t temp = (size / 16) + 1;
size -= temp;
for (size_t idx = 0; idx <= size; idx += temp) {
value += (size_t)str[(int)idx];
}
}
return(value);
}
其次重写hash_compare仿函数:
class CString_hash_compare : public hash_compare
{
public:
size_t operator()(const CString& _Key) const
{
return((size_t)CString_hash_value(_Key));
}
bool operator()(const CString& _Keyval1, const CString& _Keyval2) const
{
return (comp(_Keyval1, _Keyval2));
}
};
上面的重载忽略了基类对于less仿函数的引入,由于CString具备比較运算符,我们能够使用默认的less仿函数,在这里映射为comp。
好了。我们能够声明新的hash_map对象例如以下:
hash_map
其余的操作一样一样的。
下来就说说对于自己定义对象的用法:首先定义
struct IHashable
{
virtual unsigned long hash_value() const = 0;
virtual bool operator < (const IHashable& val) const = 0;
virtual IHashable& operator = (const IHashable& val) = 0;
};
让我们自写的类都派生自这里,有一个标准,接下来定义我们的类:
class CTest : public IHashable
{
public:
int m_value;
CString m_message;
public:
CTest() : m_value(0)
{
}
CTest(const CTest& obj)
{
m_value = obj.m_value;
m_message = obj.m_message;
}
public:
virtual IHashable& operator = (const IHashable& val)
{
m_value = ((CTest&)val).m_value;
m_message = ((CTest&)val).m_message;
return(*this);
}
virtual unsigned long hash_value() const
{
// 这里使用类中的m_value域计算hash值。也能够使用更复杂的函数计算全部域总的hash值
return(m_value ^ 0xdeadbeef
}
virtual bool operator < (const IHashable& val) const
{
return(m_value < ((CTest&)val).m_value);
}
};
用这个类的对象做为hash索引准备工作例如以下。由于接口中规定了比較运算符,所以这里能够使用标准的less仿函数。所以这里忽略:
template
class MyHashCompare : public hash_compare<_Tkey>
{
public:
size_t operator()(const _Tkey& _Key) const
{
return(_Key.hash_value());
}
bool operator()(const _Tkey& _Keyval1, const _Tkey& _Keyval2) const
{
return (comp(_Keyval1, _Keyval2));
}
};
下来就这样写:
CTest test;
test.m_value = 123;
test.m_message = "This is a test";
MyHash[test] = 2005;
int val = MyHash[test];
能够看到正确的数字被返回。
三、关于hash_map的思考:
1、性能分析:採用了内联代码和模版技术的hash_map在效率上应该是很优秀的,但我们还须要注意例如以下几点:
经过查看代码。字符串索引会比简单类型索引速度慢,自己定义类型索引的性能则和我们选择hash的内容有非常大关系,简单为主。这是使用hash_map的基本原则。
能够通过重写hash_compair仿函数。更改里面关于桶数量的定义。假设取值合适,也能够得到更优的性能。
假设桶数量大于10。则牢记它应该是一个质数。
* 在自己定义类型是。重载的等号(或者拷贝构造)有可能成为性能瓶颈。使用对象指针最为索引将是一个好的想法。但这就必须重写less仿函数,理由同使用字符串指针作为索引。
hash_map类在头文件hash_map中,和全部其他的C++标准库一样。头文件没有扩展名。例如以下声明:
[cpp] view plaincopy
1. #include
2. usingnamespacestd;
3. usingnamespacestdext;
hash_map是一个聚合类。它继承自_Hash类,包含一个vector,一个list和一个pair,当中vector用于保存桶,list用于进行冲突处理。pair用于保存key->value结构。简要地伪码例如以下:
[cpp] view plaincopy
1. classhash_map<class_Tkey,class_Tval>
2. {
3. private:
4. typedefpair<_Tkey, _Tval> hash_pair;
5. typedeflist
6. typedefvector
7. };
当然。这仅仅是一个简单模型。C++标准库的泛型模版一向以嵌套复杂而闻名,初学时看类库,无疑天书啊。微软的hash_map类还聚合了hash_compare仿函数类,hash_compare类里又聚合了less仿函数类,乱七八糟的。
以下说说用法:
一、简单变量作为索引:整形、实性、指针型
事实上指针型也就是整形,算法一样。可是hash_map会对char, const char, wchar_t, const wchar_t做特殊处理。
这样的情况最简单。以下代码是整形演示样例:
[cpp] view plaincopy
1. hash_map<int,int> IntHash;
2. IntHash[1] = 123;
3. IntHash[2] = 456;
4. intval = IntHash[1];
5. intval = IntHash[2];
实型和指针型使用方法和整形一样,原理例如以下:
1、使用简单类型作索引声明hash_map的时候。不须要声明模版的后两个參数(最后一个參数指名hash_map节点的存储方式。默觉得pair。我觉得这就挺好。不是必需改动)。使用默认值就好。
2、对于除过字符串的其他简单类型,hash_map使用模版函数 size_t hash_value(const _Kty& _Keyval) 计算hash值,计算方法是经典的掩码异或法,自己主动溢出得到索引hash值。微软的project师或许开了一个玩笑。这个掩码被定义为0xdeadbeef(死牛肉。抑或是某个程序猿的绰号)。
3、对于字符串指针作索引的时候。使用定类型函数inline size_t hash_value(const char _Str)或inline size_t hash_value(const wchar_t _Str)计算hash值。计算方法是取出每个字符求和,自己主动溢出得到hash值。对于字符串型的hash索引,要注意须要自己定义less仿函数。
由于我们有理由觉得,人们使用hash表进行高速查找的预期成本要比在hash表中插入的预期成本低得多,所以插入可以比查找昂贵些;基于这个如果,hash_map在有冲突时,插入链表是进行排序插入的,这样在进行查询冲突解决的时候就行更快捷的找到须要的索引。
可是,基于泛型编程的原则,hash_map也有理由觉得每一种类型都支持使用"<"来判别两个类型值的大小,这样的设计恰好让字符串类型无所适从,众所周知。两个字符串指针的大小并不代表字符串值的大小。
见例如以下代码:
[cpp] view plaincopy
1. hash_map<constchar*,int> CharHash;
2. CharHash["a"] = 123;
3. CharHash["b"] = 456;
4. charszInput[64] ="";
5. scanf("%s", szInput);
6. intval = CharHash[szInput];
终于的结果就是不管输入不论什么字符串,都无法找到相应的整数值。由于输入的字符串指针是szInput指针。和"a"或"b"字符串常量指针的大小是绝对不会同样。
解决方法例如以下:
首先写一个仿函数CharLess。继承自仿函数基类binary_function(当然也能够不继承,这样写仅仅是符合标准,并且写起来比較方便,不用被类似于指针的指针和指针的引用搞晕。
[cpp] view plaincopy
1. structCharLess :publicbinary_function<constchar,constchar,bool>
2. {
3. public:
4. result_type operator()(constfirst_argument_type& _Left,constsecond_argument_type& _Right)const
5. {
6. return(stricmp(_Left, _Right) < 0 ?true:false);
7. }
8. };
非常好,有了这个仿函数。就能够正确的使用字符串指针型hash_map了。例如以下:
[cpp] view plaincopy
1. hash_map<constchar,int, hash_compare<constchar, CharLess> > CharHash;
2. CharHash["a"] = 123;
3. CharHash["b"] = 456;
4. charszInput[64] ="";
5. scanf("%s", szInput);
6. intval = CharHash[szInput];
如今就能够正常工作了。
至此。简单类型的用法介绍完成。
二、用户自己定义类型:比方对象类型。结构体。
这样的情况比价复杂,我们先说简单的,对于C++标准库的string类。
庆幸的是,微软为basic_string(string类的基类)提供了hash方法,这使得使用string对象做索引简单了很多。值得注意(也值得郁闷)的是。尽管支持string的hash,string类却没有重载比較运算符,所以标准的hash_compare仿函数依然无法工作。我们继续重写less仿函数。
[cpp]view plaincopy
- structstring_less :publicbinary_function<conststring,conststring,bool>
- {
- public:
- result_type operator()(constfirst_argument_type& _Left,constsecond_argument_type& _Right)const
- {
- return(_Left.compare(_Right) < 0 ?true: fase);
- }
- };
好了,我们能够书写例如以下代码:
[cpp] view plaincopy - hash_map
\int\\, hash_compare\ > StringHash; - StringHash["a"] = 123;
- StringHash["b"] = 456;
- string strKey ="a";
- intval = CharHash[strKey];
这样就能够了。
对于另外的一个经常使用的字符串类CString(我觉得微软的CString比标准库的string设计要洒脱一些)更加复杂一些。非常显然。标准库里不包括对于CString的支持。但CString却重载了比較运算符(郁闷)。我们必须重写hash_compare仿函数。值得一提的是。在Virtual Stdio 2003中,CString不再是MFC的成员,而成为ATL的成员。使用#include
首先重写一个hash_value函数:
[cpp] view plaincopy
1. inlinesize_tCString_hash_value(constCString& str)
2. {
3. size_tvalue = _HASH_SEED;
4. size_tsize = str.GetLength();
5. if(size > 0) {
6. size_ttemp = (size / 16) + 1;
7. size -= temp;
8. for(size_tidx = 0; idx <= size; idx += temp) {
9. value += (size_t)str[(int)idx];
10. }
11. }
12. return(value);
13. }
其次重写hash_compare仿函数:
[cpp] view plaincopy
1. classCString_hash_compare :publichash_compare
2. {
3. public:
4. size_toperator()(constCString& _Key)const
5. {
6. return((size_t)CString_hash_value(_Key));
7. }
8.
9. booloperator()(constCString& _Keyval1,constCString& _Keyval2)const
10. {
11. return(comp(_Keyval1, _Keyval2));
12. }
13. };
上面的重载忽略了基类对于less仿函数的引入。由于CString具备比較运算符。我们能够使用默认的less仿函数。在这里映射为comp。好了,我们能够声明新的hash_map对象例如以下:
[cpp] view plaincopy
1. hash_map
其余的操作一样一样的。
下来就说说对于自己定义对象的用法:首先定义
[cpp] view plaincopy
1. structIHashable
2.
3. virtualunsignedlonghash_value()const= 0;
4. virtualbooloperator < (constIHashable& val)const= 0;
5. virtualIHashable& operator = (constIHashable& val) = 0;
6. ;
让我们自写的类都派生自这里,有一个标准,接下来定义我们的类:
[cpp] view plaincopy
1. classCTest :publicIHashable
2. {
3. public:
4. intm_value;
5. CString m_message;
6. public:
7. CTest() : m_value(0) {}
8.
9. CTest(constCTest& obj)
10. {
11. m_value = obj.m_value;
12. m_message = obj.m_message;
13. }
14. public:
15. virtualIHashable& operator = (constIHashable& val) {
16. m_value = ((CTest&)val).m_value;
17. m_message = ((CTest&)val).m_message;
18. return(this);
19. }
20.
21. virtualunsignedlonghash_value()const{
22. // 这里使用类中的m_value域计算hash值,也能够使用更复杂的函数计算全部域总的hash值
23. return(m_value ^ 0xdeadbeef
24. }
25.
26. virtualbooloperator < (constIHashable& val)const{
27. return(m_value < ((CTest&)val).m_value);
28. }
29. };
用这个类的对象做为hash索引准备工作例如以下,由于接口中规定了比較运算符,所以这里能够使用标准的less仿函数。所以这里忽略:
[cpp] view plaincopy
1. template<class_Tkey>
2. classMyHashCompare :publichash_compare<_Tkey>
3. {
4. public:
5. size_toperator()(const_Tkey& _Key)const{
6. return(_Key.hash_value());
7. }
8.
9.
10. booloperator()(const_Tkey& _Keyval1,const_Tkey& _Keyval2)const{
11. return(comp(_Keyval1, _Keyval2));
12. }
13. };
14.
下来就这样写:
[cpp]* view plaincopy
1. CTest test;
2. test.m_value = 123;
3. test.m_message ="This is a test";
4.
5.
6. MyHash[test] = 2005;
7.
8.
9. intval = MyHash[test];
能够看到正确的数字被返回。
三、关于hash_map的思考:
1、性能分析:採用了内联代码和模版技术的hash_map在效率上应该是很优秀的。但我们还须要注意例如以下几点:
经过查看代码。字符串索引会比简单类型索引速度慢,自己定义类型索引的性能则和我们选择hash的内容有非常大关系,简单为主,这是使用hash_map的基本原则。
能够通过重写hash_compair仿函数,更改里面关于桶数量的定义。假设取值合适,也能够得到更优的性能。假设桶数量大于10,则牢记它应该是一个质数。
* 在自己定义类型是,重载的等号(或者拷贝构造)有可能成为性能瓶颈。使用对象指针最为索引将是一个好的想法,但这就必须重写less仿函数。理由同使用字符串指针作为索引。
自己使用上面的方法成功攻克了使用PTCHAR作为Key的使用。其解决方法例如以下:
[cpp] view plaincopy
1. inlinesize_tPTCHAR_hash_value(constPTCHARstr)
2. {
3. size_tvalue = _HASH_SEED;
4. size_tsize = _tcslen(str);
5. if(size > 0) {
6. size_ttemp = (size/16) + 1;
7. size -= temp;
8. for(size_tidx=0; idx<=size; idx+=temp) {
9. value += (size_t)str[(int)idx];
10. }
11. }
12. returnvalue;
13. }
14. classPTCHAR_hash_compare :publicstdext::hash_compare<PTCHAR>
15. {
16. public:
17. size_toperator()(constPTCHAR_Key)const{
18. return((size_t)PTCHAR_hash_value(_Key));
19. }
20. booloperator()(constPTCHAR_Keyval1,constPTCHAR_Keyval2)const{
21. return(_tcscmp(_Keyval1, _Keyval2));
22. }
23. };
24. stdext::hash_map<PTCHAR,long, PTCHAR_hash_compare > myHash;
25.
原文链接: https://www.cnblogs.com/llguanli/p/7220680.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/257236
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!