Java әзірлеушісіне арналған сұхбаттардағы сұрақтар мен жауаптарды талдау. 9-бөлім

Отшашу! Бағдарламашы болу оңай емес. Сіз үнемі үйренуіңіз керек, әрқашан жаңа нәрсені үйренуіңіз керек. Бірақ, кез келген басқа бизнестегі сияқты, ең қиыны - бастау, мақсатқа бірінші қадам жасау. Сіз осы сайтта отырып, осы мақаланы оқып жатқандықтан, сіз бірінші қадамды аяқтадыңыз. Бұл дегеніміз, енді сіз жол бойында жылдамдықты төмендетпей немесе өшірмей, мақсатыңызға мақсатты түрде жетуіңіз керек. Егер мен дұрыс түсінсем, сіздің мақсатыңыз Java әзірлеушісі болу немесе егер сіз болсаңыз, біліміңізді арттыру. Олай болса, сіз дұрыс жердесіз, өйткені біз 250+ Java әзірлеушісімен сұхбат сұрақтарының кең тізімін талдауды жалғастырамыз. Жалғастырайық!

Жинақтар

84. Итераторлар және олардың қолданылуы туралы айтып беріңіз

Коллекциялар Java әзірлеушісінің кез келген сұхбатындағы сүйікті тақырыптардың бірі болып табылады және коллекция иерархиясы туралы айтқанда, үміткерлер оның Жиынтық интерфейсінен басталатынын жиі айтады . Бірақ бұл дұрыс емес, өйткені бұл интерфейстің үстінде тағы бір интерфейс бар - Iterable . Бұл интерфейс ағымдағы жинақ үшін Итератор нысанын шақыруға мүмкіндік беретін iterator() әдісін білдіреді. Және бұл Итератор нысаны дегеніміз не ? Итератор – пайдаланушыға белгілі бір жинақтың жүзеге асырылуын білуді қажет етпестен, коллекция арқылы жылжу және элементтерді қайталау мүмкіндігін қамтамасыз ететін нысан. Яғни, бұл коллекцияның белгілі бір жеріне қарайтын элементтердің қандай да бір көрсеткіші. Итератордың келесі әдістері бар:

• hasNext() – егер көрсеткіштен кейін орналасқан элемент болса, ақиқат мәнін қайтарады (бұл әдіс жинақтың соңына жеткен-жетпегенін білуге ​​мүмкіндік береді);
• next() – көрсеткіштен кейінгі келесі элементті қайтарады. Егер жоқ болса, NoSuchElementException жіберіледі . Яғни, бұл әдісті қолданбас бұрын, элементтің бар екеніне көз жеткізген дұрыс - hasNext() көмегімен ;
• remove() - келесі() әдісін пайдаланып коллекциядан алынған соңғы элементті жояды . Remove () шақырылғанға дейін next () ешқашан шақырылмаса , ерекше жағдай шығарылады - IllegalStateException ;
• forEachRemaining(<Тұтынушы>) - жинақтың әрбір элементімен өткізілген әрекетті орындайды (әдіс Java 8-де пайда болды).

Мұнда талқыланған итератор әдістерін пайдаланып тізім арқылы қайталау және оның барлық элементтерін жоюдың шағын мысалы келтірілген:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

Консоль келесіні көрсетеді: Бұл элементтерді жою сәтті болғанын білдіреді. Бізде итератор болғаннан кейін біз барлық элементтерді экранға басып шығару әдісін пайдалана аламыз:

iterator.forEachRemaining(x -> System.out.print(x));

Бірақ осыдан кейін итератор одан әрі пайдалану үшін жарамсыз болады, өйткені ол бүкіл тізімді айналып өтетіндіктен, ал кәдімгі иераторда кері қайтару әдістері жоқ. Мұнда біз біртіндеп LinkedList- ке жақындаймыз , атап айтқанда, оның listIterator() әдісі , ол итератордың жаңартылған түрін - ListIterator қайтарады . Қалыпты (стандартты) итератор әдістерінен басқа, оның қосымшалары бар:

• add(<Element>) - тізімге жаңа элементті кірістіреді;
• hasPrevious() – көрсеткіштің алдында орналасқан элемент болса (алдыңғы элементтің бар-жоғын) ақиқат мәнін қайтарады ;
• nextIndex() – көрсеткіштен кейінгі келесі элемент тізіміндегі индексті қайтарады;
• oldingi() - алдыңғы элементті қайтарады (көрсеткішке дейін);
• previousIndex() – алдыңғы элементтің индексін қайтарады;
• set(<Элемент>) - келесі() немесе алдыңғы() әдістерімен қайтарылған соңғы элементті ауыстырады .

