Ey Habr! Makalenin çevirisini dikkatinize sunuyorum.
"İlişkisel veritabanı nasıl çalışır?".

İlişkisel veritabanları söz konusu olduğunda bir şeylerin eksik olduğunu düşünmeden edemiyorum. Her yerde kullanılırlar. Küçük ve kullanışlı SQLite'tan güçlü Teradata'ya kadar birçok farklı veritabanı mevcuttur. Ancak veritabanının nasıl çalıştığını açıklayan yalnızca birkaç makale var. Ne kadar az sonuç olduğunu görmek için "howdoesarelationaldatabasework" komutunu kullanarak kendiniz arayabilirsiniz. Üstelik bu yazılar kısadır. En son popüler teknolojileri (BigData, NoSQL veya JavaScript) arıyorsanız, bunların nasıl çalıştığını açıklayan daha ayrıntılı makaleler bulacaksınız.

İlişkisel veritabanları üniversite dersleri, araştırma makaleleri ve kitaplar dışında açıklanamayacak kadar eski ve sıkıcı mı?

Bir geliştirici olarak anlamadığım bir şeyi kullanmaktan nefret ediyorum. Ve eğer veritabanları 40 yılı aşkın süredir kullanılıyorsa bunun bir nedeni olmalı. Yıllar boyunca, her gün kullandığım bu tuhaf kara kutuları gerçekten anlamak için yüzlerce saat harcadım. ilişkisel veritabanları çok ilginç çünkü onlar Yararlı ve yeniden kullanılabilir konseptlere dayalı. Bir veritabanını anlamakla ilgileniyorsanız, ancak bu geniş konuyu derinlemesine inceleyecek zamanınız veya eğiliminiz olmadıysa, bu makaleyi beğenmelisiniz.

Bu makalenin başlığı açık olmasına rağmen, Bu makalenin amacı veritabanının nasıl kullanılacağını anlamak değil. dolayısıyla, basit bir bağlantı isteğinin ve temel sorguların nasıl yazılacağını zaten bilmelisiniz REZİL; aksi takdirde bu makaleyi anlayamayabilirsiniz. Bilmeniz gereken tek şey bu, gerisini anlatacağım.

Algoritmaların zaman karmaşıklığı (BigO) gibi bazı bilgisayar bilimi temelleriyle başlayacağım. Bazılarınızın bu kavramdan nefret ettiğini biliyorum, ancak bu olmadan veritabanının içindeki karmaşıklıkları anlayamazsınız. Bu çok geniş bir konu olduğundan odaklanacağım önemli olduğunu düşündüğüm şey: veritabanının nasıl işlediği SQL soruşturma. Sadece tanıtacağım temel veritabanı kavramlarıböylece makalenin sonunda kaputun altında neler olup bittiğine dair bir fikriniz olur.

Bu, birçok algoritma ve veri yapısını içeren uzun ve teknik bir makale olduğundan, okumaya zaman ayırın. Bazı kavramları anlamak zor olabilir; bunları atlayıp yine de genel fikri edinebilirsiniz.

Aranızda daha bilgili olanlar için bu makale 3 bölüme ayrılmıştır:

• Düşük seviyeli ve yüksek seviyeli veritabanı bileşenlerine genel bakış
• Sorgu Optimizasyon Sürecine Genel Bakış
• İşlem ve Tampon Havuzu Yönetimine Genel Bakış

Temellere dönüş

Yıllar önce (çok çok uzak bir galakside...), geliştiricilerin kodladıkları operasyonların sayısını tam olarak bilmeleri gerekiyordu. Yavaş bilgisayarlarının CPU ve hafızasını boşa harcamayı göze alamadıkları için algoritmalarını ve veri yapılarını ezbere biliyorlardı.

Bu bölümde, veritabanını anlamak için gerekli olan bu kavramlardan bazılarını size hatırlatacağım. Ayrıca konsepti tanıtacağım veritabanı dizini.

O(1) ve O(n2)

Günümüzde pek çok geliştirici algoritmaların zaman karmaşıklığını umursamıyor... ve haklılar!

