Equals, HashCode and HashMap

java.lang.Object class-н equals(), hashCode() методууд болон HashMap-н талаар жаахан ярилцъя.

java.lang.Object нь Java-н бүхий л (бүр байж болох бүх) обьектуудын эх(эцэг ч юм уу) нь бөгөөд, бүгд энэ л
class-с удамшсан байдаг учраас энэ class-т тодорхойлогдсон методууд бүх class-уудад дамжиж очно. Тэдний нэг
нь equals юм. Equals нь 2 instance-н хоорондын тэнцэлийг шалгаад true false буцаадаг функц юм.
Эндээс "Обьектын тэнцэл гэж юу вэ" гэсэн асуулт гарч ирнэ.

Обьектын тэнцэл...

Java-д тэнцлийг тэнцүүгийн тэмдэг(==) болон equals методоор шалгадаг. Тэнцүүгийн тэмдэг нь primitive
төрлүүдийн хооронд тэнцүү эсэхийг шалгах ганц арга. Харин референс төрлүүдийн хувьд энэ операторыг
ашиглавал, 2 референсийг нэг обьект руу зааж буй эсэхийг л шалгана. Тэр 2 референс ижилхэн санах ойн хаяг
зааж байгаа эсэхийг шалгана гэсэн үг. (Хувьсагч гэдгийг 1-8  byte-н урттай, санах ойн нэг хэсэг гээд үзвэл,
референс болон primitive-үүдийн хооронд тэнцүүгийн тэмдэг маань нээх тийм ялгаатай үйлдэл хийхгүй л
байгаа юм.)

Харин цаад обьектын хувьд, тэнцүү эсэхийг шалгах ганц арга нь equals метод юм. Гэхдээ class болгоны "тэнцэх"
логик нь өөр өөр учир, class болгон өөрийн гэсэн equals методтой байх (override хийх) хэрэгтэй юм. Default
implementation буюу Object дээр байдаг хувилбар нь яг == шиг ажилладаг. Өөрөөр хэлбэл 2 обьект гээд байгаа
маань, яг үнэндээ санах ойдоо нэг л обьект бол true үгүй бол false буцаадаг.

Мэдээж, "Best code is no code" гэдэг шиг, онцын шаардлагагүй үед энэ метод-г override хийгээд байх хэрэггүй
бөгөөд дутуу үүсгэснээс огт үүсгээгүй байх нь илүү дээр. Онцийн шаардлага гэдэг нь, тухайн class-н field-үүд
нь ямар нэг утга илэрхийлдэг тэр утгыг нь ашиглаж, 2 өөр газраас үүссэн (санах ойд 2 өөр газар байрлаж
байгаа) instance-г харьцуулах, эсвэл list, map, set-д ашиглах бол override хийнэ гэсэн үг.

Тэгвэл ямар үед equals-г override хийх шаардлаггүй вэ?
    - Class-н instance-ууд нь хоорондоо, логик тэнцэтгэл шаардагдахгүй бол. Жишээ нь java.util.Random
      class-ын instance бүр нь өөр өөр байх ёстой учраас, equals-г implement хийх нь шал утгагүй юм.
    - Superclass нь хэрэгцээтэй логик-г нь equals дээрээ implement хийгээд өгцөн бол. Жишээ нь, ихэнх Set-н
      implementation-ууд AbstractSet-н, List-нхэн AbstractList-н equals-г ашигладаг. (Ашигладаг гэдэг нь,
      зүгээр л юу ч бичилгүй орхичиход л өөрөө ашиглачихна гэсэн үг. Тэрнээс ашиглах гээд ямар нэг юм
      хийгээд байх хэрэггүй.)
    - Class нь зөвхөн тодорхой хүрээнд ашиглагдах, тэр хүрээндээ equals нь ашиглагдахгүй гэдэг нь ойлгомжтой
      үед. Жишээ нь, private эсвэл default access modifier-тай class.
    - Class нь зөвхөн ганц л instance-тай байх тохиолдолд. Жишээ нь singleton.

За тэгвэл equals метод маань ямар байх ёстой гэсэн үг үү? 10 жилийн математик-н хичээл дээр гардаг дүрэмтэй
ер нь бол их төстэй.
    - reflexive, a = a, null биш байх бүх x-н хувьд x.equals(x) үргэлж true байна.
    - symmetric, if a = b then b = a, null биш байх бүх x, y-н хувьд x.equals(y) нь ямар утга буцаана
      y.equals(x) ч мөн тийм утга буцаана.
    - transitive, if a = b, b = c then a = c, null биш байх бүх x, y, z-н хувьд x.equals(y) болон
      y.equals(z) нь true бол x.equals(z) ч мөн true байна.
    - consistent, equals-т ашиглагдаж буй 2 instance-д өөрчлөлт ороогүй л бол, equals-н утга ямагт ижил
      байна. (цаг хугацаанаас хамаарч өөрчлөгдөхгүй)
    - null биш байх бүх x-н хувьд, x.equals(null) үргэлж false байна.

Эдгээр дүрмийг баримтлалгүй "алдаатай" бичигдсэн equals нь програмд тодорхойгүй асуудал үүсгэх ба асуудлын
шалтгааныг олох их хугацаа авсан ажил болох болно. Жишээ авч үзвэл,

