프로그래밍2008/01/18 13:51

hash string

map 을 사용하다 보면 오브젝트를 스트링으로 얻어올 때가 있는데

string 비교를 하게 된다..

좀더 빠르게 하기 위해

string 를 해쉬코드로 바꿔서 오브젝트에 저장하고

비교해 써먹으면 될것 같다.


    unsigned long
    hash(unsigned char *str)
    {
        unsigned long hash = 5381;
        int c;

        while (c = *str++)
            hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

        return hash;
    }




class GameObject
{
public:
	   void SetName( const char*Name )
	   {
	   	   m_Name = Name;
	   	   m_HashCode = GetHashCode( Name );
	   }
	   inline virtual bool operator < ( const GameObject& Obj ) const
	   {
	   	   if( m_HashCode != Obj.m_HashCode )
	   	   	   return m_HashCode < Obj.m_HashCode;
	   	   return strcmp( m_Name, Obj.m_Name ) < 0;
	   }
...
}

unsigned long GetHashCode( const char* pString )
{
	   unsigned long i,len;
	   unsigned long ch;
	   unsigned long result;
	   
	   len     = strlen( pString );
	   result = 5381;
	   for( i=0; i<len; i++ )
	   {
	   	   ch = (unsigned long)pString[i];
	   	   result = ((result<< 5) + result) + ch; // hash * 33 + ch
	   }	  

	   return result;
}


notice !
생성된 hash code 가 unique 하지 않을 수 있다.



http://www.cse.yorku.ca/~oz/hash.html
http://www.gpgstudy.com/forum/viewtopic.php?t=795&highlight=hash+map
http://www.ddj.com/184409859

'프로그래밍' 카테고리의 다른 글

Memory Pool / Management 튜토리얼  (0) 2008/07/30
Freetype 2.0 폰트라이브러리 필터링  (0) 2008/07/22
Directshow strmbase.lib strmbasd.lib  (0) 2008/02/04
freetype dxfont 간 성능 비교..  (0) 2008/01/23
STL Vector  (0) 2008/01/22
hash string  (0) 2008/01/18
Texture Stage Argument  (0) 2008/01/18
FreeType2 library ft_pixel_mode_mono  (0) 2008/01/18
FreeType2 Library Metrics pixel 포맷  (0) 2008/01/18
freetype library  (0) 2007/12/14
rand(), srand(), RAND_MAX  (2) 2007/11/10
Posted by hangenie(한진희)의 Music 블로그 Hangenie
TAG ,
Trackback 0 Comment 0

댓글을 달아 주세요