Ancak çok fazla veriyle uğraştığınızda (binlerden bahsetmiyorum) ya da milisaniyeler içinde uğraşırken bu kavramı anlamak kritik hale geliyor. Ve tahmin edebileceğiniz gibi veritabanlarının her iki durumla da başa çıkması gerekiyor! Konuyu anlatmak için gereğinden fazla zaman harcamana izin vermeyeceğim. Bu, daha sonra maliyete dayalı optimizasyon kavramını anlamamıza yardımcı olacaktır (maliyet merkezli optimizasyon).

Kavram

Algoritmanın zaman karmaşıklığı Belirli bir veri miktarı için bir algoritmanın tamamlanmasının ne kadar süreceğini görmek için kullanılır. Bu karmaşıklığı tanımlamak için büyük O matematiksel gösterimini kullanırız.Bu gösterim, bir algoritmanın belirli sayıda giriş için kaç işleme ihtiyaç duyduğunu açıklayan bir fonksiyonla birlikte kullanılır.

Örneğin, "bu algoritmanın karmaşıklığı O(some_function())" dediğimde, bu, algoritmanın belirli miktarda veriyi işlemek için some_function(a_certain_amount_of_data) işlemleri gerektirdiği anlamına gelir.

Bu durumda, Önemli olan veri miktarı değil**, aksi takdirde ** veri hacmi arttıkça işlem sayısı nasıl artıyor?. Zaman karmaşıklığı kesin bir işlem sayısı sağlamaz ancak yürütme süresini tahmin etmenin iyi bir yoludur.

Bu grafikte, farklı algoritma zaman karmaşıklığı türleri için işlem sayısını ve girdi verisi miktarını görebilirsiniz. Bunları görüntülemek için logaritmik bir ölçek kullandım. Yani veri miktarı hızla 1 milyardan 1 milyara çıkıyor.

• O(1) veya sabit karmaşıklık sabit kalır (aksi takdirde buna sabit karmaşıklık denmez).
• O(log(n)) Milyarlarca veriyle bile düşük kalıyor.
• En kötü zorluk - O(n2), operasyon sayısının hızla arttığı yer.
• Diğer iki komplikasyon da aynı hızla artıyor.

Örnekler

Az miktarda veriyle O(1) ve O(n2) arasındaki fark ihmal edilebilir düzeydedir. Örneğin 2000 öğeyi işlemesi gereken bir algoritmanız olduğunu varsayalım.

• O(1) algoritması size 1 operasyona mal olacak
• O(log(n)) algoritması size 7 işleme mal olacak
• O(n) algoritması size 2 işleme mal olacak
• O(n*log(n)) algoritması size 14 işleme mal olacak
• O(n2) algoritması size 4 işleme mal olacak

O(1) ve O(n2) arasındaki fark büyük gibi görünse de (4 milyon işlem) ancak gözlerinizi kırpmak için gereken süre kadar maksimum 2 ms kaybedersiniz. Gerçekten de modern işlemciler işleyebilir saniyede yüz milyonlarca işlem. Bu nedenle birçok BT projesinde performans ve optimizasyon bir sorun değildir.

Dediğim gibi devasa miktarda veriyle çalışırken bu kavramı bilmek yine de önemli. Bu sefer algoritmanın 1 öğeyi işlemesi gerekiyorsa (ki bu bir veritabanı için çok fazla değildir):

• O(1) algoritması size 1 operasyona mal olacak
• O(log(n)) algoritması size 14 işleme mal olacak
• O(n) algoritması size 1 işleme mal olacak
• O(n*log(n)) algoritması size 14 işleme mal olacak
• O(n2) algoritması size 1 işleme mal olacak

Matematiği yapmadım, ancak O(n2) algoritmasıyla bir kahve (hatta iki tane!) içmeye zamanınız olduğunu söyleyebilirim. Veri hacmine bir 0 daha eklerseniz kestirmek için zamanınız olur.

Daha derine inelim

Bilginiz için:

• İyi bir karma tablo araması O(1)'de bir öğe bulur.
• İyi dengelenmiş bir ağacın aranması O(log(n)) cinsinden sonuçlar üretir.
• Bir diziyi aramak O(n) cinsinden sonuçlar üretir.
• En iyi sıralama algoritmaları O(n*log(n)) karmaşıklığına sahiptir.
• Kötü bir sıralama algoritması O(n2) karmaşıklığına sahiptir.

