给定一个字符串，如果快速得到另一个hashCode相同的最短字符串

因为java.lang.Object中的hashCode()方法返回类型是in。其范围为 －2³¹ ~ 2³¹ －1。

Java中用UTF编码，字符长度16位，即大约有2¹⁶ 个字符。长度为2个字符串就有2³² 个。等于int的范围。

根据抽屉原理：

• 有一个长度为3的字符串，一定存在另一个长度≤3的字符串，它们的hashCode相等。
• 任何一个字符串，一定存在很多个与它的hashCode相等的字符串。比如"一一一一一一一一一"和“侏丝丈业”的hashCode都是626609664。

那么有2个算法题：

1. 题目1：给定任意一个字符串，求与它的hashCode相等的最短字符串（短的意思是说如果a比b短，意味着 a.length()<b.length() || (a.length()==b,length() && a.compareTo(b)<0) ）。
2. 题目2：给定任意一个int值，求hashCode等于此int值的最短字符串（短的意思同上）。

 

先记下，什么时候有空写个算法研究一下。

几点思考：

     1       String类中hashCode要多次用到31^n次这个。可以先用全局静态量记住。如

                               int[] POW31={1,31,961,29791,923521,...};

              这样31^n = POW31[n]就可以了。

     2       如果不考虑int的符号(即当作无符号整数)，hashCode会在一定范围内随着字符串增加而增加。即存在区间的概念，可以通过区间段快速定位。这样给定一个hashCode的int值时，可以快速定位到一个区间（即可以大致猜出如果长度为2时，它的第一字符一定在某个范围内，比如['A','z']）。

     3       从hashCode求字符串的过程有点类似于把一个10进制的int值转换为31进制。所不同的是31进制的每位一定是[0,30]的整数，而hashCode的每位可能是[0,65535]。也就是说如果转换为31进制后第一个不为0的最高位是 x(1<=x<=30)，则结果字符串的首位可能是 x、x*31、x*31*31、x*31*31*31、...这些可能值中的一个（前提条件是那些可能值必须小于65536）。

 

另外附java.lang.String中hashCode()的算法。

public int hashCode()
返回此字符串的哈希码。String 对象的哈希码按下列公式计算： 
           s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
使用 int 算法，这里 s[i] 是字符串的第 i 个字符，n 是字符串的长度，^ 表示求幂。（空字符串的哈希码为 0。）