近两天在温习数据结构时，对散列函数与树结构数据处理优化有些想法。
首先看看散列函数的定义：在数据元素的关键字与该元素的存储位置之间建立一种对应关系，将这种关系称为散列函数（hash function）。
例如，哈希表（Hash table，也叫散列表）,就是采用散列函数将元素数据映射成数据或链表的存储位置实现的，HashMap类似，只是映射结果是key不是位置。
期待c++标准库直接支持hashtable/hashmap/hashset的容器。
1、深化树层级
场景设想，目前我们有组对象，他们都有一个唯一的编号,一个很大的编号，为了快速访问和定位，很容易设想std::map<long long key, T val>去装载他们。
但很显然易见的是当map大到一定程度时对效率影响还是挺大的，这是就需要层级结构处置他们，就可以结合散列函数做一个类似的map装载他们：
给出的示例代码：
template <class T>
class OBJMAP
{
public:
OBJMAP(){};
~OBJMAP(){};
void insert(long long key,T val)
{
data[hash(key)][key]=val;
};
T getVal(long long key)
{
std::map<long long,std::map<long long,T> >::iterator it = data.find(hash(key));
if(it != data.end()){
std::map<long long,T>::iterator it_obj = it->second.find(key);
if(it_obj != it->second.end())
{
return it_obj->second;
}
}
return T();
};
long long size()
{
long long ret = 0;
std::map<long long,std::map<long long,T> >::iterator it = data.begin();
while(it != data.end()){
ret += static_cast<long>(it->second.size());
it++;
}
return ret;
};
//其他函数类似
private:
long long hash(long long key)
{
//简单的散列表示,实际按需调整设定散列算法,例如前几位表示区域,中间几位表述类型,后面表示对象号等等
return static_cast<int>(key/PAGECOUNT);
};
private:
//
static const long long PAGECOUNT = 10000;
std::map<long long,std::map<long long,T> > data;
};
2、扁平化树层级
场景设想，有时候我们会遇到这样一种情况，我们要识别一个对象，首先需要找到他所在区域，再找到所在类型，再更具编号识别到对象，看起来应该是这样存储的：
std::map<int,std::map<int,std::map<int,T> > >,如果数据量不大，这种多层级的如果通过散列函数概念，建立区域、类型、编号到位置key一对一的映射关系[1]，或者说区域、类型、编号组合成一个key 对象[2]，就能将多层级简化
[2]示列代码：
class KeyObj
{
public:
KeyObj(int _domain,int _type, int _id)
: m_domain(_domain),m_type(_type),m_id(_id)
{
};
//
static int cmp_Key(const KeyObj &obj1, const KeyObj &obj2)
{
int diff = obj1.m_domain - obj2.m_domain;
if(diff!=0) return diff;
diff = obj1.m_type - obj2.m_type;
if(diff!=0) return diff;
diff = obj1.m_id - obj2.m_id;
if(diff!=0) return diff;
return 0;
};
int m_domain;
int m_type;
int m_id;
};
inline bool operator==(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1,obj2)==0 ; }
inline bool operator!=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1,obj2)!=0 ; }
inline bool operator>=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1,obj2)>=0 ; }
inline bool operator<=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1,obj2)<=0 ; }
inline bool operator>(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1,obj2)>0 ; }
inline bool operator<(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1,obj2)<0 ; }
template <class T>
class MyObj
{
MyObj(){};
void insert(KeyObj key,T val)
{
data[key]=val;
};
void insert(int _domain,int _type, int _id,T val)
{
insert(KeyObj(_domain,_type,_id),val);
};
T getVal(KeyObj key)
{
std::map<KeyObj,T>::iterator it = data.find(key);
if(it != data.end()){
return it->second;
}
return T();
};
//其他函数类似实现
private:
std::map<KeyObj,T> data;//由于采用map，需要KeyObj实现map的key排序准则
};
散列表在实际应用场景要比这复杂很多，主要看其引入是否能降低访问复杂度、插入复杂度等，否则宁可不用。
