C, PHP, VB, .NET

Дневникът на Филип Петров


* Метод hashCode()

Публикувано на 08 декември 2010 в раздел ПИК3 Java.

Хеширането е важна част от езика за програмиране Java. То ни позволява при определени случаи ефективно и бързо да сравняваме обекти подобно на стандартния метод equals(). Когато на обект от даден клас извикаме метод "hashCode()", то като резултат получаваме цяло число (int). Идеята е следната:

"Ако два обекта са еднакви при сравнение с equals(), техните методи hashCode() трябва да връщат равни числа" (1)

Ето един пример:

public class hashCodeExample{
   public static void main(String[] args){
      String s1 = "abcd";
      String s2 = "abcd";
      String s3 = "aBcd";
      System.out.println(s1+" has hash code: "+s1.hashCode());
      System.out.println(s2+" has hash code: "+s2.hashCode());
      System.out.println(s3+" has hash code: "+s3.hashCode());
   }
}

Резултатът ще бъде:

abcd has hash code: 2987074
abcd has hash code: 2987074
aBcd has hash code: 2956322

Виждате, че обектите, които са еднакви имат и еднакви хеш кодове. Това обаче не винаги ще бъде вярно, когато самите ние създаваме класове. Нека дадем следния пример:

public class hashCodeExample{
   public static void main(String[] args){
      Person p1 = new Person("Ivan", 23);
      Person p2 = new Person("Ivan", 23);
      Person p3 = new Person("Petar", 23);
      System.out.println(p1.name+" age "+p1.age+" hash code: "+p1.hashCode());
      System.out.println(p2.name+" age "+p2.age+" hash code: "+p2.hashCode());
      System.out.println(p3.name+" age "+p3.age+" hash code: "+p3.hashCode());
   }
}

class Person{
   public String name;
   public int age;
   public Person(String name, int age){
      this.name = name;
      this.age = age;
   }
   public boolean equals(Object o){
      if(!(o instanceof Person)) return false;
      Person p = (Person)o;
      if(p.name == null) return false;
      return (this.name.equals(p.name) && this.age == p.age);
   }
}

Резултатът ще бъде:

Ivan age 23 hash code: 9555723
Ivan age 23 hash code: 8414877
Petar age 23 hash code: 15613422

Виждаме, че клас Person не отговаря на условието (1). Следователно ние трябва да се погрижим да предефинираме метод hashCode() така, че два еднакви обекта да връщат един и същи хеш код. Това може да стане например така:

public class hashCodeExample{
   public static void main(String[] args){
      Person p1 = new Person("Ivan", 23);
      Person p2 = new Person("Ivan", 23);
      Person p3 = new Person("Petar", 23);
      System.out.println(p1.name+" age "+p1.age+" hash code: "+p1.hashCode());
      System.out.println(p2.name+" age "+p2.age+" hash code: "+p2.hashCode());
      System.out.println(p3.name+" age "+p3.age+" hash code: "+p3.hashCode());
   }
}

class Person{
   public String name;
   public int age;
   public Person(String name, int age){
      this.name = name;
      this.age = age;
   }
   public boolean equals(Object o){
      if(!(o instanceof Person)) return false;
      Person p = (Person)o;
      if(p.name == null) return false;
      return (this.name.equals(p.name) && this.age == p.age);
   }
   public int hashCode(){ 
      return ((this.name==null?0:this.name.hashCode())+this.age); 
   }
 }

Резултатът вече ще е валиден:

Ivan age 23 hash code: 2291281
Ivan age 23 hash code: 2291281
Petar age 23 hash code: 77005191

Виждаме, че за да направим обектите си валидни, то елементарно трябва да предефинираме методът hashCode(). Въпросът, който остава е - проблем ли е ако ние не го правим? Всички програми в досегашните ни примери работеха напълно коректно и нямаха проблеми. Тогава защо ни е да предефинираме метод hashCode()? За да отговорим на този въпрос трябва да разгледаме два варианта:

  1. Обектите са еднакви, но връщат различни хеш кодове: няма абсолютно никакъв проблем да работим с такива обекти, но такъв ще се появи тогава, когато ги добавяме към HashSet, HashMap или друг вид множество Set или речник Map (тези структури от данни ще разгледаме по-късно в следваща статия). Множествата и речниците използват функцията hashCode() и очакват правилото за нея да бъде спазено. Следователно при тях резултатите при липса на метода стават не само непредвидими, а самите структури стават неизползваеми;
  2. Обектите са различни, но връщат еднакви хеш кодове: това принципно не е проблем - не нарушава дефиницията на hashCode(). Единственото негативно в този случай ще е, че HashSet и HashMap ще работят по-бавно когато има много обекти с много повторения на хеш кода. Затова е добре хеш кодовете да са максимално различни при различните обекти.

