HashMap 散列初体验

雨点打透心脏的1/2处 2022-06-04 00:29 128阅读 0赞

**参考目录：**

>  1. [HashMap 散列初体验][HashMap]  
>  2.[ 为什么HashMap 常用String 对象作key][_HashMap _String _key]  
>  3. [HashMap 原理][HashMap 1]  
>  4.[自定义 hashCode()][hashCode]  
>  5.[HashMap 的性能因子][HashMap 2]

我们用Groundhog(土拨鼠)对象与Prediction(预报) 对象做了一个简单的土拨鼠预测季节的例子。我们用Groundhog 对象作为map 的key，将该土拨鼠预测的季节(Prediction)信息作为map 的value。

import java.lang.reflect.Constructor;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Random;
    
    public class SpringDetector { 
        public static <T extends Groundhog> void detectSpring (Class<T> type) throws Exception{
            Constructor<T> constructor = type.getConstructor(int.class);
            Map<Groundhog,Prediction> map = new HashMap<>();
    
            for(int i = 0;i < 10;i++)
                map.put(constructor.newInstance(i),new Prediction());
            for (Groundhog key : map.keySet())
                System.out.println(key + " pridict: " + map.get(key));
    
            Groundhog Groundhog = constructor.newInstance(1);
            System.out.println("Looking up prediction for : " + Groundhog);
    
            if(map.containsKey(Groundhog))
                System.out.println(map.get(Groundhog));
            else
                System.out.println("Key not found.");
        }
        public static void main(String[] args) throws Exception{
    
            detectSpring(Groundhog.class);
        }
    }
    
    class Groundhog{
        protected int number;
    
        public Groundhog(int number){
            this.number = number;
        }
        public String toString(){
            return "Groundhog #" + number;
        }
    }
    
    class Prediction{
        private static Random rand = new Random(40);
        private boolean shadow = rand.nextDouble() > 0.5;
    
        @Override
        public String toString() {
            if(shadow)
                return "Winter will come!";
            else
                return "Early Spring!";
        }
    }

> 输出  
> Groundhog \#9 pridict: Winter will come!  
> Groundhog \#0 pridict: Winter will come!  
> Groundhog \#2 pridict: Early Spring!  
> Groundhog \#5 pridict: Early Spring!  
> Groundhog \#7 pridict: Early Spring!  
> Groundhog \#4 pridict: Early Spring!  
> Groundhog \#6 pridict: Winter will come!  
> Groundhog \#1 pridict: Early Spring!  
> Groundhog \#3 pridict: Winter will come!  
> Groundhog \#8 pridict: Winter will come!  
> Looking up prediction for : Groundhog \#1  
> Key not found.

上面是其中一次的输出结果，在Groundhog 类中通过构造函数传递了一个标志数字，于是可以根据这个标志在HashMap 中查找Prediction ：“我想要看 Groundhog \#1 这只土拨鼠预测的季节情况。”在Prediction 类中提供了一个boolean 值 与一个toString 的方法。detectSpring () 方法使用反射机制来实例化从Groundhog 或从Groundhog 派生类出来的对象。

我们首先使用Groundhog 和 Prediction 类来填充map ，然后打印该map 中的数据。然后我们想要查看“ Groundhog \#1”这只土拨鼠的季节预测情况。但是却发现无法找到 “Groundhog \#1” 这个键，从上面的输出结果我们看出， “Groundhog \#1” 是已经存在map 中了。为什么这只土拨鼠没有工作呢？ 问题在Groundhog 这个类自动继承Object 类，所以在这里使用Object 中的hashCode() 方法生成散列码，而它默认是根据对象的地址来计算散列码。因此map 中的“ Groundhog \#1”与要创建的查找“ Groundhog \#1”两个实例的散列码是不同的，因此在map 中查找不到该土拨鼠预测季节的情况。

也许我们会认为我们只需要重写Object 类中的hashCode() 方法即可。如果你这样做，你会发现它仍然行不通，除非你同时覆盖equals() 方法，因为它也是Object 类的一部分，**HashMap 使用equals() 方法来判断当前的键是否与表中的键相同。**在这里我们简单看一下Object 类中的equals() 方法与 hashCode() 方法：

