🇬🇧 ❗️Hashtable. Collision.❗️

Hi, guys! Today I'd like to continue Hashtable chain of topics.
Previous I wanted to stopped on question:
- What if hashes are equal? 🤔🤔🤔

I should introduce the concept of collision in Hashtable. Simply to say, collision is a situation when hashes of two different keys produce the same result, thus, arranging the value (from key->value pair) to the same bucket (or index of array which is inside of the Hashmap). Let me give you a simple example to explain this concept:

You have key1->value1 and key2->value2. You want to put them into map. If you remember we put a value into the Hashmap by calculating the hash for its key. Let's say that hash(key1) is equal to 42 and hash(key2) is equal to 42. So, this is collision.

And you will have a question: what to do in this situation?
I'll shortly describe the solution which is implemented in HashMap.

The buckets inside of HashMaps are Lists. This means that if we already have an object with the same hash, then the second value is just added to the list.

Thus, if there are a lot of collisions inside of our Hashtable, then we could end up with O(N) [in worst case] speed for retrieval, since we will have to loop through all elements of the list associated with that hash.

❓But how can we solve this situation❓
🔽 You can share you answers in the comments.🔽

🇺🇿❗️Hashtable. Kolliziya.❗️

Hammaga salom! Bugun Hashtable mavzusini davom etamiz. Oldingi marta "Agar xeshlangan qiymatlar teng bo'lsachi? 🤔🤔🤔" degan savolda to'xtadik.

Bu yerda kolliziya tushunchasini kiritish lozim. Oddiy qilib aytganda, kolliziya - bu ikkita kalitning xeshlari teng bo'lgan holat. Bu degani HashMap realizatsiyasida shu ikkita kalitning xeshlari bitta bucketga (massivning indeksiga) yozilishi kerak bo'ladi. Keling bu holatni namunada ko'rib chiqamiz:

Sizda ikkita juft bor: kalit1->qiymat1 va kalit2->qiymat2. Siz bularni HashMap ga joylamoqchisiz. Esingizda bo'lsa, biz HashMap-ni ichiga qiymatni uning kalitining xeshi bo'yicha joylashtiramiz. Masalan, hash(kalit1) 42 teng bo'lsin va hash(kalit2) ham 42ga teng bo'lsin. Bu kolliziya holati.

Sizda savol tug'ilishi mumkin: bunday vaziatda nima qilish kerak?
HashMap-da ishlatilgan realizatsiyaga o'tsak, kolliziyaga uchragan kalit->qiymat juftlar List ma'lumotlar tuzilmasiga yoziladi.

Shunday qilib, kolliziya holati HashMap-dan ma'lumotni kalit bo'yicha olish tezligini O(1) dan O(N) ga [eng yomon holatda] tushurib yuboradi, chunki endi biz List-ni har bir qiymatini qarab chiqishimiz kerak.

❓Endi bu holatda nima qilsa bo'ladi❓
🔽 Javoblaringizni comment-larda bo'lishishingiz mumkin🔽

🇬🇧Practice

Hi, guys! Let's solve one easy problem, where you can use HashTable data structure.

🟢 Easy: 2248. Intersection of Multiple Arrays
👨‍💻 My solution: Java solution

Have fun!

🇺🇿 Amaliyot

Hammaga salom! Bugun bitta oson masalani yechamiz. Uni yechish uchun siz Hashtable ma'lumotlar tuzilmasini ishlatishingiz mumkin.

🟢 Oson: 2248. Intersection of Multiple Arrays
👨‍💻 Mening yechimim: Java solution

Omad!

🇬🇧Practice Again.

Hi, guys! Not that much from me today since it's the weekend.
Just one ❗️hard❗️👀👀👀 problem.

🔴 Hard: 980. Unique Paths III
👨‍💻 My solution: Java DFS readable code Solved | 91% time and 94% memory

Have fun😅😬😂!

🇺🇿 Yanada ko'proq amaliyot

Hammaga salom! Bugun dam olish kuni bo'lgani uchun ko'p narsa yozmayman.
Atiga 1ta ❗️qiyin❗️👀👀👀 masala.

🔴 Qiyin: 980. Unique Paths III
👨‍💻 Mening yechimim: Java DFS readable code Solved | 91% time and 94% memory

Vazifani mazza qilib bajarasiz degan umiddaman😅😬😂!

🇬🇧 equals() method in Java

Hi, guys! In order to understand how HashMap works in Java, we need to understand the contract of equals() and hashCode() methods inside of Object class. Let's cover the contract in Java docs for the first method.