Not: İlerleyen bölümlerde bu algoritmaları ve veri yapılarını göreceğiz.

Algoritma zaman karmaşıklığının birkaç türü vardır:

• ortalama durum senaryosu
• en iyi durum senaryosu
• ve en kötü senaryo

Zaman karmaşıklığı genellikle en kötü senaryodur.

Ben yalnızca algoritmanın zaman karmaşıklığından bahsediyordum ama karmaşıklık aşağıdakiler için de geçerlidir:

• algoritmanın bellek tüketimi
• disk G/Ç tüketim algoritması

Elbette n2'den daha kötü komplikasyonlar da var, örneğin:

• n4: bu korkunç! Bahsedilen algoritmaların bazıları bu karmaşıklığa sahiptir.
• 3n: bu daha da kötü! Bu makalenin ortasında göreceğimiz algoritmalardan biri bu karmaşıklığa sahiptir (ve aslında birçok veritabanında kullanılmaktadır).
• faktöriyel n: küçük miktarda veriyle bile sonuçlarınızı asla alamazsınız.
• nn: Eğer bu karmaşıklıkla karşılaşırsanız kendinize bunun gerçekten faaliyet alanınız olup olmadığını sormalısınız...

Not: Size büyük O harfinin gerçek tanımını vermedim, sadece bir fikir. Bu makaleyi şuradan okuyabilirsiniz: Vikipedi gerçek (asimptotik) tanım için.

BirleştirSıralama

Bir koleksiyonu sıralamanız gerektiğinde ne yaparsınız? Ne? sort() fonksiyonunu çağırırsınız... Tamam, iyi cevap... Ancak bir veritabanı için bu sort() fonksiyonunun nasıl çalıştığını anlamalısınız.

Birkaç iyi sıralama algoritması var, bu yüzden en önemlilerine odaklanacağım: birleştirme sıralaması. Şu anda verileri sıralamanın neden yararlı olduğunu anlamayabilirsiniz, ancak sorgu optimizasyonu kısmından sonra anlamalısınız. Üstelik birleştirme sıralamasını anlamak, daha sonra adı verilen ortak veritabanı birleştirme işlemini anlamamıza yardımcı olacaktır. birleştirme kaydol (birleşme birliği).

Birleştirmek

Pek çok yararlı algoritma gibi, birleştirme sıralaması da bir hileye dayanır: N/2 boyutunda 2 sıralı diziyi N öğeli sıralanmış bir dizide birleştirmek yalnızca N işlem gerektirir. Bu işleme birleştirme denir.

Basit bir örnekle bunun ne anlama geldiğini görelim:

Bu şekil, son sıralanmış 8 öğeli diziyi oluşturmak için, 2 4 öğeli dizi üzerinde yalnızca bir kez yineleme yapmanız gerektiğini gösterir. Her iki 4 öğeli dizi de zaten sıralanmış olduğundan:

• 1) her iki mevcut öğeyi iki dizide karşılaştırırsınız (başlangıçta mevcut = ilk)
• 2) daha sonra en küçüğünü alıp 8 elemanlı bir diziye yerleştirin
• 3) ve dizideki en küçük elemanı aldığınız bir sonraki elemana geçin
• ve dizilerden birinin son öğesine ulaşana kadar 1,2,3'ü tekrarlayın.
• Daha sonra diğer dizinin kalan elemanlarını alıp 8 elemanlı bir diziye yerleştirirsiniz.

Bu işe yarar çünkü her iki 4 öğeli dizi de sıralanmıştır ve dolayısıyla bu dizilere "geri dönmeniz" gerekmez.

Artık işin püf noktasını anladığımıza göre, birleştirme için sözde kodum şöyle:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Birleştirme sıralaması, bir problemi daha küçük problemlere böler ve daha sonra orijinal problemin sonucunu elde etmek için daha küçük problemlerin sonuçlarını bulur (not: bu tür algoritmaya böl ve yönet denir). Bu algoritmayı anlamıyorsanız endişelenmeyin; İlk gördüğümde anlamadım. Size yardımcı olabilirse bu algoritmayı iki aşamalı bir algoritma olarak görüyorum:

