Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Namespace Members | Compound Members | File Members

# HashMap.h

Go to the documentation of this file.

    00001 //------------------------------------------------------------------------------
    00002 // Lamp : Open source game middleware
    00003 // Copyright (C) 2004  Junpei Ohtani ( Email : junpee@users.sourceforge.jp )
    00004 //
    00005 // This library is free software; you can redistribute it and/or
    00006 // modify it under the terms of the GNU Lesser General Public
    00007 // License as published by the Free Software Foundation; either
    00008 // version 2.1 of the License, or (at your option) any later version.
    00009 //
    00010 // This library is distributed in the hope that it will be useful,
    00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00013 // Lesser General Public License for more details.
    00014 //
    00015 // You should have received a copy of the GNU Lesser General Public
    00016 // License along with this library; if not, write to the Free Software
    00017 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    00018 //------------------------------------------------------------------------------
    00019
    00020 /** @file
    00021  * ハッシュマップヘッダ
    00022  * @author Junpee
    00023  */
    00024
    00025 #ifndef HASH_MAP_H_
    00026 #define HASH_MAP_H_
    00027
    00028 // アレイリスト
    00029 #include <Core/Container/ArrayList.h>
    00030
    00031 namespace Lamp{
    00032
    00033 //------------------------------------------------------------------------------
    00034 /**
    00035  * ハッシュマップ
    00036  *
    00037  * このクラスは継承しないで下さい。
    00038  * HashKeyは以下の4つのメソッドを実装している必要があります。<br>
    00039  * HashKey();<br>
    00040  * HashKey& operator =(const HashKey& copy);<br>
    00041  * bool equals(const HashKey& compare) const;<br>
    00042  * u_int getHashCode() const;<br>
    00043  * ValueTypeは通常はポインタ型を指定して下さい。
    00044  */
    00045 template <typename HashKey, typename ValueType>
    00046 class HashMap{
    00047 public:
    00048     //--------------------------------------------------------------------------
    00049     /**
    00050      * ハッシュデータ
    00051      *
    00052      * 配列取り出し用クラス
    00053      */
    00054     template <typename HashKey, typename ValueType>
    00055     class HashData{
    00056     public:
    00057         /// デフォルトコンストラクタ
    00058         HashData() : value_(NULL){}
    00059
    00060         /// キー値
    00061         HashKey key_;
    00062         /// 値
    00063         ValueType value_;
    00064     };
    00065
    00066     //--------------------------------------------------------------------------
    00067     // 構築、破棄
    00068     //--------------------------------------------------------------------------
    00069     /**
    00070      * コンストラクタ
    00071      * @param capacity 初期容量
    00072      * @param loadFactor 負荷係数
    00073      */
    00074     explicit HashMap(int capacity = 16, float loadFactor = 0.75f) :
    00075         capacity_(capacity), loadFactor_(loadFactor), count_(0){
    00076         Assert(capacity_ > 0);
    00077         maxSize_ = (int)(capacity_ * loadFactor_);
    00078         array_ = new HashItem<HashKey, ValueType>[capacity_];
    00079     }
    00080
    00081     /**
    00082      * デストラクタ
    00083      */
    00084     ~HashMap(){
    00085         Assert(count_ == 0);
    00086         delete[] array_;
    00087     }
    00088
    00089     /**
    00090      * クローン
    00091      * @param destination クローン先ハッシュマップ
    00092      */
    00093     void cloneTo(HashMap* destination) const{
    00094         Assert(destination->getCount() == 0);
    00095         destination->loadFactor_ = loadFactor_;
    00096         destination->setCapacity(capacity_);
    00097         for(int i = 0; i < capacity_; i++){
    00098             HashItem<HashKey, ValueType>* item = &array_[i];
    00099             // 第一要素が空だった
    00100             if(item->value_ == NULL){ continue; }
    00101             while(true){
    00102                 destination->put(item->key_, item->value_);
    00103                 item = item->next_;
    00104                 if(item == NULL){ break; }
    00105             }
    00106         }
    00107     }
    00108
    00109     //--------------------------------------------------------------------------
    00110     // 情報の取得
    00111     //--------------------------------------------------------------------------
    00112     /**
    00113      * 要素数の取得
    00114      * @return 要素数
    00115      */
    00116     int getCount() const{ return count_; }
    00117
    00118     /**
    00119      * 空かどうか
    00120      * @return 空ならtrueを返す
    00121      */
    00122     bool isEmpty() const{ return (count_ == 0); }
    00123
    00124     /**
    00125      * 要素の取得
    00126      * @param key 取得する要素のキー
    00127      * @return 要素。該当するキーが無ければNULL。
    00128      */
    00129     ValueType get(const HashKey& key) const{
    00130         // ハッシュ値の割り出し
    00131         u_int hashCode = key.getHashCode();
    00132         HashItem<HashKey, ValueType>* item;
    00133         item = &array_[hashCode % capacity_];
    00134         if(item->value_ == NULL){ return NULL; }
    00135         while(true){
    00136             if(item->key_.equals(key)){ return item->value_; }
    00137             item = item->next_;
    00138             if(item == NULL){ return NULL; }
    00139         }
    00140     }
    00141
    00142     /**
    00143      * 容量の取得
    00144      * @return 容量
    00145      */
    00146     int getCapacity() const{ return capacity_; }
    00147
    00148     /**
    00149      * 負荷係数の取得
    00150      * @return 負荷係数
    00151      */
    00152     float getLoadFactor() const{ return loadFactor_; }
    00153
    00154     /**
    00155      * 配列の取得
    00156      * @param arrayList [out]データを格納するArrayList
    00157      */
    00158     void toArray(ArrayList< HashData<HashKey, ValueType> >* arrayList) const{
    00159         if(count_ == 0){ return; }
    00160         arrayList->clear(count_);
    00161         for(int i = 0; i < capacity_; i++){
    00162             HashItem<HashKey, ValueType>* item = &array_[i];
    00163             if(item->value_ == NULL){ continue; }
    00164             while(true){
    00165                 HashData<HashKey, ValueType> data;
    00166                 data.key_ = item->key_;
    00167                 data.value_ = item->value_;
    00168                 arrayList->add(data);
    00169                 item = item->next_;
    00170                 if(item == NULL){ break; }
    00171             }
    00172         }
    00173     }
    00174
    00175     //--------------------------------------------------------------------------
    00176     // ハッシュマップの変更
    00177     //--------------------------------------------------------------------------
    00178     /**
    00179      * 要素の追加
    00180      * @param key ハッシュキー。同じキーは登録不可。
    00181      * @param value 格納する値。NULLは不可。
    00182      * @return 成功すればture、すでに同じ要素があればfalseを返し、値は追加されない。
    00183      */
    00184     bool put(HashKey key, ValueType value){
    00185         Assert(value != NULL);
    00186         if(value == NULL){ return false; }
    00187         // 配列のリサイズ
    00188         if(count_ + 1 > maxSize_){
    00189             int newCapacity = capacity_ * 2;
    00190             while(true){
    00191                 maxSize_ = (int)(newCapacity * loadFactor_);
    00192                 if(count_ + 1 <= maxSize_){ break; }
    00193                 newCapacity *= 2;
    00194             }
    00195             setCapacity(newCapacity);
    00196         }
    00197         // ハッシュ値の割り出し
    00198         u_int hashCode = key.getHashCode();
    00199         // ハッシュ値にあたる要素が空なら代入して終わり。
    00200         HashItem<HashKey, ValueType>* item;
    00201         item = &array_[hashCode % capacity_];
    00202         if(item->value_ == NULL){
    00203             item->key_ = key;
    00204             item->value_ = value;
    00205             count_++;
    00206             return true;
    00207         }
    00208         while(true){
    00209             // 同値チェック
    00210             if(item->key_.equals(key)){ return false; }
    00211             // アロケーションして追加
    00212             if(item->next_ == NULL){
    00213                 HashItem<HashKey, ValueType>* newItem;
    00214                 newItem = new HashItem<HashKey, ValueType>(key, value);
    00215                 item->next_ = newItem;
    00216                 count_++;
    00217                 return true;
    00218             }
    00219             item = item->next_;
    00220         }
    00221     }
    00222
    00223     /**
    00224      * 要素の削除
    00225      * @param key ハッシュキー
    00226      * @return 削除された値。見つからなければNULL
    00227      */
    00228     ValueType remove(HashKey key){
    00229         // ハッシュ値の割り出し
    00230         u_int hashCode = key.getHashCode();
    00231         HashItem<HashKey, ValueType>* item = &array_[hashCode % capacity_];
    00232         if(item->value_ == NULL){ return NULL; }
    00233         // 第一要素の削除
    00234         ValueType returnValue = NULL;
    00235         if(item->key_.equals(key)){
    00236             returnValue = item->value_;
    00237             if(item->next_ == NULL){
    00238                 // 1番目の要素だけを削除
    00239                 item->value_ = NULL;
    00240                 item->key_ = HashKey();
    00241             }else{
    00242                 // 2番目の要素を1番目に代入して削除
    00243                 HashItem<HashKey, ValueType>* nextItem = item->next_;
    00244                 *item = *nextItem;
    00245                 delete nextItem;
    00246             }
    00247             count_--;
    00248             return returnValue;
    00249         }
    00250         // 第二要素以降の削除
    00251         HashItem<HashKey, ValueType>* nextItem;
    00252         while(true){
    00253             nextItem = item->next_;
    00254             if(nextItem == NULL){ return NULL; }
    00255             if(nextItem->key_.equals(key)){
    00256                 returnValue = nextItem->value_;
    00257                 item->next_ = nextItem->next_;
    00258                 delete nextItem;
    00259                 count_--;
    00260                 return returnValue;
    00261             }
    00262             item = nextItem;
    00263         }
    00264     }
    00265
    00266     /**
    00267      * クリア
    00268      */
    00269     void clear(){
    00270         for(int i = 0; i < capacity_; i++){
    00271             HashItem<HashKey, ValueType>* item = &array_[i];
    00272             HashItem<HashKey, ValueType>* nextItem = item->next_;
    00273             // 第一要素が空だった
    00274             if(item->value_ == NULL){ continue; }
    00275             item->key_ = HashKey();
    00276             item->value_ = NULL;
    00277             item->next_ = NULL;
    00278             count_--;
    00279             while(true){
    00280                 item = nextItem;
    00281                 if(item == NULL){ break; }
    00282                 nextItem = item->next_;
    00283                 item->key_ = HashKey();
    00284                 item->value_ = NULL;
    00285                 item->next_ = NULL;
    00286                 count_--;
    00287                 delete item;
    00288             }
    00289         }
    00290     }
    00291
    00292     /**
    00293      * 容量の設定
    00294      * @param capacity 設定するキャパシティ
    00295      */
    00296     void setCapacity(int capacity){
    00297         HashMap<HashKey, ValueType*> hashMap(capacity, loadFactor_);
    00298         int listSize = count_, listCounter = 0;
    00299         HashKey* keyList = new HashKey[listSize];
    00300         ValueType* valueList = new ValueType[listSize];
    00301         for(int i = 0; i < capacity_; i++){
    00302             HashItem<HashKey, ValueType>* item = &array_[i];
    00303             if(item->value_ == NULL){ continue; }
    00304             while(true){
    00305                 keyList[listCounter] = item->key_;
    00306                 valueList[listCounter] = item->value_;
    00307                 listCounter++;
    00308                 item = item->next_;
    00309                 if(item == NULL){ break; }
    00310             }
    00311         }
    00312         clear();
    00313         delete[] array_;
    00314         capacity_ = capacity;
    00315         maxSize_ = (int)(capacity_ * loadFactor_);
    00316         array_ = new HashItem<HashKey, ValueType>[capacity_];
    00317         // キャパシティの拡張が起こる可能性がある
    00318         for(int i = 0;i < listSize;i++){ put(keyList[i], valueList[i]); }
    00319         delete[] keyList;
    00320         delete[] valueList;
    00321     }
    00322
    00323     /**
    00324      * トリム
    00325      */
    00326     void trim(){
    00327         int newCapacity = 1, maxSize;
    00328         while(true){
    00329             maxSize = (int)(newCapacity * loadFactor_);
    00330             if(count_ <= maxSize){ break; }
    00331             newCapacity *= 2;
    00332         }
    00333         setCapacity(newCapacity);
    00334     }
    00335
    00336     //--------------------------------------------------------------------------
    00337 #ifdef _DEBUG
    00338     /**
    00339      * デバッグ用出力
    00340      * @param detail 詳細出力
    00341      */
    00342     void debugPrint(bool detail){
    00343         DebugOut("\nCapacity %d, LoadFactor %.2f MaxSize %d Size %d ",
    00344             capacity_, loadFactor_, maxSize_, count_);
    00345         if(detail){ DebugOut("\n"); }
    00346         int allocCount = 0;
    00347         for(int i = 0;i < capacity_;i++){
    00348             HashItem<HashKey, ValueType>* item = &array_[i];
    00349             int count = 0;
    00350             // 全表示
    00351             while(true){
    00352                 count++;
    00353                 if(count >= 2){ allocCount++; }
    00354                 if(detail){
    00355                     if(item->value_ != NULL){ DebugOut("*"); }
    00356                 }
    00357                 if(item->next_ == NULL){ break; }
    00358                 item = item->next_;
    00359             }
    00360             if(detail){ DebugOut("\n"); }
    00361         }
    00362         DebugOut("allocCount %d allocRate %.1f%%\n",
    00363             allocCount, (float)allocCount / count_ * 100.f);
    00364     }
    00365 #endif
    00366
    00367 private:
    00368     //--------------------------------------------------------------------------
    00369     // ハッシュアイテム
    00370     template <typename HashKey, typename ValueType>
    00371     class HashItem{
    00372     friend class HashMap;
    00373     public:
    00374         // デフォルトコンストラクタ
    00375         HashItem() : key_(), value_(NULL), next_(NULL){}
    00376
    00377         // 初期値有りコンストラクタ
    00378         HashItem(HashKey key, ValueType value) :
    00379             key_(), value_(value), next_(NULL){
    00380             key_ = key;// コピーコンストラクタの実装義務を無くす。
    00381         }
    00382
    00383         // 代入演算子
    00384         HashItem& operator =(const HashItem& copy){
    00385             key_ = copy.key_;
    00386             value_ = copy.value_;
    00387             next_ = copy.next_;
    00388             return *this;
    00389         }
    00390
    00391         // キー値
    00392         HashKey key_;
    00393         // 値
    00394         ValueType value_;
    00395         // 次のアイテム
    00396         HashItem* next_;
    00397     };
    00398
    00399     //--------------------------------------------------------------------------
    00400     // コピーコンストラクタの隠蔽
    00401     HashMap(const HashMap& copy);
    00402
    00403     // 代入コピーの隠蔽
    00404     void operator =(const HashMap& copy);
    00405
    00406     //--------------------------------------------------------------------------
    00407     // 容量
    00408     int capacity_;
    00409     // 負荷係数
    00410     float loadFactor_;
    00411     // 最大サイズ
    00412     int maxSize_;
    00413     // サイズ
    00414     int count_;
    00415     // ハッシュ配列
    00416     HashItem<HashKey, ValueType>* array_;
    00417 };
    00418
    00419 //------------------------------------------------------------------------------
    00420 } // End of namespace Lamp
    00421 #endif // End of HASH_MAP_H_
    00422 //------------------------------------------------------------------------------