LINKED LIST / HASHMAP / EQUALS AND HASHCODE CONTRACT /
LINKED LIST
Linked listlerde her hansi item-i almaq ucun pointerlerden istifade edirik.
element silende diger butun elementler surusur ancaq linkedlistden element silende sadece
pointer isaresi deyisdirilir.
Bu arada pointer sadece adres bilgisini ozunde tutan bir deyiskendir.
Linked listlerin olcusu dinamikdir
Linked list dezavantajlarindan saysaq onun item-i goturmesi daha gec isleyir cunki burada
basdan sona butun list pointerlerle scan edilib tapilir ve bir de pointerler yer tutdugu ucun yaddasda
elave olaraq linkedlistler daha cox yer tutur yaddasda (RAM-da).
Linked Listler de 2 cur olur SLL(singly linked list) DLL(soubly linked list) .SLL-de pointer ozunden
sonrakini gosterir , DLL -de ise hem evvelki hem sonraki nodu gosteren pointer olur.
sonrakini gosterir , DLL -de ise hem evvelki hem sonraki nodu gosteren pointer olur.
Ve elave circular list de var hansiki ilk node ve son node bir birine bagli olur.
Normal LL-de hemise on node null-u point edirdise burada head node-u point edir.
Bezi linkedlistle bagli well known interview suallari :
- Reverse linkedlist:
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next; // save next
curr.next = prev; // reverse
prev = curr; // reverse
curr = nextTemp;
}
return prev;
}
Burada mentiq head-den baslayaraq pointerlerin istiqametini deyismekdir eslinde.
- Length of LL:
public int length(){
int count=0;
Node current = this.head;
while(current != null){
count++;
current=current.next()
}
return count;
}
En son tail node null-a point etdiyi ucun bucur yoxlama ve counter ile uzunlugu tapa bilersiniz.
Ve ya rekursiya ile de bunu ede bielrsiniz :
public int length(Node current){
if(current == null){ //base case
return 0;
}
return 1+length(current.next());
}
- LL orta elementi tapmaq:
1-ci yanasma - uzunluq tapilib /2 -ci elementi goturulur
2-ci yanasma - slow ve fast pointer olur fast 2 2 artir , slow ise 1 1 ,
fast en sona catanda slow -un gosterdiyi element en ortadakidir.
fast en sona catanda slow -un gosterdiyi element en ortadakidir.
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
HASHMAP
Hashmap java-da collection framework altinda yer alir map interface-inden impliment edir ve hashing prinsipi ile isleyir.Yeni key ve valuenin link olunmasi ucun
hash metodundan (Object to integer code) istfde edilir.Bu bize axtaris ve indexleme zamani komek olur. Biz hashmap-a valueni put(key,value) ile elave edib get(key) ile cekirik.
hash metodundan (Object to integer code) istfde edilir.Bu bize axtaris ve indexleme zamani komek olur. Biz hashmap-a valueni put(key,value) ile elave edib get(key) ile cekirik.
Synchronized olmamasi (thread safe -dir multiple thread arasinda paylasila bilmez) ve null qebul etmesini saymasaq HashTable ile eynidir.
Arxada eslinde Hashmap node-lardan ibaretdir ve bu node-larda linkedlist ve array strukturlarindan istifade edilir. Hemin node-larda asagidaki fieldler var heresinde :
Hashmap-in default size-i 16-dir ( 0 to 15) ,ancaq eger size kifayet etmire 0.75(75%) ile resize bucket artimi gedir arxada. Ve size-da bir mehdudyyet de yoxdur.
BU arada hashMap-in capacity-si ne qeder mumkun tutumu varsa onu , size-i ise hazirda ne qeder dolduru onu qaytarir.
BU arada hashMap-in capacity-si ne qeder mumkun tutumu varsa onu , size-i ise hazirda ne qeder dolduru onu qaytarir.
He indi gelin baxaq put() metodu cagrildiqda arxada ne bas verir :
- HashMap<String, Integer> map = new HashMap<>();
- map.put("Aman", 19);
1)Ilk olaraq “Aman” key-in hashCode-u hesablanir. Tutaqki 2657860 edir deyek.
2)Daha sonra hemin hashcode-a gore index hesablanir. Ve tutaqki bu da 4 edir :
Index bu dustura gore hesablanir : Index = hashcode(Key) & (n-1)
3) Ve bizim node 4-cu indexe yerlesdirilir
Tutaqki deyek artiq dolu olan index value aldiq basqa bir put ucun onde ne bas verir ?
Bu zaman evvelce equals() metodu ile baxilir ki key-ler eynidirmi eynidirse tebii ki en sonuncu ile evez edir.
Eger keyler ferqlidirse iki node obyekti linkedlist vasitesile link edir bir birine bu cur node bagliligi bir yerde bucket adlanir:
Eger keyler ferqlidirse iki node obyekti linkedlist vasitesile link edir bir birine bu cur node bagliligi bir yerde bucket adlanir:
Ve eslinde arxada her iki node eyni indexde yerlesir :
Bes get(key) nece calisir?
Bu zaman yene evvelce key-in hashcode-u daha sonra ona uygun olaraq index tapilir.Ve hemin indexde yerlesen ilk node -dan baslanlaraq key yoxlanilir eyni olan node goturulur.
Equls ve hashcode ?
Artiq dediklerimden yeqinki bildiz ki key olaraq eslinde Object vere bilirik sadece burda onemli olan hemin obyektin equals ve hashcode contract-ina emel etmesidir yeqni siz equals override edib obyektinizde
hashcode etmesez eslinde duz islemeyecek isteyirsiz gelin baxaq bir misal uzerinden :
hashcode etmesez eslinde duz islemeyecek isteyirsiz gelin baxaq bir misal uzerinden :
Equals and hashcode contract nedir ?
Burada run etsek eslinde equals metoduna hec girmeyecek get(key) zamani qaytara bilmeyecek Ayse sozunu. Niye? Cunki oyrendik ki, hashcode generate olunur ve ona esasen put proses gedir hashmap istifadesinde.
Belede eslinde arxada TelefonRehberi sinifimiz deyiskenleri eyni olsa da ferqli hashcode-lar arxada yaranacaq. Bunun ucun biz hashcode override edib onu hemin fieldlere esasen her hansi qayda ile almaqdir.
Belede eslinde arxada TelefonRehberi sinifimiz deyiskenleri eyni olsa da ferqli hashcode-lar arxada yaranacaq. Bunun ucun biz hashcode override edib onu hemin fieldlere esasen her hansi qayda ile almaqdir.
Artiq run etdikde “Ayse” sozunu geri ala bilecik cunki key kimi istifde olunan obyektimiz ucun put ederken istifade olunan hashcode eyni olmus olur ve HasMap hemin key-e uygun value-ni bize verecek.
Yorumlar
Yorum Gönder