C Academy · Ders

Özetleme İşlevleri

Anahtarları kovalara eşleme

Özetleme İşlevleri, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 1. 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.

Karma İşlevi Nedir

Bir karma işlevi, bir anahtar alır ve bir dizi içindeki kovalara karşılık gelen bir tamsayı dizini üretir. Karma tablosunun temelini oluşturur ve dizeler gibi keyfî anahtarları hızlı dizi konumlarına dönüştürür.

Girdi: bir anahtar (dize, tamsayı vb.)
Çıktı: [0, capacity) aralığında bir kova dizini

İyi Bir Karma Değerinin Özellikleri

İyi bir karma işlevi belirlenebilir, hızlı olur ve anahtarları kovalar arasında eşit dağıtır.

Aynı anahtar her zaman aynı dizini verir
Anahtardaki küçük değişiklikler büyük dizin değişikliklerine yol açar (çığ etkisi)
Tipik verilerde az sayıda çakışma oluşur

Kovaya eşleme

Ham karma değerini hesapladıktan sonra modulo işleciyle tabloya eşleyin: index = hash % capacity.

Modulo işleminin negatif bir dizin üretmemesi için unsigned türünü kullanın.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16;
    unsigned index = (unsigned)(hash % capacity);
    printf("bucket = %u\n", index);
    return 0;
}

Basit Toplam Karma

En basit dize karma yöntemi, karakter değerlerini toplar. Uygulaması kolaydır ancak anagramlar çakıştığı için dağılımı kötüdür.

İki farklı dizenin birbirine yakın değerlere nasıl dönüştüğünü görmek için çalıştırın.

#include <stdio.h>

unsigned long sum_hash(const char *s) {
    unsigned long h = 0;
    while (*s) h += (unsigned char)*s++;
    return h;
}

int main(void) {
    printf("%lu\n", sum_hash("abc"));
    printf("%lu\n", sum_hash("cba"));
    return 0;
}

DJB2 Karması

DJB2, Daniel J. Bernstein tarafından geliştirilen klasik ve iyi dağılımlı bir dize karmasıdır. 5381 ile başlar ve hash * 33 + c ifadesini kullanır.

Çarpma ve toplama, bitleri basit toplamdan çok daha iyi karıştırır.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++))
        h = ((h << 5) + h) + c; /* h * 33 + c */
    return h;
}

int main(void) {
    printf("%lu\n", djb2("hello"));
    printf("%lu\n", djb2("world"));
    return 0;
}

FNV-1a Karması

FNV-1a her bayt üzerinde XOR işlemi yapar, ardından bir asal sayıyla çarpar. Basit, hızlı ve yaygın olarak kullanılır.

Sıra şöyledir: önce XOR, sonra çarpma (bu, 1a çeşididir).

#include <stdio.h>

unsigned long fnv1a(const char *s) {
    unsigned long h = 1469598103934665603UL;
    while (*s) {
        h ^= (unsigned char)*s++;
        h *= 1099511628211UL;
    }
    return h;
}

int main(void) {
    printf("%lu\n", fnv1a("key1"));
    printf("%lu\n", fnv1a("key2"));
    return 0;
}

Tamsayıları karma

Tamsayı anahtarlarının da karıştırılması gerekir; çünkü yalnızca x % capacity kullanmak, anahtarlar ortak örüntülere sahip olduğunda kümelenmeye yol açar. Çarpımsal bir karıştırma (Knuth) bitleri dağıtır.

#include <stdio.h>

unsigned hash_int(unsigned x, unsigned cap) {
    x *= 2654435761u; /* Knuth multiplicative */
    return x % cap;
}

int main(void) {
    for (unsigned i = 0; i < 5; i++)
        printf("%u -> %u\n", i, hash_int(i, 8));
    return 0;
}

İki Kuvveti Kapasiteler

Kapasite ikinin kuvvetiyse % capacity işlemini hızlı bir bit düzeyinde AND işlemiyle değiştirebilirsiniz: hash & (capacity - 1).

Bu yalnızca ikinin kuvvetinden bir eksiğin düşük bitleri tam bir maske oluşturduğu için çalışır.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16; /* power of two */
    unsigned index = (unsigned)(hash & (capacity - 1));
    printf("bucket = %u\n", index);
    return 0;
}

Modulo Neden Yavaş Olabilir

% işleci, AND işleminden daha yavaş olan bir bölme komutuna derlenir. Sıkı döngülerde bu fark önemlidir.

İki kuvveti boyutunda tablo: AND maskesi kullanın
Asal boyutlu tablo: modulo kullanın (zayıf karmalar için daha iyi dağılım sağlar)

Çakışmalar Kaçınılmazdır

Güvercin yuvası ilkesine göre, çok sayıda anahtarı daha az sayıda kovaya eşlemek çakışmaları zorunlu kılar. İyi bir karma bunları en aza indirir ancak tamamen ortadan kaldıramaz.

Sonraki derste çakışmaların nasıl çözüleceği ele alınacaktır.

Dağılım Gösterimi

DJB2'nin birkaç anahtarı 8 kovaya nasıl dağıttığını sayalım. İyi karmalar oldukça dengeli dağılır.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

int main(void) {
    const char *keys[] = {"apple", "banana", "cherry", "date"};
    int counts[8] = {0};
    for (int i = 0; i < 4; i++)
        counts[djb2(keys[i]) % 8]++;
    for (int i = 0; i < 8; i++)
        printf("bucket %d: %d\n", i, counts[i]);
    return 0;
}

Hızlı Kontrol

Karma işlevlerinin temellerini ne kadar anladığınızı test edin.

Özet

Bir karma işlevinin ne yaptığını ve anahtarların kovalara nasıl eşleneceğini öğrendiniz.

İyi karmalar belirlenebilir, hızlı ve dengelidir
DJB2 ve FNV-1a sağlam dize karmalarıdır
% capacity ile veya ikinin kuvvetleri için & (capacity-1) ile eşleyin
İşaretsiz türler kullanın; çakışmalar kaçınılmazdır

Sıkça Sorulan Sorular

“Özetleme İşlevleri” dersi ücretsiz mi?

Evet — “Özetleme İşlevleri” 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.

“Özetleme İşlevleri” dersinde ne öğreneceğim?

Anahtarları kovalara eşleme 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 1. dersidir.

“Özetleme İşlevleri” 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.

Bu kursun tüm dersleri

← C Academy Sayfasına Dön