散列函數與層級結構資料

近兩天在溫習資料結構時，對散列函數與樹結構資料處理優化有些想法。

首先看看散列函數的定義：在資料元素的關鍵字與該元素的存儲位置之間建立一種對應關系，将這種關系稱為散列函數（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);

    //

    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

    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;

        diff = obj1.m_id - obj2.m_id;

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

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

            return it->second;

    //其他函數類似實作

    std::map<KeyObj,T> data;//由于采用map，需要KeyObj實作map的key排序準則

散清單在實際應用場景要比這複雜很多，主要看其引入是否能降低通路複雜度、插入複雜度等，否則甯可不用。