• Dizinin daha küçük dizilere bölündüğü bölme aşaması
• Sıralama aşaması, daha büyük bir dizi oluşturmak için küçük dizilerin birleştirildiği (birleşim kullanılarak) aşamadır.

Bölünme aşaması

Bölme aşamasında dizi 3 adımda üniter dizilere bölünür. Adımların resmi sayısı log(N)'dir (N=8 olduğundan log(N) = 3).

Bunu nasıl bilebilirim?

Ben dahiyim! Tek kelimeyle - matematik. Buradaki fikir, her adımın orijinal dizinin boyutunu 2'ye bölmesidir. Adım sayısı, orijinal diziyi kaç kez ikiye bölebileceğinizdir. Bu, logaritmanın (taban 2) tam tanımıdır.

Sıralama aşaması

Sıralama aşamasında üniter (tek elemanlı) dizilerle başlarsınız. Her adımda birden fazla birleştirme işlemi uygularsınız ve toplam maliyet N = 8 işlemdir:

• İlk aşamada, her biri 4 operasyona mal olan 2 birleştirmeniz var
• İkinci adımda, her biri 2 operasyona mal olan 4 birleştirmeniz var
• Üçüncü adımda 1 operasyona mal olan 8 birleştirmeniz var

Log(N) adımları olduğundan, toplam maliyet N * günlük(N) işlemleri.

Birleştirme sıralamasının avantajları

Bu algoritma neden bu kadar güçlü?

Çünkü:

• Yeni diziler oluşturmak yerine doğrudan giriş dizisini değiştirmek amacıyla bellek alanını azaltmak için bunu değiştirebilirsiniz.

Not: Bu tür algoritmaya denir in-yer (ek hafıza olmadan sıralama).

• Bunu, önemli miktarda disk G/Ç yüküne yol açmadan aynı anda disk alanı ve az miktarda bellek kullanacak şekilde değiştirebilirsiniz. Buradaki fikir, belleğe yalnızca şu anda işlenmekte olan parçaları yüklemektir. Çoklu gigabaytlık bir tabloyu yalnızca 100 megabaytlık bellek arabelleğiyle sıralamanız gerektiğinde bu önemlidir.

Not: Bu tür algoritmaya denir harici sıralama.

• Birden fazla işlem/iş parçacığı/sunucuda çalışacak şekilde değiştirebilirsiniz.

Örneğin, dağıtılmış birleştirme sıralaması temel bileşenlerden biridir Hadoop'un (ki bu büyük verideki bir yapıdır).

• Bu algoritma kurşunu altına dönüştürebilir (gerçekten!).

Bu sıralama algoritması çoğu (hepsi olmasa da) veritabanlarında kullanılır, ancak tek değildir. Daha fazlasını öğrenmek istiyorsanız bunu okuyabilirsiniz Araştırma çalışmasıYaygın veritabanı sıralama algoritmalarının artılarını ve eksilerini tartışan.

Dizi, Ağaç ve Hash Tablosu

Artık zaman karmaşıklığı ve sıralama fikrini anladığımıza göre size 3 veri yapısından bahsetmeliyim. Bu önemlidir çünkü onlar modern veritabanlarının temelidir. Ayrıca konsepti tanıtacağım veritabanı dizini.

sıra

İki boyutlu bir dizi en basit veri yapısıdır. Bir tablo bir dizi olarak düşünülebilir. Örneğin:

Bu 2 boyutlu dizi, satırları ve sütunları olan bir tablodur:

• Her satır bir varlığı temsil eder
• Sütunlar, varlığı tanımlayan özellikleri saklar.
• Her sütun belirli bir türdeki verileri (tamsayı, dize, tarih...) depolar.

Bu, verileri depolamak ve görselleştirmek için uygundur, ancak belirli bir değer bulmanız gerektiğinde bu uygun değildir.

Örneğin, Birleşik Krallık'ta çalışan tüm adamları bulmak istiyorsanız, her satırın Birleşik Krallık'a ait olup olmadığını belirlemek için her satıra bakmanız gerekir. Bu size N işleme mal olacakNerede N - satır sayısı fena değil ama daha hızlı bir yol olabilir mi? Artık ağaçlarla tanışmamızın zamanı geldi.

