Java иштеп чыгуучусу үчүн интервьюдан алынган суроолордун жана жооптордун анализи. 9-бөлүк

Фейерверк! Программист болуу оңой эмес. Дайыма үйрөнүү керек, ар дайым жаңы нерсени үйрөнүү керек. Бирок, башка бизнестегидей эле, эң кыйын нерсе бул баштоо, максатыңызга биринчи кадам таштоо. Жана сиз бул сайтта отуруп, бул макаланы окуп жатканыңыз үчүн, сиз биринчи кадамды бүтүрдүңүз. Бул эми сиз максатыңызга максаттуу кадам ташташыңыз керек дегенди билдирет. Эгер мен туура түшүнсөм, сиздин максатыңыз Java иштеп чыгуучусу болуу же эгер сиз болсоңуз, бorмиңизди жогорулатуу. Эгер ошондой болсо, анда сиз туура жердесиз, анткени биз 250+ Java иштеп чыгуучусунун интервью суроолорунун кеңири тизмесин талдоону улантабыз. уланталы!

Коллекциялар

84. Итераторлор жана алардын колдонулушу жөнүндө айтып бериңиз

Коллекциялар Java иштеп чыгуучуларынын ар кандай маегинде сүйүктүү темалардын бири болуп саналат жана коллекция иерархиясы жөнүндө сөз кылганда, талапкерлер көбүнчө ал Collection интерфейсинен башталат деп айтышат . Бирок бул туура эмес, анткени бул интерфейстин үстүндө дагы бир интерфейс бар - Iterable . Бул интерфейс учурдагы коллекция үчүн Iterator an objectисин чакырууга мүмкүндүк берген iterator() ыкмасын билдирет. Жана бул Итератор an objectиси деген эмне ? Итератор - бул коллекция боюнча жылдыруу жана колдонуучуга белгилүү бир коллекцияны ишке ашырууну билбестен элементтерди кайталоо мүмкүнчүлүгүн камсыз кылган an object. Башкача айтканда, бул коллекциянын элементтерине карата кандайдыр бир көрсөткүч, ал андагы белгилүү бир жерди карайт. Итератордо төмөнкү ыкмалар бар:

• hasNext() - эгер көрсөткүчтөн кийин жайгашкан элемент бар болсо, чындыкты кайтарат (бул ыкма коллекциянын аягына жеткенин билүүгө мүмкүндүк берет);
• next() - көрсөткүчтөн кийинки элементти кайтарат. Эгерде эч ким жок болсо, NoSuchElementException ыргытылат . Башкача айтканда, бул ыкманы колдонуудан мурун, элементтин бар экенине ынануу жакшы - using hasNext() ;
• remove() - кийинки() ыкмасын колдонуу менен коллекциядан алынган акыркы элементти жок кылат . Эгерде next() эч качан remove() чакырылганга чейин чакырылбаган болсо, анда өзгөчө учур чыгарылат - 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());

Консол төмөнкүнү көрсөтөт: Бул элементтерди алып салуу ийгorктүү болду дегенди билдирет. Бизде итератор болгондон кийин, экранга бардык элементтерди басып чыгаруу ыкмасын колдонсок болот:

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

Бирок мындан кийин, итератор андан ары колдонуу үчүн жараксыз болуп калат, анткени ал бүт тизмени кыдырып чыгат жана кадимки итератордо артка кайтуу ыкмалары жок. Бул жерде биз акырындык менен LinkedList , тактап айтканда, анын listIterator() ыкмасына жакындайбыз , ал итератордун модернизацияланган түрүн - ListIterator кайтарат . Кадимки (стандарт) итератор ыкмаларынан тышкары, бул дагы кошумчалары бар:

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

Көрүнүп тургандай, бул итератордун функционалдуулугу алда канча кызыктуу: ал эки тарапка тең кыймылга мүмкүндүк берет жана элементтер менен иштөөдө колуңузду бошотот. Ошондой эле, адамдар итераторлор жөнүндө айтканда, алар кээде үлгүнүн өзүн билдирет. Кыйынчылыкка кабылбаш үчүн жана бул тууралуу ынанымдуу сүйлөңүз, Итератор үлгүсү жөнүндө бул макаланы окуңуз .

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

Javaда эки коллекция иерархиясы бар. Биринчи иерархия төмөнкү түзүлүшү менен Коллекция иерархиясынын өзү болуп саналат : Ал, өз кезегинде, төмөнкү чакан жыйнактарга бөлүнөт:

• Set – мындай берorштер структурасын иретсиз уникалдуу (кайталанбаган) элементтерди камтыган жыйынды катары сүрөттөгөн интерфейс . Интерфейстин стандарттык ишке ашыруулары бар - TreeSet , HashSet жана LinkedHashSet .
• Тизме – an objectтердин иреттелген ырааттуулугун сактаган маалымат структурасын сүрөттөгөн интерфейс. Тизмеде камтылган инстанциялар бул коллекциядагы индекси боюнча киргизorши жана жок кылынышы мүмкүн (массивге окшош, бирок динамикалык өлчөмүн өзгөртүү менен). Интерфейстин стандарттуу ишке ашыруулары бар - ArrayList , Vector ( эскирген жана иш жүзүндө колдонулbyte ) жана LinkedList .
• Кезек FIFO-Биринчи кирген биринчи чыгып эрежеси боюнча элементтерди кезек түрүндө сактаган маалымат структурасын сүрөттөгөн интерфейс . Интерфейстин төмөнкү стандарттуу ишке ашыруулары бар: LinkedList (ооба, ал кезекти да ишке ашырат) жана PriotityQueue .

