C Academy · บทเรียน

ฟังก์ชันแฮช

แมปคีย์ไปยังบักเก็ต

ฟังก์ชันแฮช เป็นบทเรียน C Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน C Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

ฟังก์ชันแฮชคืออะไร

ฟังก์ชันแฮชรับคีย์และสร้างดัชนีจำนวนเต็มในอาร์เรย์ของช่องเก็บ ฟังก์ชันนี้เป็นหัวใจของตารางแฮช โดยเปลี่ยนคีย์รูปแบบใด ๆ เช่น สตริง ให้เป็นตำแหน่งในอาร์เรย์ที่เข้าถึงได้อย่างรวดเร็ว

ข้อมูลเข้า: คีย์ (สตริง จำนวนเต็ม และอื่น ๆ)
ข้อมูลออก: ดัชนีช่องเก็บใน [0, capacity)

คุณสมบัติของแฮชที่ดี

ฟังก์ชันแฮชที่ดีต้องให้ผลลัพธ์แน่นอน ทำงานรวดเร็ว และกระจายคีย์ไปยังช่องเก็บอย่างสม่ำเสมอ

คีย์เดียวกันให้ดัชนีเดิมเสมอ
การเปลี่ยนแปลงคีย์เพียงเล็กน้อยทำให้ดัชนีเปลี่ยนแปลงมาก (การถล่ม)
เกิดการชนกันน้อยสำหรับข้อมูลทั่วไป

การแมปไปยังช่องเก็บ

เมื่อคำนวณค่าแฮชดิบแล้ว ให้แมปค่าเข้าตารางด้วยตัวดำเนินการมอดูโล: index = hash % capacity

ใช้ชนิด unsigned เพื่อให้มอดูโลไม่สร้างดัชนีติดลบ

#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;
}

แฮชผลรวมอย่างง่าย

ฟังก์ชันแฮชสตริงที่ง่ายที่สุดคือการนำค่าของอักขระมาบวกกัน วิธีนี้ทำได้ง่ายแต่กระจายได้ไม่ดี เพราะคำที่ประกอบด้วยอักขระชุดเดียวกันแต่เรียงต่างกันจะชนกัน

เรียกใช้เพื่อดูว่าสตริงต่างกันสองสตริงได้ค่าแฮชที่อยู่ใกล้กันอย่างไร

#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

DJB2 เป็นฟังก์ชันแฮชสตริงแบบคลาสสิกที่กระจายได้ดี คิดค้นโดย Daniel J. Bernstein โดยเริ่มต้นที่ 5381 และใช้ hash * 33 + c

การคูณแล้วบวกช่วยผสมบิตได้ดีกว่าการหาผลรวมธรรมดามาก

#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

FNV-1a ใช้ XOR กับแต่ละไบต์ แล้วคูณด้วยจำนวนเฉพาะ วิธีนี้เรียบง่าย รวดเร็ว และใช้งานอย่างแพร่หลาย

ลำดับคือ XOR ก่อน แล้วจึงคูณ ซึ่งเป็นรูปแบบ 1a

#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;
}

การทำแฮชจำนวนเต็ม

คีย์จำนวนเต็มยังต้องผ่านการผสมค่า เพราะการใช้ x % capacity เพียงอย่างเดียวจะกระจุกตัวเมื่อคีย์มีรูปแบบร่วมกัน การผสมแบบคูณ (Knuth) ช่วยกระจายบิต

#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;
}

ความจุที่เป็นกำลังสองของสอง

เมื่อความจุเป็นกำลังสองของสอง คุณสามารถแทนที่ % capacity ด้วย AND ระดับบิตที่รวดเร็วได้: hash & (capacity - 1)

วิธีนี้ใช้ได้เพราะบิตล่างของค่ากำลังสองของสองลบหนึ่งประกอบกันเป็นมาสก์เต็มรูปแบบ

#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;
}

เหตุใดมอดูโลจึงอาจช้า

ตัวดำเนินการ % ถูกคอมไพล์เป็นคำสั่งหาร ซึ่งช้ากว่า AND ในลูปที่ทำงานถี่ เรื่องนี้มีผลต่อประสิทธิภาพ

ตารางที่มีขนาดเป็นกำลังสองของสอง: ใช้มาสก์ AND
ตารางที่มีขนาดเป็นจำนวนเฉพาะ: ใช้มอดูโล (กระจายได้ดีกว่าสำหรับแฮชที่มีคุณภาพต่ำ)

การชนกันหลีกเลี่ยงไม่ได้

ตามหลักกล่องนกพิราบ การแมปคีย์จำนวนมากลงในช่องเก็บที่มีจำนวนน้อยกว่าย่อมรับประกันว่าจะเกิดการชนกัน แฮชที่ดีช่วยลดการชนกันได้ แต่ไม่สามารถกำจัดได้ทั้งหมด

บทเรียนถัดไปจะครอบคลุมวิธีจัดการการชนกัน

สาธิตการกระจาย

มานับกันว่า DJB2 กระจายคีย์สองสามรายการไปยังช่องเก็บ 8 ช่องอย่างไร แฮชที่ดีจะกระจายค่าได้ค่อนข้างสม่ำเสมอ

#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;
}

ตรวจสอบความเข้าใจอย่างรวดเร็ว

ทดสอบความเข้าใจเกี่ยวกับพื้นฐานของฟังก์ชันแฮช

สรุปทบทวน

คุณได้เรียนรู้ว่าฟังก์ชันแฮชทำงานอย่างไร และวิธีแมปคีย์ไปยังช่องเก็บ

แฮชที่ดีให้ผลแน่นอน รวดเร็ว และสม่ำเสมอ
DJB2 และ FNV-1a เป็นฟังก์ชันแฮชสตริงที่มีประสิทธิภาพดี
แมปด้วย % capacity หรือใช้ & (capacity-1) เมื่อความจุเป็นกำลังสองของสอง
ใช้ชนิดข้อมูลแบบ unsigned เพราะการชนกันหลีกเลี่ยงไม่ได้

คำถามที่พบบ่อย

บทเรียน “ฟังก์ชันแฮช” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “ฟังก์ชันแฮช” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส C Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส C Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “ฟังก์ชันแฮช”

แมปคีย์ไปยังบักเก็ต คุณปฏิบัติ C Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน C Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน C Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน

บทเรียน “ฟังก์ชันแฮช” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน C Academy นี้ได้ไหม

ได้ บทเรียน C Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

← กลับไปที่ C Academy