Not: Çoğu modern veri tabanı, tabloları verimli bir şekilde depolamak için genişletilmiş diziler sağlar: yığınla düzenlenmiş tablolar ve dizinle düzenlenmiş tablolar. Ancak bu, bir grup sütunda belirli bir koşulu hızlı bir şekilde bulma sorununu değiştirmez.

Veritabanı ağacı ve dizin

İkili arama ağacı, özel bir özelliğe sahip bir ikili ağaçtır; her düğümdeki anahtar şu şekilde olmalıdır:

• sol alt ağaçta saklanan tüm anahtarlardan daha büyük
• sağ alt ağaçta saklanan tüm anahtarlardan daha az

Bunun görsel olarak ne anlama geldiğini görelim

Fikir

Bu ağacın N = 15 elemanı var. Diyelim ki 208'i arıyorum:

• Anahtarı 136 olan kökten başlıyorum. 136<208 olduğundan 136. düğümün sağ alt ağacına bakıyorum.
• 398>208 dolayısıyla 398 numaralı düğümün sol alt ağacına bakıyorum
• 250>208 dolayısıyla 250 numaralı düğümün sol alt ağacına bakıyorum
• 200<208, dolayısıyla 200 düğümünün sağ alt ağacına bakıyorum. Ancak 200'ün sağ alt ağacı yok, değer mevcut değil (çünkü eğer varsa sağ alt ağaç 200'de olacaktır).

Şimdi diyelim ki 40'ı arıyorum

• Anahtarı 136 olan kökten başlıyorum. 136 > 40 olduğundan 136 numaralı düğümün sol alt ağacına bakıyorum.
• 80 > 40, dolayısıyla 80. düğümün sol alt ağacına bakıyorum
• 40= 40, düğüm mevcut. Düğümün içindeki satır kimliğini alıyorum (resimde gösterilmiyor) ve verilen satır kimliğini bulmak için tabloya bakıyorum.
• Satır kimliğini bilmek, verinin tabloda tam olarak nerede olduğunu bilmemi sağlıyor, böylece onu anında alabiliyorum.

Sonuçta her iki arama da bana ağacın içindeki seviye sayısına mal olacak. Birleştirme sıralaması ile ilgili kısmı dikkatli okursanız log(N) seviyelerinin olduğunu göreceksiniz. Görünüşe göre arama maliyeti günlüğü(N), Fena değil!

Sorunumuza dönelim

Ama bu çok soyut, o yüzden sorunumuza geri dönelim. Basit bir tamsayı yerine, önceki tabloda birinin ülkesini temsil eden bir dize düşünün. Diyelim ki tablonun "ülke" alanını (sütun 3) içeren bir ağacınız var:

• Birleşik Krallık'ta kimin çalıştığını bilmek istiyorsanız
• Büyük Britanya'yı temsil eden düğümü bulmak için ağaca bakıyorsunuz
• "UKnode"un içinde Birleşik Krallık işçi kayıtlarının yerini bulacaksınız.

Diziyi doğrudan kullanırsanız, bu arama N işlemi yerine log(N) işlemine mal olacaktır. Az önce sunduğunuz şey şuydu veritabanı dizini.

Anahtarları karşılaştıracak bir fonksiyonunuz (örn. alan grupları) olduğu sürece herhangi bir alan grubu (dize, sayı, 2 satır, sayı ve dize, tarih...) için bir dizin ağacı oluşturabilirsiniz; böylece anahtarlar arasında sıralama (veritabanındaki tüm temel türler için durum budur).

B+TreeIndex

Bu ağaç belirli bir değeri elde etmede iyi çalışsa da, ihtiyacınız olduğunda BÜYÜK bir sorunla karşılaşabilirsiniz. iki değer arasında birden fazla öğe alın. Bunun maliyeti O(N) olacaktır çünkü ağaçtaki her düğüme bakmanız ve bu iki değer arasında olup olmadığını kontrol etmeniz gerekecektir (örneğin, ağacın sıralı bir geçişiyle). Üstelik bu işlem, ağacın tamamını okumak zorunda olduğunuz için disk G/Ç dostu değildir. Verimli bir şekilde yürütmenin bir yolunu bulmalıyız aralık isteği. Bu sorunu çözmek için modern veritabanları önceki ağacın B+Tree adı verilen değiştirilmiş bir versiyonunu kullanır. B+Tree ağacında:

• yalnızca en düşük düğümler (yapraklar) bilgi depola (ilgili tablodaki satırların konumu)
• düğümlerin geri kalanı burada yönlendirme için doğru düğüme arama sırasında.

Gördüğünüz gibi burada daha fazla düğüm var (iki kez). Aslında, doğru düğümü bulmanıza yardımcı olacak (ilişkili tablodaki satırların konumunu saklayan) ek düğümleriniz, "karar düğümleri" vardır. Ancak arama karmaşıklığı hala O(log(N))'dir (yalnızca bir düzey daha vardır). En büyük fark şu ki alt seviyedeki düğümler ardıllarına bağlanır.

Bu B+Tree ile 40 ile 100 arasındaki değerleri arıyorsanız:

• Önceki ağaçta yaptığınız gibi sadece 40'ı (veya 40 yoksa 40'tan sonraki en yakın değeri) aramanız gerekir.
• Daha sonra 40'e ulaşana kadar doğrudan varis bağlantılarını kullanarak 100 varis toplayın.

Diyelim ki M ardıl buldunuz ve ağacın N düğümü var. Belirli bir düğümü bulmanın maliyeti, önceki ağaçta olduğu gibi log(N)'dur. Ancak bu düğümü aldığınızda, M operasyonlarında ardıllarına referanslarla M ardılları elde edeceksiniz. Bu aramanın maliyeti yalnızca M+log(N) önceki ağaçtaki N işlemle karşılaştırıldığında işlemler. Üstelik ağacın tamamını okumak zorunda değilsiniz (yalnızca M+log(N) düğümleri), bu da daha az disk kullanımı anlamına gelir. M küçükse (örneğin 200 satır) ve N büyükse (1 satır), BÜYÜK bir fark olacaktır.

Ancak burada (yine!) yeni sorunlar var. Veritabanına (ve dolayısıyla ilişkili B+Tree dizinine) bir satır ekler veya silerseniz:

• B+Ağacı içindeki düğümler arasındaki sırayı korumalısınız, aksi takdirde sıralanmamış bir ağaç içindeki düğümleri bulamazsınız.
• B+Tree'de mümkün olan minimum sayıda seviyeyi tutmalısınız, aksi takdirde O(log(N)) zaman karmaşıklığı O(N) olur.

Başka bir deyişle B+Tree'in kendi kendini düzenleyen ve dengeli olması gerekir. Neyse ki bu, akıllı silme ve ekleme işlemleriyle mümkündür. Ancak bunun bir bedeli vardır: B+ ağacındaki ekleme ve silme işlemlerinin maliyeti O(log(N))'dur. Bu yüzden bazılarınız bunu duydu çok fazla indeks kullanmak iyi bir fikir değil. Gerçekten mi, bir tablodaki satırın hızla eklenmesi/güncellenmesi/silinmesini yavaşlatıyorsunuzçünkü veritabanının, her dizin için pahalı bir O(log(N)) işlemi kullanarak tablonun dizinlerini güncellemesi gerekir. Ayrıca indeks eklemek daha fazla iş yükü anlamına gelir. işlem yöneticisi (makalenin sonunda açıklanacaktır).

Daha fazla ayrıntı için şu adresteki Wikipedia makalesine bakabilirsiniz: B+ağaç. B+Tree'in bir veritabanında uygulanmasına ilişkin bir örnek istiyorsanız, şuna göz atın Bu makalede и Bu makalede Önde gelen bir MySQL geliştiricisinden. Her ikisi de InnoDB'nin (MySQL motoru) dizinleri nasıl işlediğine odaklanıyor.

Not: Bir okuyucu bana düşük seviyeli optimizasyonlar nedeniyle B+ ağacının tamamen dengelenmesi gerektiğini söyledi.

Karma tablo

Son önemli veri yapımız hash tablosudur. Değerleri hızlı bir şekilde aramak istediğinizde bu çok kullanışlıdır. Dahası, bir karma tablosunu anlamak, daha sonra karma birleştirme adı verilen ortak bir veritabanı birleştirme işlemini anlamamıza yardımcı olacaktır ( karma birleştirme). Bu veri yapısı aynı zamanda veritabanı tarafından bazı dahili şeyleri depolamak için de kullanılır (örn. kilit masası veya tampon havuzu, bu kavramların her ikisini de daha sonra göreceğiz).

