随笔 - 3  文章 - 2  trackbacks - 0
<2024年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

留言簿

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

stdext::hash_map使用字符串(const char*)做key的话,不是只指定一个compare函数难么简单,要给定一个结构体,其包括hash函数,compare函数,以及“桶设定”

struct StringCompare 
{
//define hash function for strings 
    enum 
    { 
        //parameters for hash table 
        bucket_size = 4,  // 一个桶4byte长度(因为sizeof(char*)=4)
        min_buckets = 8 // 最少存在8个桶
    };
    size_t operator()(const char* str) const 
    { 
        unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
    }
    bool operator()(const char *s1, const char* s2) const 
    {    
        if (strcmp(s1, s2) == 0)
        {
            return false;
        }
        else
        {
            return true;
        }
    } 
}; 

然后

stdext::hash_map<const char*, Your Data Type, StringCompare>

posted @ 2012-08-14 20:40 寰子 阅读(403) | 评论 (0)编辑 收藏


得分第一:

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
    unsigned 
int seed = 131// 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
 
    
while (*str)
    
{
        hash 
= hash * seed + (*str++);
    }

 
    
return (hash & 0x7FFFFFFF);
}


得分第二:

// AP Hash Function
unsigned int APHash(char *str)
{
    unsigned 
int hash = 0;
    
int i;
 
    
for (i=0*str; i++)
    
{
        
if ((i & 1== 0)
        
{
            hash 
^= ((hash << 7^ (*str++^ (hash >> 3));
        }

        
else
        
{
            hash 
^= (~((hash << 11^ (*str++^ (hash >> 5)));
        }

    }

 
    
return (hash & 0x7FFFFFFF);
}


得分第三:

// DJB Hash Function
unsigned int DJBHash(char *str)
{
    unsigned 
int hash = 5381;
 
    
while (*str)
    
{
        hash 
+= (hash << 5+ (*str++);
    }

 
    
return (hash & 0x7FFFFFFF);
}


得分第四:

// JS Hash Function
unsigned int JSHash(char *str)
{
    unsigned 
int hash = 1315423911;
 
    
while (*str)
    
{
        hash 
^= ((hash << 5+ (*str+++ (hash >> 2));
    }

 
    
return (hash & 0x7FFFFFFF);
}


 

另外,此处也有一篇文章,其中提及了另外几种效率也颇高的hash算法

http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633 


 

posted @ 2012-08-14 20:32 寰子 阅读(322) | 评论 (1)编辑 收藏

 

double CCarNaviView::CalculateRotateAngle(CPoint pntBegin,CPoint pntNext)
{
    CPoint pntFirst(pntBegin);
    CPoint pntSecond(pntNext);

    
double dRotateAngle = atan2(fabs(pntBegin.x-pntNext.x),fabs(pntBegin.y-pntNext.y));
 
    
//如果下一点的横坐标大于前一点(在第一和第四象限)
    if (pntNext.x>=pntFirst.x)
    
{
        
//在第一象限(0<=dRotateAngle<=90)
        if (pntNext.y>=pntFirst.y)
        
{
            
//不做任何处理
            dRotateAngle=dRotateAngle;
        }

        
else
        
{
            dRotateAngle
=PI-dRotateAngle;
        }

    }

    
else//(在第二和第三象限)
    {
        
//第二象限
        if (pntNext.y>=pntFirst.y)
        
{
            dRotateAngle
=2*PI-dRotateAngle;
        }

        
else//第三象限
        {
            dRotateAngle
=PI+dRotateAngle;
        }

    }

    dRotateAngle 
= dRotateAngle * 180 / PI;
    
return dRotateAngle;
}

posted @ 2012-08-14 20:28 寰子 阅读(1399) | 评论 (1)编辑 收藏
仅列出标题