Amélioration Java Chapitre 26------hashCode

-------------------------------- -------------------------------------------------- -------------------------------------------------- ------------------------------------------

Dans les trois articles de blog précédents, LZ a expliqué (HashMap, HashSet, HashTable), dans lequel LZ a continué à expliquer sa position et la méthode get, parmi ces deux méthodes, le calcul du hashCode de la clé devrait être la partie la plus importante et la plus essentielle, donc ci-dessous LZ dévoile le "mystère" du hashCode.

Le rôle du hashCode

Pour comprendre les principes internes d'une méthode, nous Vous devez d'abord comprendre ce qu'elle fait, c'est-à-dire ce que fait cette méthode. Lors de l'explication des tableaux (Java Improvement Chapter (18)------Arrays), nous avons mentionné que les tableaux constituent la structure de données la plus efficace en Java, mais que la "plus élevée" a une condition préalable. Nous devons d’abord connaître l’emplacement des données interrogées. Deuxièmement : si nous effectuons une recherche itérative, la quantité de données doit être faible. Pour de grandes quantités de données, les collections sont généralement recommandées.

Il existe deux types de collections en Java, l'une est List et l'autre est Set. La différence entre elles est que les éléments de la collection List sont ordonnés. , et peuvent être répétés, tandis que les éléments de la collection Set ne sont pas ordonnés et non répétables. List est facile à gérer, mais pour Set, comment s'assurer que les éléments ne sont pas répétés ? Vérifiez si equals() est égal en itérant. C'est acceptable lorsque la quantité de données est petite, mais l'efficacité peut être imaginée lorsque notre quantité de données est importante (bien sûr, nous pouvons utiliser des algorithmes pour optimiser). Par exemple, si nous insérons 1 000 données dans HashSet, devons-nous vraiment itérer 1 000 fois et appeler la méthode equals() 1 000 fois ? hashCode fournit la solution. Comment y parvenir ? Regardons d'abord le code source (Object) de hashCode.

public native int hashCode();

C'est une méthode locale, et sa mise en œuvre est liée à la machine locale Ici. nous allons le laisser pour l'instant. On pense que ce qu'il renvoie est l'emplacement physique du stockage d'objets (en fait non, c'est écrit ici pour faciliter la compréhension). Lorsque nous ajoutons un élément à une collection, la collection appellera d'abord la méthode hashCode, afin que l'emplacement où il est stocké puisse être directement localisé s'il n'y a pas d'autres éléments, il sera enregistré directement. S'il y a déjà un élément, appelez la méthode equals pour vérifier si les deux éléments sont identiques. S'ils sont identiques, ils ne seront pas stockés. S'ils sont différents, ils seront hachés vers d'autres emplacements (pour plus de détails,). veuillez vous référer à (Amélioration Java) ()-----HashMap )). De cette façon, lorsque nous stockons un grand nombre d’éléments, nous pouvons réduire considérablement le nombre d’appels à la méthode equals(), améliorant ainsi considérablement l’efficacité.

Donc hashCode joue le rôle de recherche de domaine (trouver l'emplacement d'un objet dans la collection) ) . HashCode peut diviser la collection en plusieurs zones. Chaque objet peut calculer son code de hachage. Les codes de hachage peuvent être regroupés à une certaine zone de stockage. Selon le code de hachage d'un objet, la zone de hachage peut être déterminée. , réduisant ainsi considérablement le nombre d'éléments de correspondance de requête et améliorant l'efficacité des requêtes.

L'importance du hashCode pour un objet

hashCode Est-ce important ? Ce n'est pas important, pour les collections et les tableaux List, c'est un fardeau, mais pour HashMap, HashSet et HashTable, cela devient extrêmement important. Par conséquent, vous devez faire attention à hashCode lorsque vous utilisez HashMap, HashSet et HashTable. Pour un objet, son processus hashCode est l'implémentation d'un simple algorithme de hachage, et son processus d'implémentation joue un rôle très important dans la réalisation du processus d'accès à l'objet.

LZ a mentionné deux structures de données, HashMap et HashTable Bien qu'elles présentent plusieurs différences, leurs principes de mise en œuvre sont les mêmes. Ici, j'utilise HashTable et prend un exemple pour illustrer. l'importance du hashCode pour un objet.

           一个对象势必会存在若干个属性，如何选择属性来进行散列考验着一个人的设计能力。如果我们将所有属性进行散列，这必定会是一个糟糕的设计，因为对象的hashCode方法无时无刻不是在被调用，如果太多的属性参与散列，那么需要的操作数时间将会大大增加，这将严重影响程序的性能。但是如果较少属相参与散列，散列的多样性会削弱，会产生大量的散列“冲突”，除了不能够很好的利用空间外，在某种程度也会影响对象的查询效率。其实这两者是一个矛盾体，散列的多样性会带来性能的降低。

           那么如何对对象的hashCode进行设计，LZ也没有经验。从网上查到了这样一种解决方案：设置一个缓存标识来缓存当前的散列码，只有当参与散列的对象改变时才会重新计算，否则调用缓存的hashCode，这样就可以从很大程度上提高性能。

           在HashTable计算某个对象在table[]数组中的索引位置，其代码如下：

