Çakışma İşleme
Zincirleme ve yoklama
Çakışma İşleme, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, C Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. C Academy kursu toplamda 4 dersten oluşur.
Çakışma Sorunu
İki farklı anahtar aynı kovaya dönüştüğünde bir çakışma oluşur. Çakışmalar kaçınılmaz olduğundan her karma tablosu, tek bir yuvada birden fazla anahtarı saklamak için bir stratejiye ihtiyaç duyar.
İki temel yaklaşım ailesi ve açık adreslemedir.
Ayrı Zincirleme
ayrı zincirleme yönteminde her kova, girdilerden oluşan bağlı bir liste tutar. Çakışma olduğunda ilgili kovanın listesine basitçe sona (veya başa) ekleme yaparsınız.
- Kovalar liste başlarını tutar
- Aramalar kısa bir listeyi dolaşır
Zincirleme Düğüm Yapısı
Her düğüm bir anahtar, bir değer ve bir next işaretçisi tutar. Tablo, düğüm işaretçilerinden oluşan bir dizidir.
#include <stdio.h>
typedef struct Node {
char *key;
int value;
struct Node *next;
} Node;
int main(void) {
Node *buckets[8] = {0};
printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
return 0;
}Zincirleme ile Ekleme
Kova listesinin başına ekleme işlemi O(1)'dir. Burada elle küçük bir zincir oluşturup yazdırıyoruz.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int key; struct Node *next; } Node;
Node *prepend(Node *head, int key) {
Node *n = malloc(sizeof *n);
n->key = key; n->next = head;
return n;
}
int main(void) {
Node *bucket = NULL;
bucket = prepend(bucket, 10);
bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
for (Node *p = bucket; p; p = p->next)
printf("%d ", p->key);
printf("\n");
return 0;
}Açık Adresleme
açık adresleme yönteminde her girdi doğrudan kova dizisinde bulunur. Çakışma olduğunda sabit bir dizi kullanarak başka bir boş konum araştırırsınız.
Ek düğüm ayrılmadığından önbellek kullanımı verimlidir.
Doğrusal Araştırma
Doğrusal araştırma, sonraki konumu, ardından bir sonrakini denetler ve dizinin başına döner: (h + i) % capacity.
Basit ve önbellek dostudur; ancak kümelenme sorunundan etkilenir.
#include <stdio.h>
int main(void) {
int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
unsigned h = 2, cap = 8;
for (unsigned i = 0; i < cap; i++) {
unsigned idx = (h + i) % cap;
if (!slots[idx]) { printf("insert at %u\n", idx); break; }
}
return 0;
}Karesel Araştırma
Karesel araştırma, araştırma konumlarını dağıtmak ve birincil kümelenmeyi azaltmak için (h + i*i) % capacity ifadesini kullanır.
#include <stdio.h>
int main(void) {
unsigned h = 3, cap = 8;
for (unsigned i = 0; i < 4; i++)
printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
return 0;
}Çift Özetleme
Çift özetleme, adım boyutu için ikinci bir özet kullanır: (h1 + i*h2) % capacity. Böylece her anahtarın kendine ait bir araştırma dizisi olur ve üç yöntem arasında en iyi dağılım elde edilir.
#include <stdio.h>
int main(void) {
unsigned h1 = 3, h2 = 5, cap = 8;
for (unsigned i = 0; i < 4; i++)
printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
return 0;
}Açık Adreslemede Silme
Açık adreslemede bir konumu yalnızca temizleyemezsiniz; çünkü bu, diğer anahtarların araştırma zincirlerini bozabilir. Bunun yerine konumu bir silme işareti ile işaretleyin; böylece aramalar bu konumun ötesinde araştırmaya devam eder.
Zincirleme ve Açık Adresleme Karşılaştırması
Ödünleşimler:
- Zincirleme: yüksek doluluk oranlarını iyi yönetir ve silme işlemleri basittir; ancak işaretçiler ve bellek ayırmaları kullanır
- Açık adresleme: önbellek dostudur ve girdi başına bellek ayırmaz; ancak tablo dolmaya yaklaştığında performansı hızla düşer ve silme işaretleri gerektirir
Araştırma Sayısı Gösterimi
Konumlar kümelendiğinde doğrusal araştırma birkaç adım gerektirebilir. Burada boş bir konum bulmak için gereken araştırma sayısını hesaplıyoruz.
#include <stdio.h>
int main(void) {
int slots[8] = {1,1,1,0,0,0,0,0};
unsigned h = 0, cap = 8, probes = 0;
for (unsigned i = 0; i < cap; i++) {
probes++;
if (!slots[(h + i) % cap]) break;
}
printf("probes used = %u\n", probes);
return 0;
}Kısa Kontrol
Çakışma yönetimi bilginizi sınayın.
Özet
Özet tablolarının çakışmaları nasıl çözdüğünü incelediniz.
- Zincirleme, her kova için bağlı bir liste tutar
- Açık adresleme, boş bir konum arar
- Araştırma türleri: doğrusal, karesel ve çift özetleme
- Açık adresleme, silme işlemi için silme işaretleri gerektirir
Sıkça Sorulan Sorular
“Çakışma İşleme” dersi ücretsiz mi?
Evet — “Çakışma İşleme” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve C Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. C Academy kursu toplamda 4 dersten oluşur.
“Çakışma İşleme” dersinde ne öğreneceğim?
Zincirleme ve yoklama C Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
C Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te C Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Çakışma İşleme” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu C Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her C Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.