1. Энгийнээр хэлбэл бүхий instance өөрөө өөртэйгөө тэнцүү байх ёстой. Энийг баримтлаагүй тохиолдолд, List
рүү дөнгөж нэмчихээд, нэмсэн reference-ээ ашиглаад contains-р шалгахад л false буцаана гэсэн үг.

2. Жишээ болгож доорх class-г харъя,

    Энэхүү Class-н хувьд cis.equals(s) нь үнэн байх боловч, s.equals(cis) нь худлаа байна. Алдаа нь юундаа
байна гэхээр String обьект-н equals методыг нь өөрчилж чадахгүй мөртлөө, чаддаг юм шиг String-тэй
харьцуулсанд байгаа юм.

3. Доорх 2 class-г хараарай, Point-н хувьд асуудалгүй ч, түүнээс удамшсан ColorPoint-д нь асуудал байна.

    Энэ жишээн дээр, нэг ижил цэг дээр байгаа, 3 өөр point-н талаар гарч байна. p1 нь p2-тойгоо, p2 нь
p3-тайгаа тэнцүү боловч, p1 нь p3-тайгаа тэнцэхгүй байна. Гэхдээ java дээр ч иймэрхүү жишээ байдаг байна.
(Date болон Timestamp).

    Энэхүү жишээний шийдэл нь "aggregation over inheritance" гэсэн Object-oriented-design-н зарчим юм.
Өөрөөр хэлбэл, Point гэсэн class-с ColorPoint-г удамшуулж үүсгэхийн оронд, ColorPoint дотор Point-н нэг
реферэнс-г байршуулах байдлаар шийдэж болох байлаа.

HashCode
    Equals-тай адил мөн л "цаанаасаа ирдэг" метод. Гол санаа нь, instance бүхэн өөрийгөө тодорхойлох ямар
нэг sтоон утгатай байх юм. Тэр тоон утга нь, хоорондоо "тэнцүү" 2 instance-н хувьд тэнцүү байх ёстой гэсэн
"бичигдээгүй хуультай". Энэ нь equals болон hashCode-н хоорондын уялдаа нь юм. Гэхдээ эсрэгээрээ, ижилхэн
hashCode-той 2 instance "тэнцүү" байх албагүй. Өөрөөр хэлбэл symmetric биш. Албагүй гэсэн болохоос, ёсгүй
гээгүй болохоор, hashCode, equals 2 маань symmetric ч байж болно, symmetric байвал бүүр л "сайн". (Гэхдээ
symmetric байна гэдэг боломжгүй зүйл л дээ.)

    Тэгэхээр доторх логик нь өөрчлөгдснөөр хоорондын уялдаа нь алдагдах учир equals-г override хийх бүрдээ
бас hashCode-оо "янзлах" хэрэгтэй болно.

    Мөн equals-н consistent гэдэг дүрэм энд ч бас хамааралтай, тухайн instance-т өөрчлөлт ороогүй л бол,
түүний hashCode нь үргэлж нэг ижил л байх ёстой.

    Жишээ болгож String-н hashCode-г харцгаая,

Арай хураангуй байдлаар гэвэл,
    

HashMap
    HashMap нь өөр өөрийн гэсэн давтагдахгүй дугаар бүхий "сагс"-нуудын цуглуулгатай бөгөөд сагс бүр нь
LinkedList-д түлхүүр-утгаа хадгалдаг. Шинээр түлхүүр-утга орж ирэх үед, түлхүүрийнх нь hashCode-г аваад тэр
дугаартай сагсанд очно, хэрэв сагс хоосон биш бол, түлхүүртэй "тэнцэх" элемент хүртэл явна. Хэрэв тийм
элемент олдвол, утгаа дараад бичнэ. Хэрэв олдохгүй бол, листэнд нэмж өгнө. Түлхүүр ашиглан HashMap-с утга
авах нь ч мөн адил, эхлээд түлхүүрийн hashCode бүхий дугаартай сагсан дээр очоод, equals методын true буцаах
елементийг олтлоо linkedList-р хэсээд олбол утгыг нь буцаагаад, олохгүй бол null буцаана.

    Яг эндээс hashCode болон equals-н "уялдаа" нь харагдах ёстой юм. Тэнцүү биш обьектууд ижил hashCode-той
байхыг давхцал гэх юм бол, хэдий чинээ их давхцалтай байна, сагсан дахь элементүүд төдий чинээ их байна.
Сагсан дахь элементүүд их байх тусам "хэсэх" шаардлага ихсэнэ. Тэр чинээгээрээ get болон put методууд
удаашрана. Харин давхцал үгүй бол, HashMap нь O(1) гэсэн хурдаар олно.

References
http://mdasgin.blogspot.com/2011/12/equals-metodu-nasl-yazlmal.html
http://stackoverflow.com/a/256447/1787373
http://eclipsesource.com/blogs/2012/09/04/the-3-things-you-should-know-about-hashcode/
http://stackoverflow.com/questions/15518418/whats-behind-the-hashcode-method-for-string-in-java
http://en.wikipedia.org/wiki/Java_hashCode()
https://infinitescript.com/2014/09/hashmap-internal-implementation-analysis-in-java/
http://www.dineshonjava.com/2013/06/how-does-java-hashmap-work-internally.html#.VCoY_fkab4R