Hash tablosu, bir öğeyi anahtarıyla hızlı bir şekilde bulan bir veri yapısıdır. Bir karma tablosu oluşturmak için şunları tanımlamanız gerekir:

• ключ elemanlarınız için
• Özet fonksiyonu anahtarlar için. Hesaplanan anahtar karmaları, öğelerin (adı verilen) konumunu verir. segmentler ).
• tuşları karşılaştırma işlevi. Doğru segmenti bulduktan sonra bu karşılaştırmayı kullanarak segment içerisinde aradığınız öğeyi bulmalısınız.

Basit bir örnek

Açık bir örnek verelim:

Bu karma tablosunun 10 bölümü vardır. Tembel olduğum için sadece 5 parçayı hayal ettim ama senin akıllı olduğunu biliyorum, bu yüzden diğer 5 parçayı kendi başına hayal etmene izin vereceğim. Anahtarın karma işlevi modulo 10'u kullandım. Başka bir deyişle, segmentini bulmak için öğenin anahtarının yalnızca son rakamını saklıyorum:

• son rakam 0 ise eleman 0 segmentine düşer,
• son rakam 1 ise eleman 1 segmentine düşer,
• son rakam 2 ise eleman 2. alana düşer,
• ...

Kullandığım karşılaştırma fonksiyonu basitçe iki tam sayı arasındaki eşitliktir.

Diyelim ki 78. elementi almak istiyorsunuz:

• Karma tablosu, 78 olan 8'in karma kodunu hesaplar.
• Karma tablosu 8. bölüme bakar ve bulduğu ilk öğe 78'dir.
• 78. maddeyi sana geri veriyor
• Aramanın maliyeti yalnızca 2 işlemdir (biri hash değerini hesaplamak için, diğeri ise segment içindeki öğeyi aramak için).

Şimdi diyelim ki 59. elementi almak istiyorsunuz:

• Karma tablosu, 59 olan 9'in karma kodunu hesaplar.
• Hash tablosu segment 9'da arama yapar, bulunan ilk eleman 99'dur. 99!=59 olduğundan, eleman 99 geçerli bir eleman değildir.
• Aynı mantık kullanılarak ikinci eleman (9), üçüncü eleman (79), ..., sonuncu eleman (29) alınır.
• Öğe bulunamadı.
• Arama 7 operasyona mal oldu.

İyi karma işlevi

Gördüğünüz gibi aradığınız değere göre maliyet aynı olmuyor!

Şimdi anahtarın hash fonksiyonunu modulo 1 olarak değiştirirsem (yani son 000 rakamı alarak), 000 segmentinde hiçbir öğe olmadığından ikinci arama yalnızca 6 işlem maliyeti olur. Asıl zorluk, çok az sayıda öğe içeren paketler oluşturacak iyi bir karma işlevi bulmaktır..

Örneğimde iyi bir karma işlevi bulmak kolaydır. Ancak bu basit bir örnek; iyi bir karma işlevi bulmak, anahtar şu olduğunda daha zordur:

• dize (örneğin - soyadı)
• 2 satır (örneğin - soyadı ve adı)
• 2 satır ve tarih (örneğin - soyadı, adı ve doğum tarihi)
• ...

İyi bir karma işleviyle karma tablosu aramalarının maliyeti O(1).

Dizi ve karma tablo karşılaştırması

Neden bir dizi kullanmıyorsunuz?

Hımm, güzel soru.

• Hash tablosu olabilir kısmen belleğe yüklendive kalan bölümler diskte kalabilir.
• Bir diziyle bellekte bitişik alan kullanmanız gerekir. Büyük bir tablo yüklüyorsanız yeterli sürekli alan bulmak çok zordur.
• Karma tablo için istediğiniz anahtarı seçebilirsiniz (örneğin ülke ve kişinin soyadı).

Daha fazla bilgi için ilgili makaleyi okuyabilirsiniz. JavaHash Haritasıkarma tablosunun verimli bir uygulaması olan; Bu makalede ele alınan kavramları anlamak için Java'yı anlamanıza gerek yoktur.

Kaynak: habr.com