Konuşma notu: Geçen hafta bir soruyu yanıtlamak için tüm bir grafı dolaştık. Bu hafta bu fikri tersine çeviriyoruz: hiçbir şeyi dolaşmadan, tam olarak nereye bakılacağını hesaplayabilir miyiz?
Konuşma notu: Yirmi bir kısa animasyon tüm dersi taşır; her fikir, tanıtıldığı yerde bir normal ve bir uç/zor çalıştırma alır.
Konuşma notu: Her terim ilk geçtiği yerde tam olarak tanımlanır; bu tablo yalnız onu tekrar nerede bulacağınızı söyler.
Konuşma notu: Canlı çalıştırmak isterseniz şimdi bir terminal açın; bugünün her kod parçası tam gösterildiği gibi derlenir ve çalışır.
Konuşma notu: Bugünkü her şey ya ikili aramayı özel bir durumda geçer, ya da "karşılaştırmayı" tamamen bırakıp "hesaplamaya" geçer.
Konuşma notu: Burada hiçbir şey yepyeni bir makine değil — Hafta 2'nin iki temel yapısı bugün boyunca yapı taşı olarak yeniden karşımıza çıkıyor.
Konuşma notu: Bu haritadaki her kutu aşağıda kendi slaytlarını alıyor, çoğu kısa bir animasyon ve eksiksiz bir C/Java programıyla.
Konuşma notu: Bölüm 1, bugünkü her algoritmanın farklı yanıtladığı tek soruyu kurar: bir anahtarı bulmadan — ya da yok olduğunu söylemeden — önce kaç karşılaştırma?
Konuşma notu: İkisine de evet — özel veri için daha hızlı karşılaştırmalı arama var, hash'leme ise karşılaştırmaları neredeyse tamamen kaldırıyor.
Konuşma notu: "Önce doğruluk, sonra hız" — bugünkü her algoritma her girdide yine de doğru yanıtı vermek zorunda.
Konuşma notu: Bölüm 2–6 birinci soruyu yanıtlıyor; Bölüm 7'den itibaren ikinci soruyu, hash'leme ile.
Konuşma notu: Bölüm 2–5'teki her algoritma, sıradan ikili aramanın göz ardı ettiği veriye dair bir ekstra gerçeği kullanıyor.
Konuşma notu: Haftanın en büyük fikri olan hash'leme, Bölüm 7 başlamadan hemen önce kendi araç kutusu slaytını alıyor.
Konuşma notu: Dizinin gerçek değerlerinin, sıralı olmanın ötesinde taşıyabileceği ekstra bilgiyi düşünün.
Konuşma notu: Bu tam olarak Bölüm 3'ün enterpolasyon aramasının tam bir algoritmaya dönüştürdüğü fikir.
Konuşma notu: Bölüm 2, "ikili aramadan hızlı" ailesini açar: ikiye bölmek yerine, sabit bloklarla ileri sıçra, sonra bir bloğu doğrusal tara.
Konuşma notu: Sıçramalı arama, ikili aramanın özyinelemesini bir dizi blok sıçraması ve ardından kısa bir doğrusal taramayla değiştiriyor.
Konuşma notu: Bu, derste kalkülüsün (bir toplamı minimize etmenin) bir algoritma tasarımını yönlendirdiği en temiz örneklerden biri.
Konuşma notu: Bir blok bir bölüm gibidir — son sayfasına bak, ve kelimenin içeride olduğunu anladığında ancak tam açarsın.
Konuşma notu: İki aşama, her biri kendi başına basit: doğru bloğu bulmak için kaba sıçramalar, sonra içinde kısa bir doğrusal tarama.
Konuşma notu: "Az sayıda büyük sıçrama" ile "kısa son tarama"yı dengelemek, tam olarak bir toplamı minimize eden kalkülüs problemi — her n için bir kez çözülmüş.
Konuşma notu: Normal örnek: 16 sıralı değer, hedef ikinci blokta bulundu — blok sınırı kontrollerini, sonra kısa doğrusal taramayı izleyin.
Konuşma notu: Hedef iki gerçek değerin arasına düşüyor — doğru bloktaki doğrusal tarama, hedefi geçtiği anda erken durur.
Konuşma notu: `block` yalnız `n`'den, bir kez hesaplanır — asla `target`'a bağlı değildir, yalnız dizinin boyutuna bağlıdır.
Konuşma notu: İkili aramanın erken durmasını sağlayan aynı "sıralı dizi" gerçeği, bu son taramanın da `arr[i] > target`'ta erken durmasını sağlar.
Konuşma notu: Sıçramalı arama gerçek bir orta yol: doğrusal aramadan hızlı, ikili aramadan (özyineleme yok) daha basit.
Konuşma notu: Yanlış bir blok boyutu yine de doğru yanıtı bulur — yalnız O(sqrt(n)) garantisini kaybeder.
Konuşma notu: Birkaç slayt önceki formülü hatırlayın, sonra O(sqrt(n)) sınırını uygulayın.
Konuşma notu: Bu O(sqrt(n)) sınırının somut hali: 20, teorik en kötü durum olan 2*sqrt(100)'e yakın.
Konuşma notu: Bölüm 3, "her zaman ortayı kontrol et" fikrini "hedefin nerede olması gerektiğini hesapla" ile değiştirir — sabit bir bölme noktası yerine bir formül.
Konuşma notu: Kimse böyle yapmaz — doğrudan arkaya doğru açarsınız, çünkü "S"nin kabaca nerede olması gerektiğini zaten bilirsiniz.
Konuşma notu: O(log log n) gerçekten küçük bir sayı — bir milyar eleman için bile yalnız yaklaşık 5.
Konuşma notu: Değeri yok saymak yerine kullanmak — bu tek fark, enterpolasyon aramasının tüm fikridir.
Konuşma notu: Formülden sonraki her şey ikili aramayla aynı — yalnız bölme noktasının nasıl seçildiği değişti.
Konuşma notu: Normal örnek: 16 düzgün dağılmış değer — formülün tahmininin tek bir yoklamada hedefe çok yaklaştığını izleyin.
Konuşma notu: Bu aralıktaki her değer aynı — arr[hi] arr[lo]'ya eşit, açık bir koruma olmadan formülün paydası sıfır olurdu.
Konuşma notu: Koruma isteğe bağlı değil — o olmadan, tümü eşit bir aralık programı sıfıra bölme hatasıyla çökertir.
Konuşma notu: İkili aramanın daraltma adımıyla şekilce aynı — yalnız `pos` `(lo + hi) / 2` yerine bir formülden geldi.
Konuşma notu: Enterpolasyon araması gerçek bir takas: doğru veride mükemmel, yanlış veride doğrusal aramadan iyi değil.
Konuşma notu: Çarpık bir dizi, enterpolasyon aramasının yoklama sayısını O(n)'e doğru çıkarabilir — tam olarak ikinci hatayı gösterir.
Konuşma notu: Birkaç slayt önceki karmaşıklık slaytının ikinci maddesini hatırlayın.
Konuşma notu: "Kabaca düzgün" enterpolasyon aramasının tanımında küçük bir ayrıntı değil — tüm hızlanmanın bağlı olduğu koşul.
Konuşma notu: Bölüm 4, Bölüm 2–3'ten çok farklı bir soruyu yanıtlıyor: dizinin boyutunu bile bilmiyorsanız ne olur?
Konuşma notu: İkili aramanın ilk adımı `hi = n - 1` ister — `n` bilinmiyorsa, bu adım hiç atılamaz.
Konuşma notu: "Galloping" (dörtnala), ikiye katlama aşaması için canlı bir isim — hız kazanan bir at gibi büyüyen küçük adımlar.
Konuşma notu: İkiye katlama aşamasının tek işi, ikili aramanın kullanacağı geçerli bir `hi` üretmek — başka bir şey değil.
Konuşma notu: Dizinin pratikte bilinen bir üst sınırı olmalı — buradaki "sınırsız", "sonsuz" değil, "n'i önceden bilmemize gerek yok" anlamına gelir.
Konuşma notu: Normal örnek: 16 sıralı değer, hedef ortalarda bulundu — sınırın ikiye katlanmasını, sonra ikili aramanın devralmasını izleyin.
Konuşma notu: Sınır dizinin gerçek sonunu aşacak şekilde ikiye katlanır, n-1'e sabitlenir, sonra ikili arama bulunamadı der.
Konuşma notu: Bu blok yalnız ikili aramanın nereden başlayacağına karar verir — indeks 0'daki bir şans dışında hedefi kendisi hiç bulmaz.
Konuşma notu: Hafta 1'in ikili aramasıyla tıpatıp aynı — yalnız başlangıç `lo` ve `hi` değerleri yukarıdaki ikiye katlama aşamasından geliyor.
Konuşma notu: Kazanç tam olarak bu: üstel arama dizinin boyutuna değil, yanıtın NEREDE olduğuna uyum sağlar.
Konuşma notu: Sabitleme önemli çünkü aksi halde `arr[bound]`, dizinin gerçek sonunun ötesini okurdu.
Konuşma notu: Karmaşıklık slaytını hatırlayın: maliyet dizinin boyutuna değil, hedefin İNDEKSİNE bağlı.
Konuşma notu: Yalnız ikili arama burada hâlâ yaklaşık 20 karşılaştırma gerektirirdi — üstel aramanın avantajı hedef başa yakınken en büyük.
Konuşma notu: Bölüm 5, "sıralı veride daha hızlı arama" ailesini, hiç bölme ya da çarpma yapmayan bir stratejiyle kapatıyor.
Konuşma notu: Bu, erken bilgisayarlar için gerçek, pratik bir kısıtlamaydı — bazılarında donanım bölme komutu hiç yoktu.
Konuşma notu: Kiefer'ın asıl problemi, mümkün olduğunca az ölçümle bir fonksiyonun tepesini bulmaktı — aynı matematik burada yeniden kullanılıyor.
Konuşma notu: Cetvel her seferinde tam olarak bir Fibonacci adımı kadar küçülür — bu, ikili aramadaki ikiye bölmenin yerini alan şey.
Konuşma notu: Bir aşımda "iki adım küçültmek", tüm algoritmayı çarpma ya da bölmeden tamamen uzak tutan şey.
Konuşma notu: Normal örnek: 16 sıralı değer, hedef ortalarda bulundu — her yoklamadan sonra (fib, fib1, fib2) üçlüsünün küçülmesini izleyin.
Konuşma notu: Ana döngü fib1 == 1 ile biter — tek bir eleman kalır, ayrıca kontrol edilir, sonra bulunamadı bildirilir.
Konuşma notu: Yukarıdaki while döngüsü, hiçbir karşılaştırmadan önce yalnız bir kez çalışır — sadece `n` için başlangıç Fibonacci üçlüsünü bulur.
Konuşma notu: Buradaki her satır yalnız `+` ya da `-` — bölme ya da çarpmaya hiç gerek olmadığının somut kanıtı bu.
Konuşma notu: Modern donanımda bölme ucuz olduğu için, Fibonacci araması artık çoğunlukla tarihsel ve eğitimsel bir ilgi konusu.
Konuşma notu: "Tek eleman kaldı" durumu, tam olarak bu bölümün bulunamadı uç durumunun göstermek için kurulduğu şey.
Konuşma notu: Birkaç slayt önceki "kısa tarihçe" slaytının gerekçesini hatırlayın.
Konuşma notu: Modern CPU'larda hızlı donanım bölmesi var, o yüzden bu belirli avantaj çoğunlukla kayboldu — algoritma zarif bir fikir olarak yaşıyor.
Konuşma notu: Bölüm 6, hash'lemeden önce kısa bir mola — Bölüm 2–5'in az önce inşa ettiği her şeyi karşılaştıran tek bir tablo.
Konuşma notu: Buradaki "ister", her stratejinin sade ikili aramayı geçmek için "sıralı" olmanın ötesinde dayandığı ekstra varsayım.
Konuşma notu: Her iki tablodaki her satır tek bir gereksinimi paylaşır: veri önce sıralı olmalı — şimdi başlayacak hash'leme bu gereksinimi tamamen kaldırıyor.
Konuşma notu: Bu stratejilerin hiçbiri asla "yanlış" seçim değil — her biri yalnız kendi varsayımı altında kazanan bir uzman.
Konuşma notu: `n`'i önceden bilmeyi özellikle gerektirmeyen stratejiyi hatırlayın.
Konuşma notu: Bu tam olarak Bentley ve Yao'nun 1976 tarihli özgün makalesindeki "sınırsız arama" çerçevesi.
Konuşma notu: Bölüm 7, haftanın ikinci yarısını açıyor: değerleri karşılaştırmak yerine, bir anahtarın nereye ait olduğunu doğrudan hesapla.
Konuşma notu: Evet — bu tek fikir, "karşılaştırma değil, hesapla", hash'lemenin tüm temeli.
Konuşma notu: Luhn ayrıca adını taşıyan, hash'lemeyle ilgisiz kredi kartı sağlama toplamı algoritmasını da icat etti — aynı kişinin farklı, daha ünlü bir buluşu.
Konuşma notu: Doğrudan adresleme, anahtar uzayı tablodan çok daha büyük olduğunda hash'lemenin yaklaşmaya çalıştığı ideal durum.
Konuşma notu: Sıfır çakışmalı mükemmel bir hash fonksiyonu kuramda var, ama pratikte çakışmalar beklenir ve ele alınmalıdır.
Konuşma notu: "mod" fonksiyonun tamamı — basitliği tam olarak öğretilecek ilk doğal hash fonksiyonu olmasının nedeni.
Konuşma notu: Normal örnek: m = 11 (asal), 12 rastgele anahtar — çoğu anahtarın, yalnız ara sıra bir çakışmayla, dağıldığını izleyin.
Konuşma notu: m = 10, ve her anahtar 10'un katı — k mod 10 her tek anahtar için 0: tam çakışma, olabilecek en kötü dağılım.
Konuşma notu: Bu bir batıl inanç değil — doğrudan mod işleminin bir anahtarın kendi çarpanlarıyla nasıl etkileştiğinden geliyor.
Konuşma notu: C'de, `key` negatifken `key % m` negatif olabilir — ekstra `+ m`, son `% m`'den önce bunu düzeltir.
Konuşma notu: Bir hash fonksiyonunun kendi maliyeti neredeyse bedava; bugün kalan her slayt iki anahtar çakıştıktan sonra ne olduğuyla ilgili.
Konuşma notu: Negatif-anahtar koruma slaytındaki `+ m` numarası, şaşırtıcı sayıda gerçek hatanın kaynağı olan küçük bir ayrıntı.
Konuşma notu: `key` her zaman çiftken `key mod 8`'in hangi kalanları üretebileceğini düşünün.
Konuşma notu: Bu, 10'un kuvveti uç durumuyla aynı "ortak çarpan" problemi, yalnız 10 yerine çarpan 2.
Konuşma notu: Bölüm 8, çakışmaların normal olduğunu kabul eder, sonra onları atlatmanın iki standart yolundan ilkini kurar.
Konuşma notu: Tek bir doğru yanıt yok — bugünün geri kalanı, tam olarak bu soruya iki farklı, eşit derecede geçerli yanıt.
Konuşma notu: Burada çakışmalar hiçbir şeyin üzerine yazmaz — sadece bir listeyi büyütür, ki bu tam olarak Hafta 2'nin bağlı listesinin yeniden kullanımı.
Konuşma notu: Ekleme önce zinciri aramak zorunda değil — yeni düğüm her zaman doğrudan başa gider.
Konuşma notu: Normal örnek: m = 7, 10 ekleme, 4 arama — bir kovanın zincirinin büyümesini, sonra bir arama sırasında dolaşılmasını izleyin.
Konuşma notu: m = 3, 12 anahtar: yük faktörü α = 4 — zincirler uzuyor, artık arama ortalamada birkaç yoklama tutuyor, O(1) değil.
Konuşma notu: Bu, Hafta 2'nin "başa ekleme" bağlı liste işlemi, tamamen değişmeden — yalnız kova bir hash'ten geliyor.
Konuşma notu: Bir `NULL` zincir burada bedavaya ele alınır — for döngüsü hiç çalışmaz, fonksiyon hemen false döner.
Konuşma notu: Yük faktörü, bir aramanın ortalamada kaç düğümü geçmesi gerektiğini önceden söyleyen tek sayı.
Konuşma notu: En kötü durum bilerek alarm verici — Bölüm 10'un yeniden hash'lemesi, α'nın hiç bu kadar büyümesini önlemek için var.
Konuşma notu: Hiç çakışması olmayan bir hash tablosu gerçekçi bir tasarım hedefi değil — asıl hedef onları iyi yönetmek.
Konuşma notu: Birkaç slayt önceki yük faktörü formülünü doğrudan uygulayın.
Konuşma notu: Bu tam senaryoyu, Bölüm 10'un yeniden hash'lemesi, α bu kadar büyümeden tabloyu büyüterek sonradan düzeltiyor.
Konuşma notu: Bölüm 9, çakışma sorusunu ikinci bir yolla yanıtlıyor: tablonun dışında bir liste yerine, her anahtarı tablonun içinde tut.
Konuşma notu: Evet — bu bölümün tamamı, bir anahtarın ev hücresi doluyken "sırada nereye bakayım?" sorusuna üç farklı yanıt.
Konuşma notu: Üç kural da tam olarak tek bir soruyu farklı yanıtlıyor: "ev hücresi dolu — sırada nereye bakayım?" Mezar taşı ayrıntısı 9a'da tam olarak açıklanıyor.
Konuşma notu: En basit yoklama kuralı: bir hücre doluysa, sadece bir sonrakini dene, sonda başa sar.
Konuşma notu: Bu büyüyen öbekler, tam olarak bir sonraki slaytın "birincil kümelenme" dediği şey.
Konuşma notu: Normal örnek: m = 11, 10 ekleme, bir arama ve bir silme — bir yoklama dizisinin oluşmasını, sonra arama sırasında yeniden dolaşılmasını izleyin.
Konuşma notu: Mezar taşı olmadan, bu arama boşaltılmış hücrede yanlışlıkla durup "bulunamadı" derdi — anahtar hâlâ yoklama zincirinde daha ilerideyken.
Konuşma notu: m = 8, 8 anahtar sırayla aynı hücrede çakışıyor — tablo tam olarak doluyor, sonraki ekleme doğru şekilde reddediliyor.
Konuşma notu: `state[idx] != OCCUPIED`, hem EMPTY hem DELETED'i kabul eder — bir mezar taşının hücresini yeni bir anahtar için yeniden kullanarak.
Konuşma notu: EMPTY değil, DELETED — bu tek kelimelik fark, sonraki her aramanın yoklama zincirini bozulmadan tutan şey.
Konuşma notu: Asıl sorun "öngörülebilirlik" — bir öbeğin başında çakışan her anahtar, ondan kaçmak için tam olarak aynı büyüyen öbeği yürür.
Konuşma notu: Açık adreslemede geri dönülecek "ekstra" bellek yok — tablo dolduğunda, zincirlemenin aksine, hiçbir anahtar sığmaz.
Konuşma notu: Bu hataların her biri yine de derlenir ve küçük test durumlarında genelde "doğru görünür" — tam olarak bu onları tehlikeli kılan şey.
Konuşma notu: Birkaç slayt önceki mezar taşı uç durumu animasyonunun konuşma notunu hatırlayın.
Konuşma notu: Bir mezar taşı "burada bir şey vardı, aramaya devam et" demek — yalnız gerçek bir EMPTY hücre "bu noktanın ötesinde hiçbir şey yerleştirilmedi" demek.
Konuşma notu: Karesel yoklama da her anahtarı tablonun içinde tutar, ama doğrusal yoklamanın sabit adımını hızla büyüyen bir adımla değiştirir.
Konuşma notu: Büyüyen adım kümelenme için tam çözüm — ama tam olarak bu büyüme, yeni döngü probleminin nedeni.
Konuşma notu: Normal örnek: m = 13 (asal), 10 anahtar — i² sıçramalarının tek bir büyüyen öbek yerine dağınık hücrelere düştüğünü izleyin.
Konuşma notu: m = 8, asal değil — i² dizisi, tabloda başka yerde boş hücreler olsa bile, sonsuza dek aynı birkaç hücreyi ziyaret ediyor.
Konuşma notu: `i*i`, doğrusal yoklamanın kodundan tek gerçek değişiklik — adım artık sabit +1 yerine `i`'ye bağlı.
Konuşma notu: Doğrusal yoklamadan farklı olarak, burada kötü bir m yalnız yavaşlatmakla kalmaz, doğrudan doğruluğu bozabilir — bu koşul gerçekten daha güçlü.
Konuşma notu: Animasyonun uç durumu bir döngüyü açıkça işaretliyor, tam olarak gerçekten dolu bir tabloyla karıştırılmasın diye.
Konuşma notu: "Karmaşıklık, ve m neden önemli" slaytının son maddesini hatırlayın.
Konuşma notu: Bu tam olarak birkaç slayt önceki karesel-döngü uç durumu animasyonunun gösterdiği senaryo.
Konuşma notu: Çift hash de aynı "tablonun içinde yokla" fikrini tutar, ama adımın kendisini anahtara bağlı yapar.
Konuşma notu: Bu doğrudan doğrusal yoklamanın sorununu çözer: aynı ev hücresini paylaşan iki anahtar artık oradan genelde tamamen farklı yollar izler.
Konuşma notu: Normal örnek: m = 13, R = 11, 10 anahtar — iki anahtarın bir ev hücresini paylaşmasını, sonra görünür şekilde farklı yoklama yollarını izlemesini izleyin.
Konuşma notu: m = 9, asal değil — bir anahtarın adımı m ile ortak bir çarpan paylaşıyor, o yüzden yoklama dizisi her hücreye ulaşmadan döngüye giriyor.
Konuşma notu: `h2`, sonucu her zaman `[1, r]` aralığında olacak şekilde kuruldu — hiçbir zaman 0 değil, çünkü 0 adım aynı hücreyi sonsuza dek yoklardı.
Konuşma notu: `step`, döngünün dışında, anahtar başına bir kez hesaplanır — bu anahtar için her çakışma sonra aynı kişisel adımı yeniden kullanır.
Konuşma notu: Bileşik bir m, tıpkı 9b'deki gibi, bazı anahtarların adımlarının döngüye girmesine izin verebilir — çift hash aynı temel soruna karşı bağışık değil.
Konuşma notu: Tam olarak 0'lık bir adım buradaki en tehlikeli hata — tam olarak aynı dolu hücreyi sonsuza dek yeniden yoklar.
Konuşma notu: Her alt bölümün "m neden önemli" maddelerini hatırlayın, koşulun ne kadar katı olduğunu karşılaştırın.
Konuşma notu: Karesel ve çift hash kötü bir m'de boş bir hücreyi hiç bulamayabilir; doğrusal yoklama bunun yerine zarifçe, yalnız daha yavaş, bozulur.
Konuşma notu: Bölüm 10, bu haftaki her çakışma-çözme tekniğinin şimdiye dek kaçındığı soruyu yanıtlıyor: tablo çok dolduğunda ne olur?
Konuşma notu: Tablo büyümeli — ama bir hash tablosunu büyütmek bir diziyi büyütmek kadar basit değil, çünkü her anahtarın indeksi m'ye bağlı.
Konuşma notu: Bir anahtarın indeksi mod işlemi yüzünden m'ye bağlı — m'yi değiştirin, neredeyse her anahtarın doğru indeksi de değişir.
Konuşma notu: Yeniden hash'leme hiç yeni ekleme mantığı gerektirmez — yalnız hayatta kalan her anahtar için sıradan insert()'ü bir kez çağırır.
Konuşma notu: Normal örnek: m0 = 6, 10 anahtar — α'nın eşiği aşmasını, asal boyutlu yeni bir tablonun belirmesini, her anahtarın indeksinin yeniden hesaplanmasını izleyin.
Konuşma notu: m0 = 2 çok küçük — eşik neredeyse hemen aşılıyor, ilkinden kısa süre sonra bir ikinci yeniden hash'leme geliyor.
Konuşma notu: Bu, Bölüm 7'nin bölme yöntemiyle tam olarak aynı akıl yürütme — yeni tablo boyutunun yine asal olması gerekiyor.
Konuşma notu: Döngü her ESKİ hücreyi bir kez dolaşır, o yüzden bu işlemin tamamı O(m)'ye mal olur — pahalı, ama nadiren gerçekleşir.
Konuşma notu: "Amortize", ara sıra olan pahalı işlemin, birçok ucuz işleme yayıldığında, yine de küçük bir sabite indirgendiği anlamına gelir.
Konuşma notu: Her eklemede yeniden hash'lemek, HER eklemeyi O(n)'e mal ederdi — bir eşiğin tüm amacı bunu nadir kılmak.
Konuşma notu: Eklemeden sonraki yeni α'yı hesaplayın, sonra eşikle karşılaştırın, sonra next_prime(2*m)'i uygulayın.
Konuşma notu: Bu tam olarak yukarıdaki normal-preset animasyonunun senaryosu, aynı m0 = 6 başlangıç boyutuyla.
Konuşma notu: Bölüm 11, haftanın tüm ikinci yarısının pratik karşılığı: gerçekte hangi tekniğe başvurmalısınız?
Konuşma notu: Her satır gerçek bir takas — hiçbir sütun her durumda basitçe "daha iyi" değil.
Konuşma notu: Bu sıralama, bu üç tekniğin geliştirildiği tarihsel sırayla da kabaca örtüşüyor, her biri öncekinin zayıf noktasını düzeltiyor.
Konuşma notu: Gerçek hash tablosu kütüphaneleri (örneğin Java'nın HashMap'i), tam olarak bu tür bir mühendislik takasını dokümantasyonlarında açıkça yapıyor.
Konuşma notu: Pratik kural slaytının ilk iki maddesini hatırlayın.
Konuşma notu: Silmeler sonradan yaygınlaşırsa, mezar taşları dikkatli ele alınmalı — zincirleme o zaman daha iyi bir takas olabilir.
Konuşma notu: Buradaki her satır hâlâ değerleri karşılaştırıyor — sırada özetlenecek hash'leme, bunu büyük ölçüde yapmayan tek fikir.
Konuşma notu: İki çakışma ailesi de hâlâ hızlarını önceden söyleyen bir sayıyı paylaşıyor: yük faktörü α = n/m.
Konuşma notu: Öğrenci bugünden yalnız bir cümle hatırlayacaksa, hatırlamaya değer olan bu.
Konuşma notu: Bunlar yazılı notların sonundaki öz değerlendirme sınavını yansıtıyor, slayt başına bir soru, burada daha kısa bir setle.
Konuşma notu: Sor, bekle, sonra ilerle.
Konuşma notu: Bu, Bölüm 2'nin O(sqrt(n)) sınırının, daha büyük bir n'ye uygulanmış tam hali.
Konuşma notu: Bölüm 3'ün sıfıra bölme uç durumunu hatırlayın.
Konuşma notu: Bu tam olarak Bölüm 3'teki tümü-eşit uç durumu animasyonunun göstermek için kurulduğu şey.
Konuşma notu: Bölüm 7'nin 10'un kuvveti örneğini hatırlayın.
Konuşma notu: Aynı gerçek, Bölüm 9'dan karesel ve çift hash için daha da güçlü şekilde önemli.
Konuşma notu: Bölüm 9a'nın mezar taşı uç durumunu hatırlayın.
Konuşma notu: Bu, açık adresleme uygulamalarındaki en yaygın gerçek dünya hatası, ve tam olarak mezar taşı animasyonunun gösterdiği şey.
Konuşma notu: Hafta 7–8, ara sınav haftası proje sunumu ve sınav bloğu; Hafta 9 sonra Hafta 5'in üzerine, ağırlıklı graf algoritmalarına geçiyor.
Konuşma notu: Bunlar, haftanın yazılı notlarının sonundaki aynı kaynaklar.
Konuşma notu: Tarihsel kaynaklar — Luhn, Kiefer, Bentley ve Yao — bugünün "kısa tarihçe" slaytlarının dayandığı kaynaklar.