Көріп отырғаныңыздай, бұл итератордың функционалдығы әлдеқайда қызықты: ол екі бағытта қозғалуға мүмкіндік береді және элементтермен жұмыс істеу кезінде қолыңызды босатады. Сондай-ақ, адамдар итераторлар туралы сөйлескенде, олар кейде үлгінің өзін білдіреді. Қиындыққа тап болмас үшін және бұл туралы сенімді түрде айту үшін Итератор үлгісі туралы осы мақаланы оқыңыз .

85. Java Collection Framework жүйесінде коллекция иерархиясы қандай?

Java тілінде екі жинақ иерархиясы бар. Бірінші иерархия келесі құрылымы бар Жинақ иерархиясының өзі болып табылады : Ол өз кезегінде келесі ішкі жинақтарға бөлінеді:

• Жиын – ретсіз бірегей (қайталанbyteын) элементтері бар жиын ретінде деректер құрылымын сипаттайтын интерфейс . Интерфейс стандартты іске асыруға ие - TreeSet , HashSet және LinkedHashSet .
• Тізім – нысандардың реттелген тізбегін сақтайтын деректер құрылымын сипаттайтын интерфейс. Тізімде қамтылған даналарды осы жинақтағы индексі бойынша енгізуге және жоюға болады (массивке ұқсас, бірақ динамикалық өлшемді өзгерту арқылы). Интерфейс стандартты іске асыруға ие - ArrayList , Vector ( ескірген және іс жүзінде пайдаланылмаған деп саналады ) және LinkedList .
• Кезек - FIFO - Бірінші кірген бірінші шығыс ережесіне сәйкес элементтерді кезек түрінде сақтайтын деректер құрылымын сипаттайтын интерфейс . Интерфейстің келесі стандартты іске асырулары бар: LinkedList (иә, ол кезекті де жүзеге асырады) және PriotityQueue .

Жинақтардың екінші иерархиясы Map , оның келесі құрылымы бар: Бұл жинақта ішкі жинақтарға бөлінулер жоқ (себебі Карта иерархиясының өзі ішкі жинақ сияқты, бірақ бөлек жатыр). Стандартты картаны іске асыру - Hashtable (ескірген деп саналады), LinkedHashMap және TreeMap . Шындығында, Collection туралы сұрағанда , әдетте екі иерархияны да білдіреді.

86. ArrayList-тің ішкі құрылымы қандай?

ArrayList массивке ұқсас, бірақ динамикалық түрде кеңейту мүмкіндігі бар. Бұл нені білдіреді? Шындығында, ArrayList кәдімгі массив негізінде жұмыс істейді, атап айтқанда, ол элементтерді ішкі массивте сақтайды (оның әдепкі өлшемі - 10 ұяшық). Ішкі массив толған кезде жаңа массив жасалады, оның өлшемі мына формуламен анықталады:

<размерТекущегоМассива> * 3 / 2  + 1

Яғни, егер массивіміздің өлшемі 10 болса, жаңасының өлшемі: 10 * 3/2 + 1 = 16. Содан кейін бірінші (ескі) массивтің барлық мәндері оған көшіріледі. жергілікті System.arraycopy () әдісі және бірінші жиым жойылады. Шын мәнінде, ArrayList динамикалық кеңеюі осылай жүзеге асырылады . Ең көп қолданылатын ArrayList әдістерін қарастырайық : 1. add(<Элемент>) – элементті массивтің соңына (соңғы бос ұяшыққа) қосады және алдымен осы массивте бос орын бар-жоғын тексереді. Егер ол жоқ болса, элементтері көшірілетін жаңа массив жасалады. Бұл операцияның логарифмдік күрделілігі O(1). Ұқсас әдіс бар - add(<Индекс>,<Элемент>) . Ол элементті тізімнің (массивтің) соңына емес, аргумент ретінде келген индексі бар белгілі бір ұяшыққа қосады. Бұл жағдайда логарифмдік күрделілік оның қосылған жеріне байланысты өзгереді:

• егер бұл тізімнің шамамен басы болса, логарифмдік күрделілік O(N) мәніне жақын болады, өйткені жаңасының оң жағында орналасқан барлық элементтерді бір ұяшыққа оңға жылжыту керек болады;
• егер элемент ортаға кірістірілсе - O(N/2) себебі бізге тізім элементтерінің жартысын ғана бір ұяшықты оңға жылжыту керек.

