关于一道搜索引擎TOP10热点查询

迈不过友情╰ 2022-05-14 22:59 154阅读 0赞

这是网上流传的一道百度笔试题。

我也参加过一次百度笔试，也有一道类似的题目，不过数据量更大点，要求稍微多一点，限于笔试时候有要求以后不能泄露题目所以就不具体描述了。

题目：寻找热门查询：
    
    
    搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
    
    
    假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。
    
    
    一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
    
    
    （1）请描述你解决这个问题的思路；
    
    
    （2）请给出主要的处理流程，算法，以及算法的复杂度。
    
    
    
    首先粗略计算下3百万条大概是700多M不到800M，而1千万条是放不进内存的。
    
    
    其次，这题肯定需要{字符串：次数}这样的结构。
    
    
    这题所需要的Hash显然让我很揪心，我觉得一时半会我是无法设计出一个优雅的可以应付几百万条字符串而且简单有力的Hash函数的。
    
    
    所以我有想到了尝试一下C++ STL中的Set，纯粹思考一下如果这样会如何，然后再去找找高手们设计的Hash函数。
    
    
    
    STL中Set是基于红黑树实现的，所以在里面进行查找的话是O(logN)，300万大概是3乘以2^20，所以在Set里面查找大概需要十几二十次，
    
    
    而每一次是进行一次不长于255个字符的字符串比较。
    
    
    所以采用Set的话，我的基本想法是每次往内存中读入几十万条记录，然后逐条插入。
    
    
    这时候就需要做几个动作了，比如由于采用了自定义结构，所以需要重载运算符，以{字符串：次数}中的字符串为key。
    
    
    还需要在每次插入前find下该key记录是否存在，如果存在就将对应次数加1。
    
    
    同时在处理这一千万条记录的时候保持一个10个记录大小的最大堆，用来获取最热记录。
    
    
    每次Set进行插入操作都需要检查是否要重新维持最大堆。
    
    
    
    是的，以上是一个想法。但是相比较于Hash，如果Hash需要1秒钟，那么以上的思路在最坏情况下恐怕需要按小时计算。
    
    
    所以，我就去找一下高明的Hash函数。
    
    
    
    寻觅到所谓暴雪的Hash函数：
    
    
    code1：
    unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
    {
        unsigned char *key = (unsigned char *)lpszFileName;
        unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
        int ch;
    
        while(*key != 0)
        {
    
            ch = toupper(*key++);
    
            seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
            seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
        }
        return seed1;
    } 
    
    
    code2：
    int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
    {
        const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
        int nHash = HashString(lpszString, HASH_OFFSET);
        int nHashA = HashString(lpszString, HASH_A);
        int nHashB = HashString(lpszString, HASH_B);
        int nHashStart = nHash % nTableSize, nHashPos = nHashStart;
    
        while (lpTable[nHashPos].bExists)
        {
    
            if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
                return nHashPos;
            else
                nHashPos = (nHashPos + 1) % nTableSize;
    
            if (nHashPos == nHashStart)
                break;
        }
    
        return -1; //Error value
    } 
    
    
    
    通过维持一个300万大小的Hash表，然后再参考上述两个函数，自定义一番，并且在处理1000万条数据时同样维持一个大小为10的最大堆。
    
    
    即一个字符串对应3个hash值，一个用来确定位置，两个用来进一步比较，判断都相同的话就将次数加1；
    
    
    如果位置相同，但另外两个hash值不同，则表明是不同字符串，就需要进行reHash了，或者链在一起。
    
    
    其实我个人觉得，对于这样的数据，可以适当扩大Hash表降低hash值重复的概率，就可以忽略一些偏差，
    
    即我觉得前若干热门的一般会和后面的有着巨大落差，部分偏差造成的影响不会很大。