Java高级系列——散列与散列码

你的名字 2022-05-28 11:28 225阅读 0赞

**使用散列的目的**：想要使用一个对象查找另一个对象。

**散列的价值**：散列的价值在于速度，散列使得查询得以快速进行。

**设计hashCode()时最重要的因素**：无论何时，对同一个对象调用hashCode()都会产生同样的值。如果将一个对象用put()添加进HashMap时产生一个hashCode()值，而用get()取出时却产生了另外一个hashCode()值，那么就无法重新取得该对象了。

想要使hashCode()实用，它必须速度快，并且必须有意义。也就是说，它必须基于对象的内容生成散列码。散列码不必是独一无二的（应该关注生成速度，而不是唯一性），但是通过hashCode()和equals()，必须能够完全确定对象的身份。

好的hashCode()应该产生分布均匀的散列码。如果散列码都集中在一块，那么HashMap或者HashSet在某些区域的负载会很重，这样就不如分布均匀的散列函数快。

**hashCode()基本指导**

1、给int变量result赋予某个非零值常量，例如17.

2、为对象内每个有意义的域f（即每个可以做equals操作的域）计算出一个int散列码c：

<table> 
 <thead> 
  <tr> 
   <th>域类型</th> 
   <th>计算</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean</td> 
   <td>c = (f ? 0 : 1)</td> 
  </tr> 
  <tr> 
   <td>byte、char、short或int</td> 
   <td>c = (int)f</td> 
  </tr> 
  <tr> 
   <td>long</td> 
   <td>c = (int)(f^(f&gt;&gt;&gt;32))</td> 
  </tr> 
  <tr> 
   <td>float</td> 
   <td>c = Float.floatToIntBits(f)</td> 
  </tr> 
  <tr> 
   <td>double</td> 
   <td>long l = Double.doubleToLongBits(f);<br>c = (int)(l^(l &gt;&gt;&gt; 32))</td> 
  </tr> 
  <tr> 
   <td>Object，其equals()调用这个域的equals()</td> 
   <td>c = f.hashCode()</td> 
  </tr> 
  <tr> 
   <td>数组</td> 
   <td>对每个元素应用上述规则</td> 
  </tr> 
 </tbody> 
</table>

注：如果1中给定的初始值为0，那么计算出来的散列值将不受域类型的影响，从而可能会增加冲突的可能性。

3、合并计算得到的散列码：result=37 \* result + c;  
乘法运算使得散列值依赖于域的顺序，如果一个类包含多个相同的域，那么乘法运算会产生更好的散列函数。  
我们来看看在标准类库中String类的hashCode()方法：

public int hashCode() {
            int h = hash;
            if (h == 0 && value.length > 0) {
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) {
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
    }

假如String类也根据上面的步骤来建立散列函数，并且把乘法部分省去（即将 h = 31 \* h + val\[i\]改为 h = val\[i\]），则那些仅仅是字母顺序不同的所有字符串，都会有同样的散列码。

我们之所以将乘数选为37，是因为他是一个奇素数。如果乘数是偶数，并且乘法溢出的话，则会信息丢失，因为与2相乘等价于移位运算。

4、返回result；  
5、检查hashCode()最后生成的结果，确保相同的对象有相同的散列码。  
根据以上步骤实现的一个例子如下：

package containers;
    
    import java.util.*;
    
    public class CountedString {
        private static List<String> created = new ArrayList<String>();
        private String s;
        private int id = 0;
    
        public CountedString(String str) {
            s = str;
            created.add(s);
            for (String s2 : created)
                if (s2.equals(s))
                    id++;
        }
    
        public String toString() {
            return "String: " + s + " id: " + id + " hashCode(): " + hashCode();
        }
    
        public int hashCode() {
            int result = 17;
            result = 37 * result + s.hashCode();
            result = 37 * result + id;
            return result;
        }
    
        public boolean equals(Object o) {
            return o instanceof CountedString && s.equals(((CountedString) o).s) && id == ((CountedString) o).id;
        }
    
        public static void main(String[] args) {
            Map<CountedString, Integer> map = new HashMap<CountedString, Integer>();
            CountedString[] cs = new CountedString[5];
            for (int i = 0; i < cs.length; i++) {
                cs[i] = new CountedString("hi");
                map.put(cs[i], i);
            }
    
            System.out.println(map);
    
            for (CountedString cstring : cs) {
                System.out.println("Looking up " + cstring);
                System.out.println(map.get(cstring));
            }
        }
    }