> equals  
> public boolean equals(Object obj)指示其他某个对象是否与此对象“相等”。  
> equals 方法在非空对象引用上实现相等关系：  
>     自反性：对于任何非空引用值 x，x.equals(x) 都应返回 true。  
>     对称性：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应返回 true。  
>     传递性：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回 true，那么 x.equals(z) 应返回 true。  
>     一致性：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 始终返回 true 或始终返回 false，前提是对象上 equals 比较中所用的信息没有被修改。  
>     对于任何非空引用值 x，x.equals(null) 都应返回 false。  
> Object 类的 equals 方法实现对象上差别可能性最大的相等关系；即，对于任何非空引用值 x 和 y，当且仅当 x 和 y 引用同一个对象时，此方法才返回 true（x == y 具有值 true）。  
> 注意：当此方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。  
>   
> hashCode  
> public int hashCode()返回该对象的哈希码值。支持此方法是为了提高哈希表（例如 java.util.Hashtable 提供的哈希表）的性能。  
> hashCode 的常规协定是：  
> 在 Java 应用程序执行期间，在对同一对象多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是将对象进行 equals 比较时所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。  
> **如果根据 equals(Object) 方法，两个对象是相等的，那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。**  
> 如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么对这两个对象中的任一对象上调用 hashCode 方法不 要求一定生成不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同整数结果可以提高哈希表的性能。  
> 实际上，由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。（这一般是通过将该对象的内部地址转换成一个整数来实现的，但是 JavaTM 编程语言不需要这种实现技巧。）

在这里特别强调如果你需要覆盖Object 类中的equals() 方法，那也请你也覆盖hashCode() 方法\[我曾在阿里Java 开发手册中也看到过这句话\]。equals () 方法只是比较两个对象的地址，因此如果我们要实现“ Groundhog \#1” 查看预测季节情况，那么我们必须让Groundhog 同时覆盖Object 类中的equals() 方法与hashCode() 方法。

下面我们就来这样做：重新定义一个Groundhog 2 继承自Groundhog 类，然后覆盖了equals() 方法与 hashCode() 方法，hashCode() 方法返回父类的number 作为散列码而不是再根据对象的地址来计算，equals() 方法用来判断对象是否相同。

public static void main(String[] args) throws Exception{
            detectSpring(Grounghog2.class);
     }
    
    class Groundhog 2 extends Groundhog{
        public Groundhog 2(int num){
            super(num);
        }
        @Override
        public int hashCode() {
            return number;
        }
    
        @Override
        public boolean equals(Object obj) {
            return obj instanceof Groundhog 2 && super.number ==((Groundhog 2) obj).number;
        }
    }
    //.......其余代码省略

> 输出  
> Groundhog \#0 pridict: Winter will come!  
> Groundhog \#1 pridict: Early Spring!  
> Groundhog \#2 pridict: Early Spring!  
> Groundhog \#3 pridict: Winter will come!  
> Groundhog \#4 pridict: Early Spring!  
> Groundhog \#5 pridict: Early Spring!  
> Groundhog \#6 pridict: Winter will come!  
> Groundhog \#7 pridict: Early Spring!  
> Groundhog \#8 pridict: Winter will come!  
> Groundhog \#9 pridict: Winter will come!  
> Looking up prediction for : Groundhog \#1  
> Early Spring!

根据上面的结果我们可以看出”Groundhog \#”1 不再找不到了,我们找到了该只土拨鼠预测的季节情况。上面这个例子用到了反射与泛型，你们不觉得上面的代码很优美吗？具有很强的扩展性，O(∩\_∩)O哈哈~。可见学会使用了泛型与反射是多么重要，少年多多努力吧！

参考书籍：  
《Java 编程思想》Bruce Eckel 著 陈昊鹏 译

[HashMap]: http://blog.csdn.net/codejas/article/details/78667437
[_HashMap _String _key]: http://blog.csdn.net/codejas/article/details/78837830
[HashMap 1]: http://blog.csdn.net/codejas/article/details/78673074
[hashCode]: http://blog.csdn.net/codejas/article/details/78675821
[HashMap 2]: http://blog.csdn.net/codejas/article/details/78683113