Яғни, бұл әдістің логарифмдік күрделілігі элементтің қай жерге енгізілгеніне байланысты O(N) ден O(1) аралығында болады. 2. set(<Индекс>,<Элемент>) - тізімдегі көрсетілген орынға элемент жазады. Егер сол позицияда әлдеқашан элемент болса, оны қайта жазады. Бұл операцияның логарифмдік күрделілігі O(1) болып табылады, өйткені ешқандай ығысулар жоқ: тек массивтегі индекс бойынша іздеу, біз есімізде O(1) күрделілігі бар және элементті жазу. 3. remove(<индекс>) – элементті ішкі массивтегі индексі бойынша жою. Тізімнің соңында жоқ элементті жойған кезде, элементті жойғаннан кейін қалған бос орынды жабу үшін оның оң жағындағы барлық элементтерді бір ұяшықты солға жылжыту керек. Сондықтан логарифмдік күрделілік қосу(<Индекс>,<Элемент>) сияқты болады , егер элемент ортасында болса - O(N/2) - өйткені элементтердің жартысын бір солға жылжыту керек. Тиісінше, егер ол басында болса - O(N). Егер соңында ол O(1) болса, ештеңені жылжытудың қажеті жоқ. Осы тақырыпты тереңірек зерттегісі келетіндер үшін мен осы сілтемені ArrayList сыныбының талдауы бар мақалаға қалдырамын .

87. LinkedList ішкі құрылымы қандай?

Егер ArrayList ішкі массивтегі элементтерді қамтыса, онда LinkedList қос байланысқан тізім түрінде болады. Бұл әрбір элементте алдыңғы элементке ( алдыңғы ) және келесіге ( келесі ) сілтеме бар екенін білдіреді. Бірінші элементтің алдыңғысына сілтемесі жоқ (ол бірінші), бірақ ол тізімнің басы болып саналады, ал LinkedList-те оған тікелей сілтеме бар. Соңғы элементте, шын мәнінде, келесі элемент жоқ, ол тізімнің соңғы бөлігі болып табылады, сондықтан LinkedList ішінде оған тікелей сілтеме бар . Сондықтан тізімнің басына немесе соңына қол жеткізудің логарифмдік күрделілігі O(1) болып табылады. ArrayList- те тізім ұлғайған кезде ішкі массив ұлғайды, бірақ мұнда бәрі оңайырақ болады - элементті қосқанда, бірнеше сілтемелер жай ғана өзгереді. Ең көп қолданылатын LinkedlList әдістерін қарастырайық : 1. add(<Elelement>) - тізімнің соңына қосу, яғни. соңғы элементтен кейін (5) келесідей жаңа элементке сілтеме қосылады . Жаңа элементте алдыңғы элемент ретінде соңғы (5) сілтемесі болады . Мұндай операцияның логарифмдік күрделілігі O(1) болады, өйткені тек соңғы элементке сілтеме қажет және есіңізде болса, құйрықтың LinkedList- тен тікелей сілтемесі бар және оған қол жеткізудің логарифмдік күрделілігі минималды. 2. add(<Индекс>,<Элемент>) – элементті индекс бойынша қосу. Элементті, мысалы, тізімнің ортасына қосқанда, басынан және құйрығынан (екі жағында) элементтер алдымен қажетті орын табылмайынша қайталанады. Егер біз үшінші және төртінші (жоғарыдағы суретте) арасына элементті кірістіргіміз келсе, онда дұрыс орынды іздеу кезінде үшінші элементтің келесі сілтемесі жаңасына нұсқайды. Жаңасы үшін алдыңғы сілтеме үшіншіге нұсқайды. Сәйкесінше, төртінші элементтің сілтемесі - алдыңғы - жаңа элементті көрсетеді, ал жаңа элементтің келесі сілтемесі төртінші элементті көрсетеді: Бұл әдістің логарифмдік күрделілігі жаңа элементке берілген индекске байланысты болады:

• егер ол басына немесе құйрығына жақын болса, ол O(1) мәніне жақындайды, өйткені шын мәнінде элементтерді қайталау қажет болмайды;
• ортасына жақын болса, онда O(N/2) - басынан және құйрығынан элементтер қажетті элемент табылғанша бір уақытта сұрыпталады.

3. set(<Индекс>,<Элемент>) - тізімдегі көрсетілген орынға элемент жазады. Бұл операцияның логарифмдік күрделілігі қайтадан элементтің басына, құйрығына немесе ортасына қаншалықты жақын орналасқанына байланысты O(1) мен O(N/2) аралығында болады. 4. remove(<индекс>) - элементті тізімнен алып тастап, жойылатын элементке дейін келетін элементті ( алдыңғы ) жойылғаннан кейін келетін элементке сілтеме жасайды ( келесі ). Және керісінше: жойылатын элементтен кейін келетін элемент жойылатын элементтен бұрын келетін элементке қатысты болуы үшін: Нәтиже индекс бойынша қосуға кері процесс ( add(<Индекс>,<Элемент>) ). LinkedList ішкі құрылымы туралы көбірек білгісі келетіндер үшін осы мақаланы оқуды ұсынамын .

