正文

请到「今天看啥」查看全文

乘法

所有数字相乘，积为381150。这似乎是可行的，但出现了这样的问题：lesk、lsek、slke……的积是一样的，每一个数字键还对应着3个字母，意味着重复的概率会很高。

改进后的乘法

①字母相同但字母序不同的字符串，可以通过这样的方式来避免冲突：每一个数字先乘以序号，然后再与其它值相乘。

②每一个数字键对应了3个英文字母，如果用户没有输入字母在数字键中的序号，是没办法再进一步精确计算的。能考虑的方向只能是根据给定的单词表来做概率统计，所以不予考虑。

位置冲突

即使用改进后的乘法，不同的姓名字母计算得出的积依然还是可能会发生重复，那么当发生冲突后应该怎么办？
顺序保存到下一个空白位置？仔细想想这是行不通的。如果下一个空白位置刚好又是另外的字母集合的积，那就产生了二次冲突。
幸好，还有质数。
质数只能被1和自身整除，那么上述乘法得出的任何积都不可能是质数，所以质数位置是没有保存电话号码的。
因此，以当前积为起点向右搜索下一个质数，如果该质数位置依然被使用，那么就继续查找下一个最近的质数……
至此，问题似乎是解决了。
用户输入一串数字，根据公式计算得到积，返回该下标位置的电话号码。如果不正确，再顺序查找后面的质数，直到某个质数下标的数组元素为空为止，最后返回所有查找到的电话号码。大部分情况下，只需要O(1)的时间复杂度就可以找到电话号码。

数组太大

唯一的问题是，按照上述思路建立的数组实在是太大了。一个姓名有10个字母，假如每一个字母对应的数字都是9，最后得到的积约是9的17次方。这意味着要建立9^17大小的数组，这是完全不可行的。

后来

即使不考虑数组过大因素，以我当时初学编程的水平，这样的程序也是没有能力写出来的。
我之所以还原这个思考的过程，是觉得独立思考的过程非常有趣也很有价值。想想，其实现有的算法都是当年那些大牛在实际工程中一步一步寻求解决方案而最终推导得到的。
因此，当在工程中碰到一些棘手的难题时，只要乐于思考分解问题并寻求每一个小问题解决方案，那么很多所谓的难题都是可以解决的。
后来看了《数据结构与算法分析.Java语言描述》，我才知道原来我的思路其实就是开放寻址法（Open Addressing）。
JDK的HashMap使用的则是分离链接法(separate chaining)。不同：增加了桶的概念来保存冲突的数据；进行求余运算来降低数组大小。
那么，就谈谈Java中的HashMap吧。

四、HashMap结构及算法详解

请到「今天看啥」查看全文