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

Design Patterns : Singleton

"Gang Of Four" (GOF)-н 1994 онд гаргасан "Design Patterns: Elements of Reusable Object-Oriented Software" номны
23 pattern-н бараг хамгийн энгийн ойлгомжтой нь гэж хэлж болохоор нь энэ Singleton Pattern юм.

Singleton Pattern (SP)-г ямарваа нэг class-с тухайн системд (ажиллаж буй програм дотор) зөвхөн ганц л instance 
байлгах шаардлагатай үед ашигладаг. Өөрөөр хэлбэл, програмыг ажиллаж эхлээд дуусах хүртэл, тухайн class-с нэгээс
олон instance үүсэхгүй гэсэн үг. Системийн онцлогоос шалтгаалж, үнэхээр ганц л байх зайлшгүй шаардлагатай 
тохиолдолуудад, үүнийг ашиглана. Хамгийн өргөн хэрэглэгддэг жишээ бол Logger class юм. Програмаас гарч буй бүхий
л лог зөвхөн нэг л газраар дамжиж нэг л байдлаар хадгалагдана. Мөн өөр нэг хэрэглээ нь, тухайн програмын ажиллаж
буй орчины талаарх мэдээлэл байж болно. Java-н java.lang.Runtime class нь жишээ нь Singleton юм. Мөн ADF-н 
ADFFacesContext, ADFContext нь мөн л ялгаагүй Singleton.

Энэ нь private constructor, static method/variable зэргийг ойлгоход (хэрэглээ талаас нь) их хэрэг болох pattern
байгаа юм.


Бүтэц нь гэвэл их энгийн. Class-н constructor нь заавал private байна. Ингэснээрээ, тухайн class-н instance-г 
гаднаас үүсгэх боломжгүй болох юм. Мөн instance үүсгэх болон үүссэн instance-г нь авах зорилго, public 
хандалттай (хүсвэл өөр байж болно.) static method байна. Энэ method-н үүрэг  нь, тухайн class-с ямар нэг 
instance үүссэн эсэхийг шалгаад үүсээгүй бол үүсгээд түүнийгээ буцаах юм. Яагаад static байх шаардлагатай вэ 
гэхээр, static байж байж, ямар нэг instance-р дамжихгүйгээр(угаасаа байхгүй шд) шууд энэ method-г дуудах 
боломжтой болох юм. Энэ method-н нэрийг ихэвчлэн getInstance() гэж нэрлэдэг. Нэгэнт үүсгэсэн instance-аа нэг 
газар хадгалаад, дараагийн дуудалтан дээрээ буцаах хэрэгтэй учраас, private static variable ашиглана.


Implementations:

1.  Singleton class-н хамгийн энгийн implementation доорх хэлбэртэй байж болно.

    public class Singleton {
        private static Singleton final theInstance = new Singleton();

        public static Singleton getInstance() {
            return theInstance;
        }

        private Singleton() {
            System.out.println("constructor");
        }
    }

    Тухайн class load хийгдэх мөчид, шинэ instance үүсээд theInstance variable-д утгаа өгчихнө. Дараа нь 
    шаардлага гараад getInstance method дуудагдах үед зүгээр л тэр variable-нхаа утгыг буцаачихна. 

