C++博客-xocoder's game development base

stdext::hash_map使用字符串key

寰子 — Tue, 14 Aug 2012 12:40:00 GMT

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

寰子 2012-08-14 20:40 发表评论

各种字符串Hash函数比较

寰子 — Tue, 14 Aug 2012 12:32:00 GMT

得分第一：

// 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

寰子 2012-08-14 20:32 发表评论

同一坐标系中，由任意两点计算旋转角度.

寰子 — Tue, 14 Aug 2012 12:28:00 GMT

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

。

寰子 2012-08-14 20:28 发表评论