Коллекциялардын экинчи иерархиясы Карта болуп саналат , анын төмөнкү структурасы бар: Бул коллекцияда подколлекцияларга бөлүнүүлөр жок (анткени Карта иерархиясынын өзү подколлекция сыяктуу, бирок өзүнчө жайгашкан). Стандарттык Картанын ишке ашыруулары - Hashtable (эскерилген деп эсептелет), LinkedHashMap жана TreeMap . Чынында, Коллекция жөнүндө сураганда , эки иерархия тең колдонулат.

86. ArrayListтин ички структурасы кандай?

ArrayList массивге окшош, бирок динамикалык түрдө кеңейүү мүмкүнчүлүгү бар. Бул эмнени билдирет? Чындыгында ArrayList кадимки массивдин негизинде иштейт, тактап айтканда, элементтерди ички массивде сактайт (анын демейки өлчөмү 10 клетка). Ички массив толгондо жаңы массив түзүлөт, анын өлчөмү формула менен аныкталат:

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

Башкача айтканда, биздин массивдин өлчөмү 10 болсо, жаңысынын өлчөмү: 10 * 3/2 + 1 = 16. Андан кийин, биринчи (эски) массивдин бардык маанилери ага көчүрүлөт. жергorктүү System.arraycopy () ыкмасы , жана биринчи массив жок кылынат. Чынында, ArrayListтин динамикалык кеңейиши ушундайча ишке ашат . Келгиле, эң көп колдонулган ArrayList ыкмаларын карап көрөлү : 1. add(<Элемент>) - элементти массивдин аягына (акыркы бош уячага) кошот жана алгач бул массивде боштуктун бар же жок экенин текшерет. Эгерде ал жок болсо, жаңы массив түзүлөт, ага элементтер көчүрүлөт. Бул операциянын логарифмдик татаалдыгы O(1). Ушундай эле ыкма бар - кошуу(<Индекс>,<Элемент>) . Ал элементти тизменин (массивдин) аягына эмес, аргумент катары келген индекси бар белгилүү бир уячага кошот. Бул учурда, логарифмдик татаалдык анын кошулган жерине жараша айырмаланат:

• эгерде бул болжол менен тизменин башталышы болсо, логарифмдик татаалдык 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 маалыматтарды жалгыз байланышкан тизмелердин массивинде сактайт. Бирок мен дароо белгилеп кетем: table массивинин бир уячасында бирден ашык элементтен турган окшош жалгыз байланышкан тизмеге шилтеме болгондо, бул жакшы эмес. Бул көрүнүш кагылышуу деп аталат . Бирок биринчи кезекте. Келгиле, put ыкмасын колдонуу менен жаңы жуп кантип сакталганын карап көрөлү . Биринчиден, ачкычтын hachCode() codeу алынат. Ошондуктан, хэшмап туура иштеши үчүн , бул ыкма ачкыч катары жокко чыгарылган сабактарды алышыңыз керек. Бул хэш-code андан кийин ички ыкмада колдонулат - hash() - table массивинин өлчөмүндөгү санды аныктоо . Андан кийин, алынган санды колдонуу менен, table массивинин белгилүү бир уячасына кирүүгө болот . Бул жерде бизде эки учур бар:

1. Клетка бош - анда жаңы Түйүндүн мааниси сакталат .
2. Клетка бош эмес - баскычтардын мааниси салыштырылат. Эгерде алар бирдей болсо, жаңы Түйүндүн мааниси эскинин үстүнөн жазат, эгерде алар тең эмес болсо, кийинки элементке кирип, анын ачкычы менен салыштырылат... Жана ушул сыяктуу жаңы маани эскинин үстүнөн жазмайынча же анын аягына чейин уланат. жалгыз шилтемеленген тизме жана ал жерде акыркы элемент катары сакталат.

Ачкыч боюнча элементти издөөдө ( get(<key>) методу ), ачкычтын hashCode codeу эсептелет, андан кийин hash() аркылуу массив ичиндеги анын мааниси жана натыйжадагы санды колдонуу менен table массивинин уячасы табылат . , мында издөө түйүндөрдү санап, керектүү түйүндүн ачкычын учурдагы ачкыч менен салыштыруу аркылуу ишке ашырылат. Картадагы операциялар идеалдуу кырдаалда O(1) алгоритмдик татаалдыгына ээ, анткени алар массивге кирүүдө жана эсиңизде болгондой, элементтердин санына карабастан массивдеги операциялар O(1) татаалдыгына ээ. . Бирок бул идеалдуу. Колдонулуп жаткан массив уячасы бош эмес болгондо (2) жана ал жерде мурунтан эле түйүндөр бар болсо, алгоритмдик татаалдык сызыктуу O(N) болуп калат, анткени азыр керектүү жерди табуудан мурун элементтерди кайталоо керек. Мен муну айтпай кое албайм: Java 8ден баштап, эгер жалгыз байланышкан тизме түйүнүндө 8ден ашык элемент (кагылышуу) болсо, ал бинардык даракка айланат. Бул учурда, алгоритмдик татаалдык мындан ары O(N) болбойт, бирок O(log(N)) - бул башка маселе, туурабы? HashMap - бул чоң тема жана адамдар интервьюларда ал жөнүндө суроолорду бергенди жакшы көрүшөт. Ошондуктан, мен сизге аны майда-чүйдөсүнө чейин түшүнүүгө кеңеш берем (ал тишиңизден секирип кетиши үчүн). Жеке мен HashMap суроолору жок интервью алган жокмун . Сиз бул макалада HashMapга терең сүңгүүнү таба аласыз . Бул бүгүнкү күндө, уландысы ...