С дотук казаното можем да заключим, че предефинирането на метод hashCode() е препоръчително за всеки клас. Освен това трябва да се стремим стойностите да са максимално различни. Последното впрочем е трудна задача в определени случаи. Дефинирането на добър hashCode() винаги е предизвикателство. В книгата "Thinking in Java" се дава следната "рецепта" - резултатът от функцията започва от числото 17 и за всяка променлива от класа го умножаваме по 37 и добавяме хеш кода или стойността на променливата превърната в int (при примитивен тип данни) към него. Ето пример:

class Person{
  public String firstname;
  public String lastname;
  public int age;
  public Person(String firstname, String lastname, int age){
    this.firstname = firstname;
    this.lastname = lastname;
    this.age = age;
  }
  public boolean equals(Object o){
    if(!(o instanceof Person)) return false;
    Person p = (Person)o;
    if(p.firstname == null || p.lastname == null) return false;
    return (this.firstname.equals(p.firstname) 
              && 
            this.lastname.equals(p.lastname)
              &&
            this.age == p.age);
  }
  public int hashCode(){
    int result = 17;
    result = result*37 + (this.firstname==null?0:this.firstname.hashCode());
    result = result*37 + (this.lastname==null?0:this.lastname.hashCode());
    result = result*37 + this.age;
    return result;
  }
}

Ще забележите, че по този начин е възможно числата да станат отрицателни, защото прехвърлят размера на типа данни. Това не е проблем - хеш кодът може да е отрицателен. Спазването на горната рецепта е доказало практическата си ефективност. Препоръчва се такъв метод hashCode() да се предефинира във всеки клас.

Понякога обаче не е толкова тривиално да преобразуваме всякакъв тип данни в int. Ами ако имаме член променлива float, double или long? Стремете се да спазвате следната схема в зависимост от поредната член-променлива var:

  1. Ако var е boolean, правете result = result*37 + Boolean.valueOf(this.var).hashCode();
  2. Ако var e byte, char или short, правете result = result*37 + (int)this.var;
  3. Ако var е long, правете result = result*37 + Long.valueOf(this.var).hashCode();
  4. Ако var е float, правете result = result*37 + Float.valueIOf(this.var).hashCode();
  5. Ако var e double, правете result = result*37 + Double.valueOf(this.var).hashCode();
  6. Ако var е произволен обект, за по-сигурно правете result = result*37 + (this.var==null?0:this.var.hashCode()).

Условния оператор this.var==null?0:this.var.hashCode() е важна проверка, защото ако в даден обект се запише null, неговия метод hashCode() ще връща NullPointerException.

 



2 коментара


  1. Поздравления за статията - кратко и ясно е описано какво прави hashCode(). Бих искал да повдигна следната дискусия: резглеждаме твърдението: "Класовете, които ще се хешират, освен да имплементират hashCode() и equals(), трябва да са immutable, т.е. да не може да се променя състоянието им (полетата им)". Доводите за са очевидни - ако например ползваме обекти от такъв клас за ключ в HashMap, при промяна на ключа, ще се промени и хеша му, което ще го направи неоткриваем. Това би могло да създаде проблеми, особено ако сме натворили спагети код и много други обекти пазят инстанция на съответния ключ. Доводът против е, че това води до проблеми с производителността, а също така в някои случаи правенето на класа immutable нe e тривиална задача. Освен това, ако разработваме библиотека, нямаме никакъв контрол кой с какви цели ползва нашите класове.

  2. Което ми напомня, че трябваше да пиша статии за hashMap... При това отдавна.

    За написаното си прав. И при коментара за Garbage Collector в другата статия - тоже.

Добави коментар

Адресът на електронната поща няма да се публикува


*