Lesson 1Choosing collision strategy for static contexts: open addressing vs static separate chaining with arraysCompares open addressing and static separate chaining for fixed-memory systems, analyzing cache behavior, fragmentation, implementation complexity, and guidelines for choosing a collision strategy in embedded C projects relevant to local tech.
Review of open addressing propertiesReview of static separate chainingMemory layout and cache friendlinessComplexity and implementation effortGuidelines for strategy selectionLesson 2Memory and time complexity: documenting worst and expected probes, table load factor recommendations for embeddedAnalyzes memory and time complexity of static hash tables, documenting worst-case and expected probe counts, load factor limits, and practical sizing recommendations tailored to embedded sensor applications in our area.
Worst-case probe length analysisExpected probes under random hashingImpact of load factor on performanceMemory footprint and table sizingEmbedded-specific tuning guidelinesLesson 3Safe pointer handling: using indices instead of pointers, bounds checks, and avoiding NULL dereferencesCovers safe pointer handling in static hash tables by using indices instead of raw pointers, enforcing bounds checks, and designing APIs that prevent NULL dereferences and dangling references in C code, safe for our systems.
Indices vs pointers in static tablesImplementing robust bounds checkingAvoiding NULL and dangling referencesConverting indices to pointers safelyAPI patterns that enforce safetyLesson 4Open addressing techniques: linear probing, quadratic probing, tombstones, and deletion semantics without dynamic memoryDetails open addressing in static tables, including linear and quadratic probing, tombstone markers, and deletion rules that avoid dynamic allocation while preserving probe chains and predictable performance in C implementations.
Linear probing: algorithm and trade-offsQuadratic probing: clustering behaviorDesigning and using tombstone markersDeletion semantics and probe chain repairDetecting full table and failure modesLesson 5Integration with circular buffer: keeping most recent reading and policies for consistency (write-order, timestamps)Explores how a static hash table cooperates with a circular buffer to keep the latest sensor readings, define write ordering, use timestamps for freshness, and maintain consistency when updates or concurrent-like accesses occur locally.
Mapping sensor IDs to circular buffer slotsStoring only most recent reading per sensorTimestamp fields and monotonic orderingHandling overwrite and wrap-around casesConsistency rules for concurrent-style accessLesson 6init_table: setting empty markers, initializing free lists or tombstonesExplains init_table responsibilities, such as setting empty markers, initializing free lists or tombstones, clearing metadata, and ensuring the table starts in a consistent, verifiable state before first use in our projects.
Choosing and setting empty markersInitializing tombstone and state flagsBuilding initial free-list structuresZeroing or sanitizing table memoryValidation checks after initializationLesson 7insert_or_update_reading: insert, update, handling full table, and return codesDescribes the insert_or_update_reading API, including insertion, in-place update, handling a full table, return codes, and how to integrate collision handling while keeping the interface simple and robust in C for Botswana devs.
Function prototype and parameter choicesInsert path for new sensor IDsUpdate path for existing sensor IDsHandling full table and error returnsDesigning clear status and error codesLesson 8Designing the bucket array: table size selection, prime sizing, and compile-time constantsDescribes how to design the bucket array, including choosing table size, prime or power-of-two sizing, compile-time constants, and trade-offs between memory usage, speed, and hash function simplicity in local contexts.
Prime vs power-of-two table sizesRelating table size to key capacityUsing compile-time constants in CBalancing memory and performancePlanning for future size adjustmentsLesson 9Static chaining with arrays: node pool design, next indexes, and free-list management in static memoryCovers static separate chaining using arrays, including node pool layout, next index links, free-list management, and how to implement insertion, deletion, and traversal without heap allocation in constrained environments here.
Designing the node pool array layoutUsing next indexes instead of pointersManaging a free-list in static memoryInsertion and deletion in static chainsDetecting pool exhaustion and errorsLesson 10Key and value representations: using uint8_t sensor id and SensorReading copy semanticsExplains how to represent keys and values using uint8_t sensor IDs and SensorReading structs, focusing on copy semantics, alignment, padding, and avoiding aliasing or lifetime issues in a static hash table for our use.
Choosing uint8_t for sensor ID keysDesigning the SensorReading structCopy semantics vs pointer semanticsAlignment, padding, and struct layoutValidating and normalizing sensor IDsLesson 11Hash function choices for small keyspace: identity, multiplicative, and masking for 0–255 idsDiscusses hash functions for small uint8_t keyspaces, including identity mapping, multiplicative hashing, masking, and how to balance simplicity, distribution quality, and computational cost for 0–255 sensor IDs in Botswana.
Identity hash for dense ID rangesMultiplicative hashing for uint8_t keysBit masking and table index derivationAvoiding systematic clustering patternsTesting distribution with sample dataLesson 12find_reading_by_id: probe sequences, not-found vs found responses, and safe copy-out patternsFocuses on find_reading_by_id, including probe sequences, distinguishing found from not-found, safe copying of SensorReading out of the table, and avoiding undefined behavior or stale data exposure in C, practical here.
Function signature and return patternsImplementing probe sequences for lookupHandling not-found vs found resultsSafe copy-out of SensorReading valuesAvoiding stale or partially written data
