บทเรียนที่ 1การเลือกกลยุทธ์การชนกันสำหรับบริบทแบบ static: open addressing เทียบ static separate chaining ด้วย arraysเปรียบเทียบ open addressing และ static separate chaining สำหรับระบบหน่วยความจำคงที่ วิเคราะห์พฤติกรรม cache, fragmentation, ความซับซ้อนในการใช้งาน และแนวทางในการเลือกกลยุทธ์การชนกันในโปรเจกต์ C ฝังตัว
ทบทวนคุณสมบัติของ open addressingทบทวน static separate chainingการจัดวางหน่วยความจำและ cache friendlinessความซับซ้อนและความพยายามในการใช้งานแนวทางในการเลือกกลยุทธ์บทเรียนที่ 2ความซับซ้อนของหน่วยความจำและเวลา: การบันทึกจำนวนการตรวจสอบ worst และ expected, คำแนะนำ load factor สำหรับฝังตัววิเคราะห์ความซับซ้อนของหน่วยความจำและเวลาของ static hash tables บันทึกจำนวนการตรวจสอบกรณีร้ายแรงที่สุดและที่คาดหวัง ขีดจำกัด load factor และคำแนะนำการกำหนดขนาดที่เหมาะสมสำหรับแอปพลิเคชันเซ็นเซอร์ฝังตัว
การวิเคราะห์ความยาวการตรวจสอบกรณีร้ายแรงที่สุดจำนวนการตรวจสอบที่คาดหวังภายใต้ random hashingผลกระทบของ load factor ต่อประสิทธิภาพการใช้หน่วยความจำและการกำหนดขนาดตารางแนวทางการปรับแต่งเฉพาะสำหรับฝังตัวบทเรียนที่ 3การจัดการ pointer อย่างปลอดภัย: การใช้ดัชนีแทน pointer, การตรวจสอบขอบเขต และหลีกเลี่ยง NULL dereferencesครอบคลุมการจัดการ pointer อย่างปลอดภัยใน static hash tables โดยใช้ดัชนีแทน raw pointers บังคับใช้การตรวจสอบขอบเขต และออกแบบ API ที่ป้องกัน NULL dereferences และ dangling references ในโค้ด C
ดัชนีเทียบ pointer ในตารางแบบ staticการใช้งาน bounds checking ที่แข็งแกร่งการหลีกเลี่ยง NULL และ dangling referencesการแปลงดัชนีเป็น pointer อย่างปลอดภัยรูปแบบ API ที่บังคับความปลอดภัยบทเรียนที่ 4เทคนิค open addressing: linear probing, quadratic probing, tombstones และ deletion semantics โดยไม่ใช้ dynamic memoryรายละเอียด open addressing ในตารางแบบ static รวมถึง linear และ quadratic probing, tombstone markers และกฎการลบที่หลีกเลี่ยง dynamic allocation ขณะที่ยังคงรักษา probe chains และประสิทธิภาพที่คาดเดาได้ในการใช้งาน C
Linear probing: อัลกอริทึมและการแลกเปลี่ยนQuadratic probing: พฤติกรรม clusteringการออกแบบและใช้งาน tombstone markersDeletion semantics และการซ่อมแซม probe chainการตรวจจับตารางเต็มและโหมดล้มเหลวบทเรียนที่ 5การรวมกับ circular buffer: การเก็บข้อมูลการอ่านล่าสุดและนโยบายความสอดคล้อง (write-order, timestamps)สำรวจวิธีที่ static hash table ทำงานร่วมกับ circular buffer เพื่อเก็บข้อมูลการอ่านค่าเซ็นเซอร์ล่าสุด กำหนดลำดับการเขียน ใช้ timestamps สำหรับความสดใหม่ และรักษาความสอดคล้องเมื่อมีการอัปเดตหรือการเข้าถึงแบบ concurrent
การแมป Sensor ID ไปยัง circular buffer slotsการเก็บเฉพาะข้อมูลการอ่านล่าสุดต่อเซ็นเซอร์ฟิลด์ timestamp และการเรียงลำดับแบบ monotonicการจัดการ overwrite และ wrap-aroundกฎความสอดคล้องสำหรับการเข้าถึงแบบ concurrentบทเรียนที่ 6init_table: การตั้งค่า empty markers, การเริ่มต้น free lists หรือ tombstonesอธิบายความรับผิดชอบของ init_table เช่น การตั้งค่า empty markers, การเริ่มต้น free lists หรือ tombstones, การเคลียร์ metadata และการทำให้แน่ใจว่าตารางเริ่มต้นในสถานะที่สอดคล้องและตรวจสอบได้ก่อนใช้งานครั้งแรก
การเลือกและตั้งค่า empty markersการเริ่มต้น tombstone และ state flagsการสร้างโครงสร้าง free-list เริ่มต้นการ zeroing หรือ sanitizing หน่วยความจำตารางการตรวจสอบหลังการเริ่มต้นบทเรียนที่ 7insert_or_update_reading: การแทรก, อัปเดต, การจัดการตารางเต็ม และ return codesอธิบาย API insert_or_update_reading รวมถึงการแทรก, การอัปเดตในที่ การจัดการตารางเต็ม, return codes และวิธีรวมการจัดการการชนกันขณะที่ยังคงรักษาอินเทอร์เฟซให้เรียบง่ายและแข็งแกร่งใน C
Function prototype และตัวเลือกพารามิเตอร์เส้นทางแทรกสำหรับ Sensor ID ใหม่เส้นทางอัปเดตสำหรับ Sensor ID ที่มีอยู่การจัดการตารางเต็มและการคืนข้อผิดพลาดการออกแบบ status และ error codes ที่ชัดเจนบทเรียนที่ 8การออกแบบ bucket array: การเลือกขนาดตาราง, prime sizing และ compile-time constantsอธิบายวิธีการออกแบบ bucket array รวมถึงการเลือกขนาดตาราง, prime หรือ power-of-two sizing, compile-time constants และการแลกเปลี่ยนระหว่างการใช้หน่วยความจำ ความเร็ว และความเรียบง่ายของ hash function
Prime เทียบ power-of-two table sizesการเชื่อมโยงขนาดตารางกับความจุ keyการใช้ compile-time constants ใน Cการปรับสมดุลหน่วยความจำและประสิทธิภาพการวางแผนปรับขนาดในอนาคตบทเรียนที่ 9Static chaining ด้วย arrays: การออกแบบ node pool, next indexes และการจัดการ free-list ในหน่วยความจำคงที่ครอบคลุม static separate chaining โดยใช้ arrays รวมถึงการจัดวาง node pool, ลิงก์ next index, การจัดการ free-list และวิธีการใช้งานการแทรก การลบ และการเดินทางโดยไม่ใช้ heap allocation ในสภาพแวดล้อมที่จำกัด
การออกแบบการจัดวาง node pool arrayการใช้ next indexes แทน pointerการจัดการ free-list ในหน่วยความจำคงที่การแทรกและลบใน static chainsการตรวจจับ pool exhaustion และข้อผิดพลาดบทเรียนที่ 10การแทนค่า key และ value: การใช้ uint8_t sensor id และ copy semantics ของ SensorReadingอธิบายวิธีการแทนค่า key และ value โดยใช้ uint8_t sensor ID และ struct SensorReading โดยมุ่งเน้น copy semantics, alignment, padding และการหลีกเลี่ยง aliasing หรือปัญหาช่วงชีวิตใน static hash table
การเลือก uint8_t สำหรับ key sensor IDการออกแบบ struct SensorReadingCopy semantics เทียบ pointer semanticsAlignment, padding และการจัดวาง structการตรวจสอบและ normalize sensor IDบทเรียนที่ 11การเลือก hash function สำหรับ keyspace ขนาดเล็ก: identity, multiplicative และ masking สำหรับ id 0–255พูดคุยเกี่ยวกับ hash functions สำหรับ uint8_t keyspace ขนาดเล็ก รวมถึง identity mapping, multiplicative hashing, masking และการปรับสมดุลระหว่างความเรียบง่าย คุณภาพการกระจาย และต้นทุนการคำนวณสำหรับ Sensor ID 0–255
Identity hash สำหรับช่วง ID ที่หนาแน่นMultiplicative hashing สำหรับ uint8_t keysBit masking และการได้มาซึ่ง table indexการหลีกเลี่ยงรูปแบบ clustering อย่างเป็นระบบการทดสอบการกระจายด้วยข้อมูลตัวอย่างบทเรียนที่ 12find_reading_by_id: ลำดับการตรวจสอบ, การตอบสนอง not-found เทียบ found และรูปแบบ copy-out ที่ปลอดภัยมุ่งเน้น find_reading_by_id รวมถึงลำดับการตรวจสอบ การแยกแยะ found จาก not-found การคัดลอก SensorReading ออกจากตารางอย่างปลอดภัย และการหลีกเลี่ยง undefined behavior หรือการเปิดเผยข้อมูลเก่าใน C
Function signature และรูปแบบการคืนค่าการใช้งานลำดับการตรวจสอบสำหรับ lookupการจัดการผลลัพธ์ not-found เทียบ foundการคัดลอก SensorReading ออกอย่างปลอดภัยการหลีกเลี่ยงข้อมูลเก่าหรือข้อมูลที่เขียนไม่สมบูรณ์
