[מוזיק פּלייינג] דאַג לויד: דורך איצט איר וויסן אַ פּלאַץ וועגן ערייז, און איר וויסן אַ פּלאַץ וועגן לינגקט רשימות. און מיר ווע דיסקוטירן די פּראָס און קאָנס, מיר ווע דיסקאַסט אַז לינגקט רשימות קענען באַקומען ביגער און קלענערער, אָבער זיי נעמען זיך מער גרייס. ערייז זענען פיל מער סטראַיגהטפאָרוואַרד צו נוצן, אָבער זיי ניטאָ ריסטריקטיוו אין ווי פיל ווי מיר האָבן צו שטעלן די גרייס פון די מענגע אין דער זייער אָנהייב און דעמאָלט מיר ניטאָ סטאַק מיט עס. אבער אַז ס, מיר ווע שיין פיל ויסגעמאַטערט אַלע פון ​​אונדזער טעמעס וועגן לינגקט רשימות און ערייז. אָדער האָבן מיר? אפֿשר מיר קענען טאָן עפּעס אַפֿילו מער שעפעריש. און אַז סאָרט פון לענדס דער געדאַנק פון אַ האַש טיש. אַזוי אין אַ האַש טיש מיר רע געגאנגען צו פּרובירן פאַרבינדן אַ מענגע מיט אַ לינגקט רשימה. מיר ניטאָ געגאנגען צו נעמען די אַדוואַנטאַגעס פון די מענגע, ווי ראַנדאָם צוטריט, ווייל קענען צו נאָר גיין צו מענגע עלעמענט 4 אָדער מענגע עלעמענט 8 אָן ווייל צו יטעראַטע אַריבער. אַז ס שיין שנעל, רעכט? אבער מיר אויך ווילן צו האָבן אונדזער דאַטן סטרוקטור קענען צו וואַקסן און ייַנשרומפּן. מיר טאָן ניט דאַרפֿן, מיר טאָן ניט ווילן צו זיין ריסטריקטיד. און מיר ווילן צו קענען צו לייגן און אַראָפּנעמען זאכן זייער לייכט, וואָס אויב איר צוריקרופן, איז זייער קאָמפּלעקס מיט אַ מענגע. און מיר קענען רופן דעם נייַ זאַך אַ האַש טיש. און אויב ימפּלאַמענאַד ריכטיק, מיר ניטאָ סאָרט פון גענומען די אַדוואַנטאַגעס פון ביידע דאַטן סטראַקטשערז איר ווע שוין געזען, ערייז און לינגקט רשימות. ינסערשאַן קענען אָנהייבן צו טענד צו טייטאַ פון 1. טייטאַ מיר האָבן ניט טאַקע דיסקאַסט, אָבער טייטאַ איז נאָר די דורכשניטלעך פאַל, וואָס ס אַקטשאַוואַלי געגאנגען צו פּאַסירן. איר ניטאָ ניט שטענדיק געגאנגען צו האָבן די ערגסט פאַל סצענאַר, און איר ניטאָ ניט שטענדיק געגאנגען צו האָבן דער בעסטער פאַל סצענאַר, אַזוי וואָס ס די דורכשניטלעך סצענאַר? נו אַ דורכשניטלעך ינסערשאַן זיך אַ האַש טיש קענען אָנהייבן צו באַקומען נאָענט צו קעסיידערדיק צייַט. און דילישאַן קענען באַקומען נאָענט צו קעסיידערדיק צייַט. און לוקאַפּ קענען באַקומען נאָענט צו קעסיידערדיק צייַט. טהאַט'ס-- מיר טאָן ניט האָבן אַ דאַטע ביניען נאָך אַז קענען טאָן אַז, און אַזוי דעם שוין סאָונדס ווי אַ שיין גרויס זאַך. מיר ווע טאַקע מיטאַגייטיד די דיסאַדוואַנטידזשיז פון יעדער אויף זייַן אייגן. צו באַקומען דעם פאָרשטעלונג אַפּגרייד כאָטש, מיר דאַרפֿן צו ריטינגק ווי מיר לייגן דאַטן אין די ביניען. ספּעסיפיקאַללי מיר ווילן די דאַטן זיך צו זאָגן אונדז ווו עס זאָל גיין אין די ביניען. און אויב מיר דעמאָלט דאַרפֿן צו זען אויב עס ס אין די ביניען, אויב מיר דאַרפֿן צו געפֿינען עס, מיר ווילן צו קוקן אין די דאַטע ווידער און קענען צו Effectively, ניצן די דאַטן, ראַנדאַמלי צוטריט עס. נאָר דורך קוקן אין די דאַטע מיר זאָל האָבן אַ געדאַנק פון ווו פּונקט מיר ניטאָ געגאנגען צו געפינען עס אין די האַש טיש. איצט די דאַונסייד פון אַ האַש טיש איז אַז זיי ניטאָ טאַקע שיין שלעכט ביי אָרדערינג אָדער סאָרטינג דאַטע. און אין פאַקט, אויב איר אָנהייב צו נוצן זיי צו סדר אָדער סאָרט דאַטע איר פאַרלירן אַלע פון ​​די אַדוואַנטאַגעס איר ביז אַהער האט אין טערמינען פון ינסערשאַן און דילישאַן. די צייַט ווערט נעענטער צו טייטאַ פון N, און מיר ווע בייסיקלי רעגרעססעד זיך אַ לינגקט רשימה. און אַזוי מיר נאָר ווילן צו נוצן האַש טישן אויב מיר טאָן ניט זאָרגן וועגן צי דאַטע איז אויסגעשטעלט. פֿאַר די קאָנטעקסט אין וואָס איר וועט נוצן זיי אין קס50 איר מיסטאָמע טאָן ניט זאָרגן אַז די דאַטן איז אויסגעשטעלט. אַזוי אַ האַש טיש איז אַ קאָמבינאַציע פון צוויי בוילעט ברעקלעך מיט וואָס מיר ניטאָ באַקאַנט. דער ערשטער איז אַ פֿונקציע, וואָס מיר יוזשאַוואַלי רופן אַ האַש פֿונקציע. און אַז האַש פֿונקציע איז געגאנגען צו צוריקקומען עטלעכע ניט-נעגאַטיוו ינטעגער, וואָס מיר יוזשאַוואַלי רופן אַ האַשקאָדע, גוט? די רגע שטיק איז אַ מענגע, וואָס איז טויגעוודיק פון סטאָרינג דאַטן פון די טיפּ מיר ווילן צו שטעלן אין די דאַטן סטרוקטור. מיר וועט האַלטן אַוועק אויף די לינגקט רשימה עלעמענט פֿאַר איצט און נאָר אָנהייבן מיט די באַסיקס פון אַ האַש טיש צו באַקומען דיין קאָפּ אַרום אים, און דעמאָלט מיר וועט אפֿשר קלאַפּ דיין מיינונג אַ ביסל ווען מיר פאַרבינדן ערייז און לינק רשימות צוזאַמען. די גרונט געדאַנק כאָטש איז מיר נעמען עטלעכע דאַטן. מיר לויפן אַז דאַטן דורך די האַש פֿונקציע. און אַזוי די דאַטן איז פּראַסעסט און עס ספּיץ אויס אַ נומער, גוט? און דעריבער מיט אַז נומער מיר נאָר קראָם די דאַטע מיר ווילן צו קראָם אין די מענגע בייַ אַז אָרט. אַזוי פֿאַר בייַשפּיל מיר האָבן אפֿשר דעם האַש טיש פון סטרינגס. עס ס גאַט 10 יסודות אין עס, אַזוי מיר קענען פּאַסיק 10 סטרינגס אין עס. זאל ס זאָגן מיר ווילן צו האַש יוחנן. אַזוי יוחנן ווי די דאַטן מיר ווילן צו אַרייַנלייגן אין דעם האַש טיש ערגעץ. וואו טאָן מיר לייגן עס? נו טיפּיקלי מיט אַ מענגע אַזוי ווייַט מיר מיסטאָמע וואָלט לייגן עס אין מענגע אָרט 0. אבער איצט מיר האָבן דעם נייַ האַש פֿונקציע. און לאָזן ס זאָגן אַז מיר לויפן יוחנן דורך דעם האַש פֿונקציע און עס ס ספּיץ אויס 4. גוט אַז ס ווו מיר רע געגאנגען צו וועלן צו שטעלן יוחנן. מיר ווילן צו שטעלן יוחנן אין מענגע אָרט 4, ווייַל אויב מיר האַש יוחנן אַגאַינ-- לאָזן ס זאָגן שפּעטער מיר ווילן צו זוכן און זען אויב יוחנן יגזיסץ אין דעם האַש טאַבלע-- אַלע מיר דאַרפֿן צו טאָן איז לויפן עס דורך דער זעלביקער האַש פונקציאָנירן, באַקומען די נומער 4 אויס, און קענען צו געפינען יוחנן מיד אין אונדזער דאַטן סטרוקטור. אַז ס שיין גוט. זאל ס זאָגן מיר איצט טאָן דעם ווידער, מיר ווילן צו האַש Paul. מיר ווילן צו לייגן Paul אין דעם האַש טיש. זאל ס זאָגן אַז דאָס מאָל מיר לויפן Paul דורך די האַש פֿונקציע, די האַשקאָדע וואָס איז דזשענערייטאַד איז 6. נו איצט מיר קענען לייגן Paul אין די מענגע אָרט 6. און אויב מיר דאַרפֿן צו קוקן אַרויף צי Paul איז אין דעם האַש טיש, אַלע מיר דאַרפֿן צו טאָן איז לויפן Paul דורך די האַש פֿונקציע ווידער און מיר רע געגאנגען צו באַקומען 6 אויס ווידער. און דעמאָלט מיר נאָר קוק ביי מענגע אָרט 6. איז Paul עס? אויב אַזוי, ער ס אין די האַש טיש. איז Paul ניט עס? ער ס ניט אין דער האַש טיש. עס ס שיין סטראַיגהטפאָרוואַרד. איצט ווי טאָן איר דעפינירן אַ האַש פונקציאָנירן? גוט עס ס טאַקע קיין שיעור צו די נומער פון מעגלעך האַש פֿעיִקייטן. אין פאַקט עס ס אַ נומער פון טאַקע, טאַקע גוט אָנעס אויף די אינטערנעט. עס ס אַ נומער פון טאַקע, טאַקע שלעכט אָנעס אויף די אינטערנעט. עס ס אויך שיין גרינג צו שרייַבן אַ שלעכט איינער. אַזוי וואָס מאכט זיך אַ גוט האַש פֿונקציע, רעכט? נו אַ גוט האַש פֿונקציע זאָל נוצן בלויז די דאַטע ווייל האַשעד, און אַלע פון ​​די דאַטן ווייל האַשעד. אַזוי מיר טאָן ניט ווילן צו נוצן אַניטהינג-- מיר טאָן ניט ינקאָרפּערייט עפּעס אַנדערש אנדערע ווי די דאַטע. און מיר ווילן צו נוצן אַלע פון ​​די דאַטן. מיר טאָן ניט ווילן צו נאָר נוצן אַ שטיק פון עס, מיר ווילן צו נוצן אַלע פון ​​עס. א האַש פֿונקציע זאָל אויך זיין דעטערמיניסטיק. וואָס טוט אַז מיינען? גוט עס מיטל אַז יעדער מאָל מיר פאָרן די פּינטלעך זעלביקער שטיק פון דאַטן אין די האַש פֿונקציע מיר שטענדיק באַקומען די זעלבע האַשקאָדע אויס. אויב איך פאָרן יוחנן אין די האַש פֿונקציע איך באַקומען אויס 4. איך זאָל קענען צו טאָן אַז 10,000 מאל און איך וועט שטענדיק באַקומען 4. אַזוי ניט ראַנדאָם נומערן Effectively קענען זיין ינוואַלווד אין אונדזער האַש טאַבלעס-- אין אונדזער האַש פֿעיִקייטן. א האַש פֿונקציע זאָל אויך יוואַנלי פאַרשפּרייטן דאַטע. אויב יעדער צייַט איר לויפן דאַטן דורך די האַש פֿונקציע איר באַקומען די האַשקאָדע 0, אַז ס מיסטאָמע נישט אַזוי גרויס, רעכט? איר מיסטאָמע ווילן צו גרויס אַ קייט פון האַש קאָודז. אויך זאכן קענען ווערן פאַרשפּרייטן אויס איבער די טיש. און אויך עס וואָלט זיין גרויס אויב טאַקע ענלעך דאַטע, ווי יוחנן און יונתן, אפֿשר זענען צעשפּרייט צו וועגן פאַרשידענע לאָוקיישאַנז אין די האַש טיש. אַז וואָלט זיין אַ פייַן מייַלע. דאָ ס אַ בייַשפּיל פון אַ האַש פֿונקציע. איך געשריבן דעם איין זיך פריער. עס ס ניט אַ הויפּט גוט האַש פֿונקציע פֿאַר סיבות אַז טאָן ניט טאַקע בער געגאנגען אין רעכט איצט. אבער טאָן איר זען וואָס ס געגאנגען אויף דאָ? עס מיינט ווי מיר ניטאָ דיקלערינג אַ בייַטעוודיק גערופֿן סאַכאַקל און באַשטעטיקן עס גלייַך צו 0. און דעמאָלט משמעות איך בין טאן עפּעס אַזוי לאַנג ווי סטרסטר [דזש] איז ניט גלייַך צו באַקקסלאַש 0. וואָס בין איך טאן עס? דעם איז בייסיקלי נאָר אן אנדער וועג פון ימפּלאַמענינג [? סטרל?] און דיטעקטינג ווען איר ווע ריטשט די סוף פון די שטריקל. אַזוי איך טאָן ניט האָבן צו אַקטשאַוואַלי רעכענען די לענג פון די שטריקל, איך בין נאָר ניצן ווען איך שלאָגן די באַקקסלאַש 0 כאַראַקטער איך וויסן איך ווע ריטשט די סוף פון די שטריקל. און דעמאָלט איך בין געגאנגען צו האַלטן יטעראַטינג דורך אַז שטריקל, אַדינג סטרסטר [דזש] צו סאַכאַקל, און דעמאָלט אין די סוף פון די טאָג געגאנגען צו צוריקקומען סאַכאַקל מאָד האַש_מאַקס. בייסיקלי אַלע דעם האַש פֿונקציע איז טאן איז אַדינג אַרויף אַלע פון ​​די אַסקי וואַלועס פון מיין שטריקל, און דעמאָלט עס ס אומגעקערט עטלעכע האַשקאָדע מאָדדעד דורך האַש_מאַקס. עס ס מיסטאָמע די גרייס פון מיין מענגע, רעכט? איך טאָן ניט ווילן צו זיין געטינג האַש קאָודז אויב מיין מענגע איז פון גרייס 10, איך טאָן ניט ווילן צו זיין געטינג אויס האַש קאָודז 11, 12, 13, איך קענען ניט שטעלן זאכן אין די לאָוקיישאַנז פון די מענגע, אַז וואָלט זיין ומלעגאַל. איך'ד לייַדן אַ סעגמאַנטיישאַן שולד. איצט דאָ איז אן אנדער שנעל באַזונדער. בכלל איר ניטאָ מיסטאָמע נישט געגאנגען צו ווילן צו שרייַבן דיין אייגן האַש פֿעיִקייטן. עס איז אַקשלי אַ ביסל פון אַ קונסט, ניט אַ וויסנשאַפֿט. און עס ס אַ פּלאַץ וואָס גייט אין זיי. די אינטערנעט, ווי איך געזאגט, איז פול פון טאַקע גוט האַש פֿעיִקייטן, און איר זאָל נוצן די אינטערנעט צו געפינען האַש פֿעיִקייטן ווייַל עס ס טאַקע נאָר מין פון אַ ומנייטיק וויסט פון צייַט צו שאַפֿן דיין אייגן. איר קענען שרייַבן פּשוט אָנעס פֿאַר טעסטינג צוועקן. אבער ווען איר אַקטשאַוואַלי זענען געגאנגען צו אָנהייבן כאַשינג דאַטן און סטאָרינג עס זיך אַ האַש טיש איר ניטאָ מיסטאָמע געגאנגען צו ווילן צו נוצן עטלעכע פֿונקציע וואָס איז געווען דזשענערייטאַד פֿאַר איר, אַז יגזיסץ אויף די אינטערנעט. אויב איר טאָן נאָר זיין זיכער צו ציטירן דיין קוואלן. עס ס קיין סיבה צו פּלאַגיאַריזע עפּעס דאָ. דער קאָמפּיוטער וויסנשאַפֿט קהל איז באשטימט גראָוינג, און טאַקע וואַלועס אָפֿן מקור, און עס ס טאַקע וויכטיק צו ציטירן דיין קוואלן אַזוי אַז מען קענען באַקומען אטריביאציע די אַרבעט אַז זיי ניטאָ טאן צו די נוץ פון די קהל. אַזוי שטענדיק זיין סורע-- און ניט נאָר פֿאַר האַש פֿעיִקייטן, אָבער בכלל ווען איר נוצן קאָד פון אַן אַרויס מקור, שטענדיק ציטירן דיין מקור. געבן קרעדיט צו דער מענטש וואס האט עטלעכע פון ​​די אַרבעט אַזוי איר טאָן ניט האָבן צו. גוט אַזוי לאָזן ס ריוויזיט דעם האַש טיש פֿאַר אַ רגע. דאס איז ווו מיר לינקס אַוועק נאָך מיר ינסערטיד יוחנן און Paul אין דעם האַש טיש. צי איר זען אַ פּראָבלעם דאָ? איר זאל זען צוויי. אבער אין באַזונדער, טאָן איר זען דעם מעגלעך פּראָבלעם? וואָס אויב איך האַש רינגאָ, און עס טורנס אויס אַז נאָך פּראַסעסינג אַז דאַטן דורך די האַש פֿונקציע רינגאָ אויך דזשענערייטאַד די האַשקאָדע 6. איך ווע שוין גאַט דאַטן אין האַשקאָדע-- מענגע אָרט 6. אַזוי עס ס מיסטאָמע געגאנגען צו זיין אַ ביסל פון אַ פּראָבלעם פֿאַר מיר איצט, רעכט? מיר רופן דעם אַ צונויפשטויס. און די צונויפשטויס אַקערז ווען צוויי ברעקלעך פון דאַטן לויפן דורך די זעלבע האַש פֿונקציע טראָגן דער זעלביקער האַשקאָדע. מאַשמאָעס מיר נאָך ווילן צו באַקומען ביידע ברעקלעך פון דאַטן אין די האַש טיש, אַנדערש מיר וואָלט ניט זיין פליסנדיק רינגאָ אַרביטרעראַלי דורך די האַש פֿונקציע. מיר מאַשמאָעס ווילן צו באַקומען רינגאָ אין אַז מענגע. ווי טאָן מיר טאָן עס כאָטש, אויב ער און Paul ביידע טראָגן האַשקאָדע 6? מיר טאָן ניט ווילן צו אָווועררייט Paul, מיר ווילן Paul צו זיין דאָרט אויך. אַזוי מיר דאַרפֿן צו געפֿינען אַ וועג צו באַקומען יסודות אין די האַש טיש אַז נאָך ייַנגעמאַכץ אונדזער שנעל ינסערשאַן און שנעל קוק אַרויף. און איין וועג צו האַנדלען מיט עס איז צו טאָן עפּעס גערופֿן לינעאַר פּראָובינג. ניצן דעם אופֿן אויב מיר האָבן אַ צונויפשטויס, געזונט, וואָס טוט מיר טאָן? נו מיר קענען ניט שטעלן אים אין מענגע אָרט 6, אָדער וועלכער האַשקאָדע איז דזשענערייטאַד, זאל ס שטעלן אים אין האַשקאָדע פּלוס 1. און אויב אַז ס פול לאָזן ס שטעלן אים אין האַשקאָדע פּלוס 2. די נוץ פון דעם ווייל אויב ער ס נישט פּונקט ווו מיר טראַכטן ער איז, און מיר האָבן צו אָנהייבן שאַרף, אפֿשר מיר טאָן ניט האָבן צו גיין צו ווייַט. אפֿשר מיר טאָן ניט האָבן צו זוכן אַלע N יסודות פון די האַש טיש. אפֿשר מיר האָבן צו זוכן אַ פּאָר פון זיי. און אַזוי מיר ניטאָ נאָך טענדינג צו אַז דורכשניטלעך פאַל ווייל נאָענט צו 1 ווס נאָענט צו N, אַזוי אפֿשר אַז וועט אַרבעט. אַזוי לאָזן ס זען ווי דעם זאל אַרבעט אויס אין פאַקט. און לאָזן ס זען אויב אפֿשר מיר קענען דיטעקט די פּראָבלעם אַז זאל פּאַסירן דאָ. זאל ס זאָגן מיר האַש באַרט. אַזוי איצט מיר רע געגאנגען צו לויפן אַ נייַ שטעלן פון סטרינגס דורך די האַש פֿונקציע, און מיר לויפן באַרט דורך די האַש פונקציאָנירן, מיר באַקומען האַשקאָדע 6. מיר נעמען אַ קוק, מיר זען 6 איז ליידיק, אַזוי מיר קענען שטעלן באַרט עס. איצט מיר האַש ליסאַ און אַז אויך דזשענערייץ האַשקאָדע 6. נו איצט אַז מיר ניטאָ ניצן דעם לינעאַר פּראָובינג אופֿן מיר אָנהייבן בייַ 6, מיר זען אַז 6 איז פול. מיר קענען ניט שטעלן ליסאַ אין 6. אזוי ווו טאָן מיר גיין? זאל ס גיין צו 7. 7 ס ליידיק, אַזוי אַז מעשים. אַזוי לאָזן ס שטעלן ליסאַ דאָרט. איצט מיר האַש האָמער און מיר באַקומען 7. גוט געזונט מיר וויסן אַז 7 ס פול איצט, אַזוי מיר קענען ניט שטעלן האָמער דאָרט. אַזוי לאָזן ס גיין צו 8. איז 8 בנימצא? יאָ, און 8 ס נאָענט צו 7, אַזוי אויב מיר האָבן צו אָנהייבן שאַרף מיר ניטאָ ניט געגאנגען צו האָבן צו גיין צו ווייַט. און אַזוי לאָזן ס שטעלן האָמער אין 8. איצט מיר האַש מאַגגיע און קערט 3, דאַנקען גוטסקייט מיר ניטאָ קענען צו נאָר שטעלן מאַגגיע דאָרט. מיר טאָן ניט האָבן צו טאָן קיין סאָרט פון פּראָובינג פֿאַר וואָס. איצט מיר האַש מאַרדזש, און מאַרדזש אויך קערט 6. נו 6 איז פול, 7 איז פול, 8 איז פול, 9, אַלע רעכט דאַנקען גאָט, 9 איז ליידיק. איך קענען לייגן מאַרדזש ביי 9. שוין מיר קענען זען אַז מיר ניטאָ סטאַרטינג צו האָבן דעם פּראָבלעם ווו איצט מיר ניטאָ סטאַרטינג צו אויסשטרעקן דאס מין פון ווייַט אַוועק פון זייער האַש קאָודז. און אַז טייטאַ פון 1, אַז דורכשניטלעך פאַל פון ווייל קעסיידערדיק צייַט, איז סטאַרטינג צו באַקומען אַ ביסל מאָרע-- סטאַרטינג צו טענד אַ ביסל מער צו טייטאַ פון ען. מיר 'רע סטאַרטינג צו פאַרלירן אַז מייַלע פון ​​האַש טישן. דעם פּראָבלעם אַז מיר נאָר געזען איז עפּעס גערופֿן קלוסטערינג. און וואָס ס טאַקע שלעכט וועגן קלוסטערינג איז אַז אַמאָל איר איצט האָבן צוויי עלעמענטן וואָס זענען זייַט דורך זייַט עס מאכט עס אַפֿילו מער מסתּמא, איר האָבן טאָפּל די געלעגנהייַט, אַז איר ניטאָ געגאנגען צו האָבן אן אנדער צונויפשטויס מיט וואָס קנויל, און דעם קנויל וועט וואַקסן דורך איינער. און איר וועט האַלטן גראָוינג און גראָוינג דיין ליקעליהאָאָד פון בעת ​​אַ צונויפשטויס. און יווענטשאַוואַלי עס ס נאָר ווי שלעכט ווי נישט סאָרטינג די דאַטע אין אַלע. די אנדערע פּראָבלעם כאָטש איז מיר נאָך, און אַזוי ווייַט אַרויף צו דעם פונט, מיר ווע נאָר געווען סאָרט פון שכל וואָס אַ האַש טיש איז, מיר נאָך נאָר האָבן צימער פֿאַר 10 סטרינגס. אויב מיר ווילן צו פאָרזעצן צו האַש די בירגערס פון Springfield, מיר קענען נאָר באַקומען 10 פון זיי אין עס. און אויב מיר פּרובירן און לייגן אַ 11 אָדער 12, מיר טאָן ניט האָבן אַ פּלאַץ צו שטעלן זיי. מיר קען נאָר זיין ספּיננינג אַרום אין קרייזן טריינג צו געפֿינען אַ ליידיק אָרט, און מיר אפֿשר באַקומען סטאַק אין אַ אַנלימאַטאַד שלייף. אַזוי דעם סאָרט פון לענדז צו דער געדאַנק פון עפּעס גערופֿן טשאַינינג. און דאָס איז ווו מיר רע געגאנגען צו ברענגען לינגקט רשימות צוריק אין די בילד. וואָס אויב אַנשטאָט פון סטאָרינג נאָר די דאַטן זיך אין די מענגע, יעדער עלעמענט פון דער מענגע קען האַלטן קייפל ברעקלעך פון דאַטן? נו אַז טוט נישט מאַכן זינען, רעכט? מיר וויסן אַז אַ מענגע קענען בלויז האָלד-- יעדער עלעמענט פון אַ מענגע קענען בלויז האַלטן איין שטיק פון דאַטן פון וואָס דאַטן טיפּ. אבער וואָס אויב אַז דאַטן טיפּ איז אַ לינגקט רשימה, רעכט? אזוי וואָס אויב יעדער עלעמענט פון די מענגע איז אַ טייַטל צו די קאָפּ פון אַ לינגקט רשימה? און דעמאָלט מיר קען בויען די לינגקט רשימות און וואַקסן זיי אַרביטרעראַלי, ווייַל לינגקט רשימות לאָזן אונדז צו וואַקסן און ייַנשרומפּן אַ פּלאַץ מער פלעקסיבלי ווי אַ מענגע טוט. אַזוי וואָס אויב מיר איצט נוצן, מיר ליווערידזש דעם, רעכט? מיר אָנהייבן צו וואַקסן די קייטן אויס פון די מענגע לאָוקיישאַנז. איצט מיר קענען פּאַסיק אַ אַנלימאַטאַד סומע פון ​​דאַטע, אָדער ניט אַנלימאַטאַד, אַ אַרבאַטרערי סומע פון דאַטע, אין אונדזער האַש טיש אָן אלץ פליסנדיק אין די פּראָבלעם פון צונויפשטויס. מיר ווע אויך ילימאַנייטאַד קלוסטערינג דורך טאן דעם. און געזונט מיר וויסן אַז ווען מיר אַרייַנלייגן אין אַ לינגקט רשימה, אויב איר צוריקרופן פון אונדזער ווידעא אויף לינגקט רשימות, יינציקווייַז לינגקט רשימות און דאַבלי לינגקט רשימות, עס ס אַ קעסיידערדיק צייַט אָפּעראַציע. מיר ניטאָ פּונקט אַדינג צו די פראָנט. און פֿאַר קוקן אַרויף, געזונט מיר טאָן וויסן וואָס קוקן אַרויף אין אַ לינגקט רשימה קענען זיין אַ פּראָבלעם, רעכט? מיר האָבן צו זוכן דורך עס פון אָנהייב צו סוף. עס ס קיין ראַנדאָם צוטריט אין אַ לינגקט רשימה. אבער אויב אָנשטאָט ווייל איינער לינגקט רשימה ווו אַ לוקאַפּ וואָלט זיין אָ פון N, מיר איצט האָבן 10 לינגקט רשימות, אָדער 1,000 לינגקט רשימות, איצט עס ס אָ פון N צעטיילט דורך 10, אָדער אָ פון N צעטיילט דורך 1,000. און בשעת מיר האבן גערעדט טיערעטיקאַלי וועגן קאַמפּלעקסיטי מיר דיסריגאַרד קאַנסטאַנץ, אין דער עמעס וועלט דאס טאקע ענין, רעכט? מיר אַקשלי וועט באַמערקן אַז דעם כאַפּאַנז צו לויפן 10 מאל Faster, אָדער 1,000 מאל Faster, ווייַל מיר ניטאָ דיסטריביוטינג איין לאַנג קייט אַריבער 1,000 קלענערער קייטן. און אַזוי יעדער צייַט מיר האָבן צו זוכן דורך איינער פון די קייטן מיר קענען איגנאָרירן די 999 קייטן מיר טאָן ניט זאָרגן וועגן, און נאָר זוכן אַז איינער. וואָס איז אויף דורכשניטלעך צו זייַן 1,000 מאל קירצער. און אַזוי מיר נאָך זענען סאָרט פון טענדינג צו דעם דורכשניטלעך פאַל פון ווייל קעסיידערדיק צייַט, אָבער נאָר ווייַל מיר זענען לעוורידזשינג דיוויידינג דורך עטלעכע ריזיק קעסיידערדיק פאַקטאָר. זאל ס זען ווי דעם זאל אַקטשאַוואַלי קוקן כאָטש. אַזוי דאָס איז געווען די האַש טיש מיר האבן איידער מיר דערקלערט אַ האַש טיש אַז איז טויגעוודיק פון סטאָרינג 10 סטרינגס. מיר ניטאָ ניט געגאנגען צו טאָן אַז ענימאָר. מיר שוין וויסן די לימיטיישאַנז פון וואָס אופֿן. איצט אונדזער האַש טיש ס געגאנגען צו זיין אַ מענגע פון ​​10 נאָודז, פּוינטערז צו קאָפּ פון לינגקט רשימות. און רעכט איצט עס ס נאַל. יעדער איינער פון די 10 פּוינטערז איז נאַל. עס ס גאָרנישט אין אונדזער האַש טיש רעכט איצט. איצט לאָזן ס אָנהייבן צו שטעלן עטלעכע זאכן אין דעם האַש טיש. און לאָזן ס זען ווי דעם אופֿן איז געגאנגען צו נוץ אונדז אַ קליין ביסל. זאל ס איצט האַש דזשאָוי. מיר וועט וועלן לויפן די שטריקל דזשאָוי דורך אַ האַש פונקציאָנירן און מיר צוריקקומען 6. נו וואָס טוט מיר טאָן איצט? נו איצט ארבעטן מיט לינגקט רשימות, מיר ניטאָ ניט ארבעטן מיט ערייז. און ווען מיר ניטאָ ארבעטן מיט לינגקט רשימות מיר וויסן מיר דאַרפֿן צו אָנהייבן דינאַמיקאַללי אַלאַקייטינג פּלאַץ און בנין קייטן. אַז ס סאָרט פון האָוו-- יענע זענען די האַרץ עלעמענטן פון בנין אַ לינגקט רשימה. אַזוי לאָזן ס דינאַמיקאַללי אַלאַקייט פּלאַץ פֿאַר דזשאָוי, און דעריבער לאָזן ס לייגן אים צו די קייט. אַזוי איצט קוקן וואָס מיר ווע געטאן. ווען מיר האַש דזשאָוי מיר גאַט דער האַשקאָדע 6. איצט די טייַטל ביי מענגע אָרט 6 ווייזט צו די קאָפּ פון אַ לינגקט רשימה, און רעכט איצט עס ס די בלויז עלעמענט פון אַ לינגקט רשימה. און די נאָדע אין אַז לינגקט רשימה איז דזשאָוי. אַזוי אויב מיר דאַרפֿן צו קוקן אַרויף דזשאָוי שפּעטער, מיר נאָר האַש דזשאָוי ווידער, מיר באַקומען 6 ווידער ווייַל אונדזער האַש פֿונקציע איז דעטערמיניסטיק. און דעמאָלט מיר אָנהייבן בייַ די קאָפּ פון די לינגקט רשימה שפּיציק צו דורך מענגע אָרט 6, און מיר קענען יטעראַטע אַריבער אַז טריינג צו געפֿינען דזשאָוי. און אויב מיר בויען אונדזער האַש טיש Effectively, און אונדזער האַש פונקציאָנירן Effectively צו פאַרשפּרייטן דאַטע געזונט, אויף דורכשניטלעך יעדער פון די לינגקט רשימות אין יעדער מענגע אָרט וועט זיין 1/10 די גרייס פון אויב מיר נאָר האט עס ווי אַ איין ריזיק לינגקט רשימה מיט אַלץ אין עס. אויב מיר פאַרשפּרייטן אַז ריזיק לינגקט רשימה אַריבער 10 לינגקט רשימות יעדער רשימה וועט זיין 1/10 די גרייס. און אַזוי 10 מאל קוויקער צו זוכן דורך. אַזוי לאָזן ס טאָן דעם ווידער. זאל ס איצט האַש ראַס. און לאָזן ס זאָגן ראַס, ווען מיר טאָן אַז די האַש קאָד מיר באַקומען צוריק איז 2. נו איצט מיר דינאַמיקאַללי אַלאַקייט אַ נייַ נאָדע, מיר שטעלן ראָסס אין אַז נאָדע, און מיר זאָגן איצט מענגע אָרט 2, אַנשטאָט פון פּוינטינג צו נאַל, ווייזט צו די קאָפּ פון אַ לינגקט רשימה וועמענס בלויז נאָדע איז ראַס. און מיר קענען טאָן דעם איינער מער צייַט, מיר קענען האַש רחל און באַקומען האַשקאָדע 4. מאַללאָק אַ נייַ נאָדע, שטעלן רחל אין די נאָדע, און זאָגן אַ מענגע אָרט 4 איצט ווייזט צו די קאָפּ פון אַ לינגקט רשימה וועמענס בלויז עלעמענט כאַפּאַנז צו זיין רחל. גוט אָבער וואָס כאַפּאַנז אויב מיר האָבן אַ צונויפשטויס? זאל ס זען ווי מיר שעפּן קאַליזשאַנז ניצן די באַזונדער טשאַינינג אופֿן. זאל ס האַש פאָעבע. מיר באַקומען די האַשקאָדע 6. אין אונדזער פֿריִערדיקע בייַשפּיל מיר האבן נאָר סטאָרינג די סטרינגס אין די מענגע. דעם איז אַ פּראָבלעם. מיר טאָן ניט ווילן צו קלאָבבער דזשאָוי, און מיר ווע שוין געזען אַז מיר קענען באַקומען עטלעכע קלוסטערינג פּראָבלעמס אויב מיר פּרובירן און שריט דורך און זאָנד. אבער וואָס אויב מיר נאָר מין פון מייַכל דעם דער זעלביקער וועג, רעכט? עס ס פּונקט ווי אַדינג אַן עלעמענט צו די קאָפּ פון אַ לינגקט רשימה. זאל ס נאָר מאַללאָק פּלאַץ פֿאַר פאָעבע. מיר וועט זאָגן פאָעבע ס ווייַטער טייַטל פּוינץ צו דער אַלט קאָפּ פון די לינגקט רשימה, און דעמאָלט 6 נאָר ווייזט צו די נייַ קאָפּ פון די לינגקט רשימה. און איצט קוק, מיר ווע געביטן פאָעבע אין. מיר קענען איצט קראָם צוויי יסודות מיט האַשקאָדע 6, און מיר טאָן ניט האָבן קיין פּראָבלעמס. אַז ס שיין פיל אַלע עס איז צו טשאַינינג. און טשאַינינג איז באשטימט דעם אופֿן אַז ס געגאנגען צו זיין רובֿ עפעקטיוו פֿאַר איר אויב איר זענט סטאָרינג דאַטע אין אַ האַש טיש. אבער דעם קאָמבינאַציע פון ערייז און לינגקט רשימות צוזאַמען צו פֿאָרמירן אַ האַש טיש טאַקע דראַמאַטיקלי ימפּרוווז אייער פיייקייַט צו קראָם גרויס אַמאַונץ פון דאַטן, און זייער געשווינד און עפפיסיענטלי זוכן דורך אַז דאַטע. עס ס נאָך איינער מער דאַטע ביניען אויס דאָרט וואָס זאל אַפֿילו זייַן אַ ביסל בעסער אין טערמינען פון געראַנטיינג אַז אונדזער ינסערשאַן, דילישאַן, און קוק אַרויף די צייטן זענען אַפֿילו שנעלער. און מיר וועט זען אַז אין אַ ווידעא אויף טרייז. איך בין דאַג לויד, דאָס איז קס50.