2.  Lazy-loading. Class-н шинэ instance үүсгэх процесс нь их хүнд (үнэтэй) бол, мөн class програм ажиллах
    бүрд ашиглагдахгүй байх магадлалтай тохиолдолд, дээрх арга тийм зөв сонголт болохгүй байх. Харин зөвхөн
    шаардлагатай үед л шинэ instance үүсгэдэг доорх арга илүү зөв болох талтай. Хамгийн эхний getInstance
    дуудагдах үед, шинээр instance үүснэ. Тэрний дараагаас зүгээр л variable-нхаа утгыг буцаана. 
    
    public class Singleton {
        private static Singleton final theInstance = null;

        public static Singleton getInstance() {
            if (theInstance == null) {
                theInstance = new Singleton();
            }

            return theInstance;
        }

        private Singleton() {
            System.out.println("constructor");
        }
    }

    Thread-Safe. Гэвч дээрх аргыг олон thread зэрэг хандах орчинд ашиглавал, нэгээс олон instance үүсчих
    боломжтой. Тэгэхээр getInstance() method-г synchronized болгосноор асуудлыг шийдэж болно.
    
        public static synchonized Singleton getInstance() {

    Гэвч, хамгийн эхний удаад л instance үүсгээд, бусад бүх дуудалтанд зүгээр бэлэн утга буцаадаг энэ method-г 
    synchronized болгосноороо, performance талаасаа их асуудалтай болж ирнэ. Зүгээр нэг утга буцаахын төлөө 
    lock/unlock/wait хийгдэнэ гэсэн үг. 

    Double-Checked-Locking. Дээрх асуудлыг шийдэхийн тулд, бид эхлээд variable-нхаа утгыг шалгаад, хэрэв
    instance үүссэн бол шууд буцаадаг, үүсээгүй бол synchronized block руу ордогоор хийе.

    public class Singleton {
        private static Singleton final theInstance = null;

        public static Singleton getInstance() {
            if (theInstance == null) {
                synchronized(Singleton.class) {
                    if (theInstance == null) {
                        theInstance = new Singleton();
                    }
                }
            }

            return theInstance;
        }

        private Singleton() {
            System.out.println("constructor");
        }
    }
    
    Ингэснээрээ, эхнийхээс бусад бүх дуудалт ямар нэг саадгүйгээр хурдан хэрэгжинэ. Харин эхний удаад, эхлээд
    null эсэхийг нь шалгаад, дараа нь synchronized block руу ороод, дахиад null эсэхийг шалгаад, тэгээд
    instance-аа үүсгэнэ. Яагаад яг адилхан шалгалтыг 2 удаа хийгээд байгаад гайхаж магадгүй. Яагаад гэвэл, жишээ
    нь t1 thread эхний шалгуурыг даваад, synchronized block руу орохын өмнөхөн нь t2 thread бас тэр шалгуурыг
    даваад орох ирэх боломжтой. Энэ үед хэрэв дотор талын шалгуур байхгүй байсан бол, 2 thread ээлжээр
    synchronized block руу орж instance-аа үүсгэх байсан юм. Ингээд бидний Singleton худлаа болох байлаа. Давхар
    шалгуур тавьж өгснөөрөө 2дахь thread synchronized block руу орсон ч, өмнө нь орсон thread нь үүсгэсэн байна
    уу, гэдгийг шалгаж байгаа юм. 

    Java-н хувьд Double-Checked-Locking арга нь "эвдэрхий" гэж үзэгддэг байна. Яагаад гэвэл, 
        1.  Thread A нь instance үүсээгүй байна гэж бодоод lock хийгээд instance-аа үүсгэж эхэллээ гэж бодъё
        2.  Java-д ялангуяа, тухайн constructor ажиллаж эхлэх үед л, санах ойд авсан (allocate) хаягаа шууд 
            хувьсагчдаа (theInstance) оноочихдог байна. Thread A-г instance-аа бүрэн үүсгэж дуусаагүй байх үед
            шүү дээ. Өөрөөр хэлбэл, манай static хувьсагч дутуу үүссэн обьектыг зааж байна гэсэн үг.
        3.  Яг энэ үед Thread B getInstance() method руу орж ирээд хувьсагчийнхаа утгыг хоосон байна уу гэж 
            шалгана. Мэдээж тэнд дутуу ч гэсэн нэг хаяг оноочихсон байгаа учир, түүнийгээ аваад буцна. Тэгээд 
            "дутуу үүссэн" instance-г ашиглах гэж оролдоод алдаа заана.

    Үүнээс үүдэн Java 5.0-н memory model-д өөрчлөлт орж, volatile түлхүүр үгийн ажиллах зарчим ч шинэчлэгдэж. 
    Volatile-г нэмж ашиглан дээрх аргыг алдаагүй болгосон байна.

3.  On-Demand-Holder. Нэгэнт double-checked-locking нь эвдэрхий гэж үзэгдсэн учир, мөн synchronized,
    volatile гэх мэт их "үнэтэй" аргуудыг ашиглаж буй учир, илүү хөнгөн аргыг бодож олцгоожээ. Энэ нь бидний
    эхний аргыг inner class ашиглан хийх юм. 
    
    public class Singleton {
        private static class SingletonHolder {
            private static final Singleton theInstance = new Singleton();
        }

        public static Singleton getInstance() {
            return SingletonHolder.theInstance;
        }

        private Singleton() {
            System.out.println("constructor");
        }
    }

    Singleton class нь load хийгдэж байх үед, SingletonHolder class load хийгдэхгүй. Хэзээ load хийгдэх вэ
    гэхээр, getInstance() method дуудагдах үед л хийгдэнэ. Тэр бол ямар ч Singleton-н instance үүсэхгүй гэсэн
    үг. Энэ нь lazy-loading гэдгийг нь батална. Харин getInstance() method дуудагдахад, JVM SingletonHolder-г
    load хийх хэрэгтэйгээ мэдээд (мэдээж өмнө нь хийгээгүй бол шүү дээ) load хийж эхэлнэ. Java-н ямар нэг 
    class-г load хийх үйлдэл нь өөрөө serial буюу давхар дуудагдах асуудалгүй учир бид SingletonHolder-н load
    хийгдэж, доторх Singleton-н reference-дээ шинэ intance үүсгэжн оноож өгөх процесс нь аюулгүй гэдэгт бүрэн
    итгэж болно. Энэ нь thread-safe гэдгийг нь харуулна. Нэгэнт class load хийгдэж, бүрэн хамгаалалтын доор шинэ
    instance-аа үүсгэсэн болохоор, getInstance() method-н хийх ажил нь ердөө л тэр reference-н утгыг буцаах юм.

4.  Enum. "Effective Java" номонд Joshua Bloch-н танилцуулсан арга. Нэгэнт Java-н enum нь lazy байдлаар,
    classload хийгдэх үед ажилладаг болохоор, мөн тухайн enum доторх тооны л instance-ууд үүсдэг учир, ганцхан
    элементтэй enum үүсгэх нь Singleton-г хэрэгжүүлэх сонгодог арга болж байгаа юм.

    public enum Singleton {
    INSTANCE;
        public void execute (String arg) {
                // perform operation here 
        }
    }

    Энд ямар ч getInstance гэх мэт static method, variable хэрэггүй, дуудах, ашиглахад ч амар.


Singleton pattern-ы талаар ерөнхийд нь гэвэл нэг иймэрхүү, мэдээж үлдээсэн, дутуу мэдээлэл зөндөө байгаа, мөн
ухаад л байвал ухаад л байхаар юм билээ.

Бусад pattern-ы адилаар энэ pattern-г ашиглах газар гэж бий, ашиглахгүй газар гэж бий. Буруу газраа ашиглах нь 
огт ашиглаагүйгээсээ илүүтэй хортой байж болох. Доорх линкүүдэд жишээ нь өгүүлсэн байгаа. 

References:
http://serkank.wordpress.com/2009/04/16/singleton-pattern-uzerine/
http://tech.puredanger.com/2007/07/03/pattern-hate-singleton/
http://tech.puredanger.com/2007/06/15/double-checked-locking/
http://en.wikipedia.org/wiki/Singleton_pattern
http://en.wikipedia.org/wiki/Double-checked_locking