88. HashMap ішкі құрылымы қандай?

Java әзірлеушісімен сұхбаттасу кезінде ең танымал сұрақтардың бірі болуы мүмкін. HashMap v кілт-мән жұптарымен жұмыс істейді . Олар HashMapv ішінде қалай сақталады ? HashMap ішінде түйіндердің массиві бар:

Node<K,V>[] table

Әдепкі бойынша, массив өлшемі 16 және ол элементтермен толтырылған сайын екі еселенеді ( LOAD_FACTOR мәніне жеткенде - толықтықтың белгілі бір пайызы, әдепкі бойынша ол 0,75 ). Әрбір түйін кілттің, кілттің, мәннің және келесі элементке сілтеменің хэшін сақтайды: Іс жүзінде «келесі элементке сілтеме» әрбір элементтің сілтемесі бар жеке байланыстырылған тізіммен жұмыс істейтінімізді білдіреді. келесісі. Яғни, HashMap деректерді жеке байланыстырылған тізімдер массивінде сақтайды. Бірақ мен бірден ескертемін: кесте массивінің бір ұяшығында бірнеше элементтерден тұратын ұқсас дара байланыстырылған тізімге сілтеме болса, бұл жақсы емес. Бұл құбылыс соқтығыс деп аталады . Бірақ бірінші нәрсе. put әдісі арқылы жаңа жұптың қалай сақталатынын көрейік . Алдымен кілттің hachCode() codeы алынады. Сондықтан хэшмап дұрыс жұмыс істеуі үшін бұл әдіс кілттер ретінде қайта белгіленген сабақтарды алуыңыз керек. Содан кейін бұл хэш codeы ішкі әдісте - hash() - кесте массивінің өлшеміндегі санды анықтау үшін пайдаланылады . Әрі қарай, алынған нөмірді пайдаланып, кесте массивінің белгілі бір ұяшығына қол жеткізіледі . Мұнда бізде екі жағдай бар:

1. Ұяшық бос - онда жаңа Түйін мәні сақталады .
2. Ұяшық бос емес – пернелердің мәні салыстырылады. Егер олар тең болса, жаңа Түйін мәні ескінің үстінен жазады, егер олар тең болмаса, келесі элементке қол жеткізіледі және оның кілтімен салыстырылады... Жаңа мән кейбір ескінің үстінен жазғанша немесе оның соңына жеткенше осылай жалғасады. жалғыз байланыстырылған тізім және сол жерде соңғы элемент ретінде сақталады.

Элементті кілт бойынша іздеу кезінде ( get(<key>) әдісі ), кілттің хэшcodeы есептеледі, содан кейін оның массив ішіндегі мәні hash() көмегімен және алынған санды пайдаланып кесте массивінің ұяшығы табылады. , онда іздеу түйіндерді санау және қажетті түйіннің кілтін ағымдағы кілтпен салыстыру арқылы жүзеге асырылады. Картадағы операциялар , идеалды жағдайда, O(1) алгоритмдік күрделілігіне ие, өйткені олар массивке қатынасады және есіңізде болса, элементтер санына қарамастан, массивтегі операциялардың күрделілігі O(1) болады. . Бірақ бұл идеалды. Пайдаланылатын жиым ұяшығы бос болмағанда (2) және ол жерде әлдеқашан түйіндер болса, алгоритмдік күрделілік сызықтық O(N) мәніне айналады, себебі енді дұрыс орынды табу алдында элементтерді қайталау қажет. Мен мұны айта алмаймын: Java 8-ден бастап, егер жеке байланыстырылған тізім түйінінде 8-ден астам элемент (соқтығыс) болса, ол екілік ағашқа айналады. Бұл жағдайда алгоритмдік күрделілік енді O(N) емес, O(log(N)) болады - бұл басқа мәселе, солай емес пе? HashMap - бұл үлкен тақырып және адамдар сұхбат кезінде ол туралы сұрақтар қойғанды ​​ұнатады. Сондықтан, мен сізге егжей-тегжейлі түсінуге кеңес беремін (ол тісіңізден секіретін етіп). Жеке өзім HashMap сұрақтарынсыз сұхбат алған емеспін . Сіз бұл мақалада HashMap- ке терең бойлай аласыз . Бұл бүгінге, жалғасы...