int index = (hash & 0x7FFFFFFF) % tab.length;

           为什么要&0x7FFFFFFF？因为某些对象的hashCode可能会为负值，与0x7FFFFFFF进行与运算可以确保index为一个正数。通过这步我可以直接定位某个对象的位置，所以从理论上来说我们是完全可以利用hashCode直接定位对象的散列表中的位置，但是为什么会存在一个key-value的键值对，利用key的hashCode来存入数据而不是直接存放value呢？这就关系HashTable性能问题的最重要的问题:Hash冲突！

           我们知道冲突的产生是由于不同的对象产生了相同的散列码，假如我们设计对象的散列码可以确保99.999999999%的不重复，但是有一种绝对且几乎不可能遇到的冲突你是绝对避免不了的。我们知道hashcode返回的是int，它的值只可能在int范围内。如果我们存放的数据超过了int的范围呢？这样就必定会产生两个相同的index，这时在index位置处会存储两个对象，我们就可以利用key本身来进行判断。所以具有相索引的对象，在该index位置处存在多个对象，我们必须依靠key的hashCode和key本身来进行区分。

      hashCode与equals

           在Java中hashCode的实现总是伴随着equals，他们是紧密配合的，你要是自己设计了其中一个，就要设计另外一个。当然在多数情况下，这两个方法是不用我们考虑的，直接使用默认方法就可以帮助我们解决很多问题。但是在有些情况，我们必须要自己动手来实现它，才能确保程序更好的运作。

           对于equals，我们必须遵循如下规则：

           对称性：如果x.equals(y)返回是“true”，那么y.equals(x)也应该返回是“true”。

           反射性：x.equals(x)必须返回是“true”。

           类推性：如果x.equals(y)返回是“true”，而且y.equals(z)返回是“true”，那么z.equals(x)也应该返回是“true”。

           一致性：如果x.equals(y)返回是“true”，只要x和y内容一直不变，不管你重复x.equals(y)多少次，返回都是“true”。

           任何情况下，x.equals(null)，永远返回是“false”；x.equals(和x不同类型的对象)永远返回是“false”。

           对于hashCode，我们应该遵循如下规则：

           1. 在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，则对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。

           2. 如果两个对象根据equals(Object o)方法是相等的，则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。

           3. 如果两个对象根据equals(Object o)方法是不相等的，则调用这两个对象中任一个对象的hashCode方法，不要求产生不同的整数结果。但如果能不同，则可能提高散列表的性能。

           至于两者之间的关联关系，我们只需要记住如下即可：

           如果x.equals(y)返回“true”，那么x和y的hashCode()必须相等。

           如果x.equals(y)返回“false”，那么x和y的hashCode()有可能相等，也有可能不等。

           理清了上面的关系我们就知道他们两者是如何配合起来工作的。先看下图：

           整个处理流程是：

           1、判断两个对象的hashcode是否相等，若不等，则认为两个对象不等，完毕，若相等，则比较equals。

           2、若两个对象的equals不等，则可以认为两个对象不等，否则认为他们相等。

           实例：

public class Person {
    private int age;
    private int sex;    //0：男，1：女
    private String name;
    
    private final int PRIME = 37;
    
    Person(int age ,int sex ,String name){
        this.age = age;
        this.sex = sex;
        this.name = name;
    }

    /** 省略getter、setter方法 **/
    
    @Override
    public int hashCode() {
        System.out.println("调用hashCode方法...........");

        int hashResult = 1;
        hashResult = (hashResult + Integer.valueOf(age).hashCode() + Integer.valueOf(sex).hashCode()) * PRIME;
        hashResult = PRIME * hashResult + ((name == null) ? 0 : name.hashCode()); 
        System.out.println("name:"+name +" hashCode:" + hashResult);
        
        return hashResult;
    }

    /**
     * 重写hashCode()
     */
    public boolean equals(Object obj) {
        System.out.println("调用equals方法...........");
        
        if(obj == null){
            return false;
        }
        if(obj.getClass() != this.getClass()){
            return false;
        }
        if(this == obj){
            return true;
        }

        Person person = (Person) obj;
        
        if(getAge() != person.getAge() || getSex()!= person.getSex()){
            return false;
        }
        
        if(getName() != null){
            if(!getName().equals(person.getName())){
                return false;
            }
        }
        else if(person != null){
            return false;
        }
        return true;
    }
}

           该Bean为一个标准的Java Bean，重新实现了hashCode方法和equals方法。

public class Main extends JPanel {

    public static void main(String[] args) {
        Set<Person> set = new HashSet<Person>();
        
        Person p1 = new Person(11, 1, "张三");
        Person p2 = new Person(12, 1, "李四");
        Person p3 = new Person(11, 1, "张三");
        Person p4 = new Person(11, 1, "李四");
        
        //只验证p1、p3
        System.out.println("p1 == p3? :" + (p1 == p3));
        System.out.println("p1.equals(p3)?:"+p1.equals(p3));
        System.out.println("-----------------------分割线--------------------------");
        set.add(p1);
        set.add(p2);
        set.add(p3);
        set.add(p4);
        System.out.println("set.size()="+set.size());
    }
}

            运行结果如下：

           从上图可以看出，程序调用四次hashCode方法，一次equals方法，其set的长度只有3。add方法运行流程完全符合他们两者之间的处理流程。

以上就是Java提高篇（二六）------hashCode 的内容，更多相关内容请关注PHP中文网（www.php.cn）！