There are five characteristics of relation between two objects which must be met. This relation must be:
- reflexive🪞: for any non-null reference value x, x.equals(x) should return true.
- symmetric 👉|👈: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
- transitive 🥴=🥴=🥴: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
- consistent❗️ : for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
- for any non-null reference value x, x.equals(null) should return false ❌.

This is taken from official java docs. For more info - check the link.

Note that contract of equals() in Java is pretty popular question on interviews.

🇺🇿 Javadagi equals() metodi

Hammaga salom! Java-da HashMap qanday ishlashini tushunish uchun Object klassidagi equals() va hashCode() metodlarining shartnomalarini bilishimiz kerak. Keling bu postda equals()-ning shartnomasini ko'rib chiqaylik.

Ikki obyekt o'rtasidagi munosabatning beshta xususiyati bajarilishi lozim. Bular:
- refleksiv🪞: null-ga teng bo'lmagan havolaning qiymatini x desak, x.equals(x) true qaytarishi lozim.
- simetrik 👉|👈: null-ga teng bo'lmagan havolalarning qiymatlarini x va y desak, x.equals(y) true qaytarishi lozim, agar faqat y.equals(x) true bo'lsa.
- tranzitiv🥴=🥴=🥴: null-ga teng bo'lmagan havolalarning qiymatlarini x, y va z desak va x.equals(y) true qaytarsa, va y.equals(z) true qaytarsa, x.equals(z) ham true qaytarishi shart.
- konsistent (doimiy)❗️: null-ga teng bo'lmagan havolalarning qiymatlarini x va y bo'lsin. Unda x.equals(y) bir nechta chaqiruv oshirsak, har doim true yoki har doim false qaytarishi kerak (agar chaqiruvlar orasida obyekt ma'lumotlari o'zgartirilmagan bo'lsa).
- null-ga teng bo'lmagan havolaning qiymatini x desak, x.equals(null) chaqirilsa, false❌ qaytarishi lozim.

Shu matnni rasmiy Java docs-dan oldim. Qo'shimcha ma'lumot uchun bu havolani tekshiring: havola.

E'tibor bering, Java-dagi equals() metodinig shartnomasi intervyularda (ishga olishda) juda ko'p uchraydigan savol.

🇬🇧 Practice

Hi, guys! Another day - another challenge🚀🚀🚀. Let's solve one interesting problem today.

It is a guessing game problem. The rules can be found here: Bulls and Cows.

🟡 Medium: 299. Bulls and Cows
👨‍💻 My solution:
Explained Java O(N) Solution Harder, Better, Faster, Stronger...

By the way, I wrote detailed explanation for my solution. Check it out.

Cheers!

🇺🇿 Amaliyot

Hammaga salom! Bugun mashqlar bajarish kuni. Keling bitta juda ham qiziq masalani yechamiz🚀🚀🚀.

Bu masala taxmin qilish o'yini asosida tuzilgan. O'yinning qoidalarini bu yerda topsangiz bo'ladi: Bulls and Cows.

🟡 O'rta daraja: 299. Bulls and Cows
👨‍💻 Mening yechimim:
Explained Java O(N) Solution Harder, Better, Faster, Stronger...

Yozgan yechimimni yaxshilab tushuntirishga harakat qilganman.

Omad!

🇬🇧 Practice

Hi, guys! Today it is a practice day again😁
I found two interesting problems for you!
You implement Stack data structure using only Queue data structure in first and, vice versa, implement Queue data structure using only Stack data structure.

🟢 Easy: 225. Implement Stack using Queues
👨‍💻 My solution: Java | Using 2 Queues

🟢 Easy: 232. Implement Queue using Stacks
👨‍💻 My solution: Java | 1 ms | Explained

Good luck!

🇺🇿 Amaliyot

Hammaga salom! Bugun ham masalalar yechamiz. Ikkita qiziqarli vazifa tayyorlab qo'ydim. Birinchisida Queue ma'lumotlar tuzilmasini (MT) ishlatib, Stack MTsini yaratishingiz kerak. Ikkinchisida esa Stack MTsini ishlatgan holda, Queue MTsini yozishingiz kerak bo'ladi.

🟢 Oson: 225. Implement Stack using Queues
👨‍💻 Mening yechimim: Java | Using 2 Queues

🟢 Oson: 232. Implement Queue using Stacks
👨‍💻 Mening yechimim: Java | 1 ms | Explained

Omad!

🇬🇧 Theory: hashCode() contract.

Hi, guys! Previously I wrote about equals() contract in Java. And now it is time to write about the contract of hashCode() in Java.

The general contract of hashCode is:

- Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

- If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

- It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
In other words, it is possible that non-equal objects may produce equal hash codes. Thus, this might lead to collision. I wrote a post about collisions here.

This info is taken from: Java Docs

🇺🇿 Nazariya: hashCode() shartnomasi.

Hammaga salom! Oldingi postlarning bittasida equals() shartnomasi haqida yozgan edim. Bugun esa hashCode() shartnomasini o'tamiz. Eslatib o'taman: bu mavzular HashMap-ning qanday ishlashini yaxshi tushunishda yordam beradi.

hashCode() shartnomasi quyidagicha:

- Java dasturi ishlayotgan paytda, agar obyekt ichidagi ma'lumotlar o'zgartirilmagan holda, hashCode() metodi shu obyektda bir va undan ko'p marta chaqirilsa, bu metod doimo bir integer sonini qaytarishi shart. Bu integer soni shu Java dasturining har xil bajarilishlarida bir xil bo'lib qolishi shart emas.

- Agar ikkita obyekt equals(Object) asosida teng bo'lsa, hashCode() metodini shu ikkita obyektlarda chaqirganimizda bir xil integer qiymat qaytarishi shart.

- Agar ikkita obyekt equals(Object) asosida teng bo'lmasa, ularning hashCode() metodlarini chaqirganimizda qaytarilgan integer sonlar farqli bo'lishi shart emas. Lekin dasturchi har doim yodda tutish kerak bo'lgan narsa shuki, teng bo'lmagan obyektlar hashCode() metodi chaqirilganida teng bo'lmagan integer sonlarni qaytarsa, bu narsa hash table-larni ishlashini yaxshilashi mumkin.
Oddiy til bilan aytsak, teng bo'lmagan obyektlar hashCode() chaqirilganida teng son qaytarishlari mumkin. Bu kolliziyaga olib kelishi mumkin. Kolliziya haqida bu yerda yozganman: Kolliziya.

Ma'lumotlar Java Docs-dan olingan.

🇬🇧 Practice. Hashtable.

Hi, guys! Today we are going to practice solving a problem using Hashtable data structure.
In this task you will have to apply a discount to each n-th bill.

🟡 Medium: 1357. Apply Discount Every n Orders
👨‍💻 My solution: Java 87% speed | 89% memory solutions

Try to write the fastest solution and share it in the comments.
Good luck!

🇺🇿 Amaliyot. Hashtable.

Hammaga salom! Bugun biz masalani Hashtable ma'lumotlar tuzilmasini ishlatgan holda yechishga harakat qilamiz.
Bermoqchi bo'lgan vazifada siz har bir n-chi chekning jamini chegirma bilan hisoblab berishingiz kerak.

🟡 O'rta daraja: 1357. Apply Discount Every n Orders
👨‍💻 Mening yechimim: Java 87% speed | 89% memory solutions

Mening fikrimcha, bu masalani Hashtable ishlatmasdan ham yechsa bo'ladi.
Eng tez ishlaydigan algoritm yozishga harakat qiling va comment-da bo'lishing.

Omad!

🇬🇧 Practice. Arrays.

Hi, guys! Today I'll give you a problem which I struggled with when I was learning Java. Sherali, my coursemate who taught us Java [I wrote about it here], challenged us to solve it. I remember that it took me immense amount of time to solve, one or two weeks I guess.
So, today's task is to return values of 2d array in spiral order.

🟡 Medium: 54. Spiral Matrix
👨‍💻 My solution: Java 100% Faster Solution

This time it took 25 minutes to write a solution which passed all the tests - which is impressive result for me.

Good luck!

🇺🇿 Amaliyot. Massivlar.

Hammaga salom! Bugun yechmoqchi bo'lgan masalamiz qiziq vazifalardan bittasi. Hali Sherali bizga Java o'rgatayotgan paytlarda [bu haqida post yozgan edim - havola], u bizga shu masalani bergan edi. Shu vazifani bajarish men uchun juda ham qiyin bo'lgani esimda. Bir yoki ikki hafta ketgan to'g'ri yechim topishim uchun.
Bugungi masala 2d massivni spiral holatda aylanib chiqish.

🟡 O'rta daraja: 54. Spiral Matrix
👨‍💻 Mening yechimim: Java 100% Faster Solution

Bu safar esa hamma testlardan o'tgan yechimni topish uchun chamasi 25 daqiqa ketdi. Men uchun bu juda katta natija.

Omad!

🇬🇧 Overriding equals() and hashCode()

Hi, guys! No problem solving for today.
I've prepared video on overriding equals() and hashCode() methods in Java. This video summarizes what we covered on these two methods so far. It's not that long - 6.5 minutes.

Link: Overriding equals and hashCode in Java - 039

Enjoy!