---

一些看似复杂的问题，如果采用Hash表数据结构和查找算法，往往就能很容易的得到解决。所以当大家发现用了其他数据结构和算法都无法解决了，不妨考虑考虑Hash查找算法。

用Hash表解决问题的关键是确定它的key（关键字）。确定了关键字，再确定对应的值。然后Hash表就建立了起来。建立起Hash表之后，就可以通过查表来解决问题。

问题1：给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。

思路与解答：对单词aadb 定义特征码是a2b1d1， dddabc的特征码是a1b1c1d3，以此类推，根据特征码建立Hash表。然后对给顶单词，搜索Hash表，就可以得到这个单词的兄弟单词数量。

问题2：请编写一个高效率的函数来找出字符串中的第一个无重复字符。例如，"total"中的第一个无重复字符上一"o"。

算法：

 

public static Character FisrtNonRepeated(String str)

{

     Hashtable      charHash = new Hashtable();

     int           i, length;

     Character      c;

     Integer       intgr;

 

     length = str.length();

     for (i = 0; i < length; i++)

    {

         c = new Character9str.charAt(i));

         intgr = (Integer) charHash.get(c);

         if (intgr == NULL)

        {

              charHash.put(c, new Integer(1));

         }

        else

        {

              charHash.put(c, new Integer(intgr.intValue() + 1));

         }

     }

     for (i = 0; i < length; i++)

    {

         c = new Character(str.charAt(i));

         if (((Integer) charHash.get(c)).intValue() == 1)

              return (c);

     }

     return (null);

}

 

问题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

    1）请描述你解决这个问题的思路；

    2）请给出主要的处理流程，算法，以及算法的复杂度。

       分析：

1）使用哈希算法解决此问题。

2）流程：首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度（注意值与日志项对应关系），选出前十的频度，取出对应的日志串，就是要找的热门字符串。

此题哈希的设计与应用是关键。