Pelajaran 1Memilih strategi tabrakan untuk konteks statis: open addressing vs static separate chaining dengan arrayMembandingkan open addressing dan static separate chaining untuk sistem memori tetap, menganalisis perilaku cache, fragmentasi, kompleksitas implementasi, dan panduan untuk memilih strategi tabrakan dalam proyek C tertanam.
Ulasan sifat open addressingUlasan static separate chainingTata letak memori dan kesesuaian cacheKompleksitas dan upaya implementasiPanduan pemilihan strategiPelajaran 2Kompleksitas memori dan waktu: mendokumentasikan probe terburuk dan yang diharapkan, rekomendasi faktor beban tabel untuk tertanamMenganalisis kompleksitas memori dan waktu tabel hash statis, mendokumentasikan jumlah probe kasus terburuk dan yang diharapkan, batas faktor beban, dan rekomendasi ukuran praktis yang disesuaikan untuk aplikasi sensor tertanam.
Analisis panjang probe kasus terburukProbe yang diharapkan di bawah hashing acakDampak faktor beban pada performaJejak memori dan ukuran tabelPanduan penyetelan khusus tertanamPelajaran 3Penanganan pointer aman: menggunakan indeks alih-alih pointer, pemeriksaan batas, dan menghindari dereferensi NULLMembahas penanganan pointer aman dalam tabel hash statis dengan menggunakan indeks alih-alih pointer mentah, menegakkan pemeriksaan batas, dan merancang API yang mencegah dereferensi NULL dan referensi menggantung dalam kode C.
Indeks vs pointer dalam tabel statisMengimplementasikan pemeriksaan batas yang kuatMenghindari referensi NULL dan menggantungMengonversi indeks ke pointer dengan amanPola API yang menegakkan keamananPelajaran 4Teknik open addressing: linear probing, quadratic probing, tombstones, dan semantik penghapusan tanpa memori dinamisMerinci open addressing dalam tabel statis, termasuk linear dan quadratic probing, penanda tombstone, dan aturan penghapusan yang menghindari alokasi dinamis sambil mempertahankan rantai probe dan performa yang dapat diprediksi dalam implementasi C.
Linear probing: algoritma dan trade-offQuadratic probing: perilaku pengelompokanMerancang dan menggunakan penanda tombstoneSemantik penghapusan dan perbaikan rantai probeMendeteksi tabel penuh dan mode kegagalanPelajaran 5Integrasi dengan buffer sirkular: menyimpan pembacaan terbaru dan kebijakan untuk konsistensi (urutan tulis, timestamp)Mengeksplorasi bagaimana tabel hash statis bekerja sama dengan buffer sirkular untuk menyimpan pembacaan sensor terbaru, mendefinisikan urutan tulis, menggunakan timestamp untuk kesegaran, dan mempertahankan konsistensi saat pembaruan atau akses seperti konkuren terjadi.
Memetakan ID sensor ke slot buffer sirkularMenyimpan hanya pembacaan terbaru per sensorField timestamp dan urutan monotonikMenangani kasus overwrite dan wrap-aroundAturan konsistensi untuk akses gaya konkurenPelajaran 6init_table: mengatur penanda kosong, menginisialisasi daftar bebas atau tombstonesMenjelaskan tanggung jawab init_table, seperti mengatur penanda kosong, menginisialisasi daftar bebas atau tombstones, membersihkan metadata, dan memastikan tabel dimulai dalam status konsisten dan dapat diverifikasi sebelum penggunaan pertama.
Memilih dan mengatur penanda kosongMenginisialisasi tombstone dan flag statusMembangun struktur daftar bebas awalMengosongkan atau menyanitasi memori tabelPemeriksaan validasi setelah inisialisasiPelajaran 7insert_or_update_reading: sisip, perbarui, menangani tabel penuh, dan kode kembalianMenggambarkan API insert_or_update_reading, termasuk penyisipan, pembaruan di tempat, menangani tabel penuh, kode kembalian, dan cara mengintegrasikan penanganan tabrakan sambil menjaga antarmuka sederhana dan kuat dalam C.
Prototipe fungsi dan pilihan parameterJalur sisip untuk ID sensor baruJalur pembaruan untuk ID sensor yang adaMenangani tabel penuh dan kembalian kesalahanMerancang kode status dan kesalahan yang jelasPelajaran 8Merancang array bucket: pemilihan ukuran tabel, ukuran prima, dan konstanta waktu kompilasiMenggambarkan cara merancang array bucket, termasuk memilih ukuran tabel, ukuran prima atau pangkat-dua, konstanta waktu kompilasi, dan trade-off antara penggunaan memori, kecepatan, dan kesederhanaan fungsi hash.
Ukuran tabel prima vs pangkat-duaMenghubungkan ukuran tabel dengan kapasitas kunciMenggunakan konstanta waktu kompilasi dalam CMenyeseimbangkan memori dan performaMerencanakan penyesuaian ukuran masa depanPelajaran 9Static chaining dengan array: desain node pool, indeks next, dan pengelolaan free-list dalam memori statisMembahas static separate chaining menggunakan array, termasuk tata letak node pool, tautan indeks next, pengelolaan free-list, dan cara mengimplementasikan penyisipan, penghapusan, dan traversal tanpa alokasi heap dalam lingkungan terbatas.
Merancang tata letak array node poolMenggunakan indeks next alih-alih pointerMengelola free-list dalam memori statisPenyisipan dan penghapusan dalam rantai statisMendeteksi kehabisan pool dan kesalahanPelajaran 10Representasi kunci dan nilai: menggunakan uint8_t id sensor dan semantik salinan SensorReadingMenjelaskan cara merepresentasikan kunci dan nilai menggunakan ID sensor uint8_t dan struct SensorReading, berfokus pada semantik salinan, penyelarasan, padding, dan menghindari masalah aliasing atau masa pakai dalam tabel hash statis.
Memilih uint8_t untuk kunci ID sensorMerancang struct SensorReadingSemantik salinan vs semantik pointerPenyelarasan, padding, dan tata letak structMemvalidasi dan menormalkan ID sensorPelajaran 11Pilihan fungsi hash untuk ruang kunci kecil: identitas, multiplikatif, dan masking untuk id 0–255Membahas fungsi hash untuk ruang kunci uint8_t kecil, termasuk pemetaan identitas, hashing multiplikatif, masking, dan cara menyeimbangkan kesederhanaan, kualitas distribusi, dan biaya komputasi untuk ID sensor 0–255.
Hash identitas untuk rentang ID padatHashing multiplikatif untuk kunci uint8_tBit masking dan derivasi indeks tabelMenghindari pola pengelompokan sistematisMenguji distribusi dengan data sampelPelajaran 12find_reading_by_id: urutan probe, respons tidak-ditemukan vs ditemukan, dan pola copy-out amanBerfokus pada find_reading_by_id, termasuk urutan probe, membedakan ditemukan dari tidak-ditemukan, penyalinan aman SensorReading keluar dari tabel, dan menghindari perilaku tidak terdefinisi atau paparan data usang dalam C.
Tanda tangan fungsi dan pola kembalianMengimplementasikan urutan probe untuk pencarianMenangani hasil tidak-ditemukan vs ditemukanCopy-out aman nilai SensorReadingMenghindari data usang atau sebagian tertulis
