C语言中高效近期集合成员测试及12字节消息去重优化方案咨询

Great question! Let's break down your problem: you're handling infinite 12-byte random messages, need to deduplicate only the most recent 1000 entries, and your current linear scan of a circular buffer is CPU-intensive for high-throughput scenarios. Below are several far more efficient approaches tailored for C, balancing CPU and memory performance:

1. Open-Addressing Hash Table with LRU Eviction #

This is the gold standard for precise deduplication with fast lookups and controlled memory usage.

How it works: #

• Use an open-addressing hash table (no linked lists, better cache locality than chained hash tables) to store your 12-byte message keys. Lookups are average O(1) since you compute a hash of the 12-byte message, jump directly to the candidate slot, and do at most a few memcmp checks.
• Pair the hash table with a doubly linked list to track insertion order. When you exceed 1000 entries, evict the oldest entry (tail of the list) from both the list and hash table.

Implementation Notes for C: #

• For the hash function, use a fast, collision-resistant algorithm like MurmurHash3 (optimized for 12-byte inputs) to generate a 64-bit hash value. This minimizes collision chances for random data.
• Define a compact slot structure to save memory:

  typedef struct {
      uint8_t key[12];
      bool occupied;
      struct ListNode* list_node; // Pointer to linked list entry for eviction
  } HashSlot;
  
  typedef struct ListNode {
      uint8_t key[12];
      struct ListNode* prev;
      struct ListNode* next;
  } ListNode;
  

• Keep the hash table's load factor around 0.75 (capacity = ~1333 slots for 1000 entries) to balance memory usage and lookup speed.

Pros: #

• Precise deduplication (no false positives)
• Near-constant time lookups/insertions/evictions
• Better cache performance than chained hash tables

2. Bloom Filter (For Memory-Conscious Scenarios) #

If you can tolerate an extremely low false positive rate (e.g., <0.1%), a Bloom Filter is unbeatable for memory efficiency.

How it works: #

• A Bloom Filter uses a bit array and multiple hash functions to mark the presence of keys. For your 12-byte messages and 1000-entry limit, you only need ~880 bytes of memory — way smaller than your 12KB circular buffer.
• To handle "recent only" entries, use a sliding window Bloom Filter or periodically rebuild the filter when it reaches capacity. Alternatively, use a counting Bloom Filter (each bit becomes a small counter) to support evictions, though this increases memory usage slightly.

Implementation Snippet: #

// Bloom Filter with ~0.1% false positive rate for 1000 entries
typedef struct {
    uint64_t bits[110]; // 7040 bits (~880 bytes)
    size_t entry_count;
} BloomFilter;

// 3 distinct hash functions using MurmurHash3 with different seeds
uint64_t hash_seed1(const uint8_t* key) { /* ... */ }
uint64_t hash_seed2(const uint8_t* key) { /* ... */ }
uint64_t hash_seed3(const uint8_t* key) { /* ... */ }

bool bloom_contains(BloomFilter* bf, const uint8_t* key) {
    uint64_t h1 = hash_seed1(key) % (sizeof(bf->bits)*8);
    uint64_t h2 = hash_seed2(key) % (sizeof(bf->bits)*8);
    uint64_t h3 = hash_seed3(key) % (sizeof(bf->bits)*8);
    return (bf->bits[h1/64] & (1ULL << (h1%64))) &&
           (bf->bits[h2/64] & (1ULL << (h2%64))) &&
           (bf->bits[h3/64] & (1ULL << (h3%64)));
}

Pros: #

• Minimal memory footprint
• Extremely fast lookups (just a few hash computations and bit checks)

Caveat: #

• False positives are possible. If your use case can't tolerate this, pair the Bloom Filter with a small hash table to verify positive hits (this is called a "filter-and-verify" approach).

3. Direct 96-bit Key Hash Set #

Since your messages are exactly 12 bytes (96 bits), you can treat the message itself as a unique hash key (collisions are statistically negligible for 1000 random entries).

How it works: #

• Use an open-addressing hash table where the key is the 12-byte message directly. Compute a 64-bit hash of the 12-byte value to find the initial slot, then use linear probing to resolve collisions.
• Track insertion order with a circular buffer or linked list to evict old entries when you hit the 1000 limit.

Pros: #

• No need for a separate hash function (though using one still helps with slot distribution)
• Zero collision risk for practical purposes (the probability of two random 12-byte messages colliding is ~1 in 3e28 for 1000 entries)
• Simple to implement since the key is the raw message

Comparison to Your Current Approach #

Your circular buffer requires an O(n) linear scan (1000 memcmp operations per check) which becomes a CPU bottleneck at high throughput. All the methods above reduce lookup time to average O(1), cutting CPU usage dramatically while keeping memory usage comparable or lower.

Final Recommendations: #

• Precise deduplication, high throughput: Use an open-addressing hash table with LRU eviction.
• Memory is critical, low false positives acceptable: Use a Bloom Filter (with optional verification layer).
• Simple implementation, no third-party libs: Use a direct 96-bit key hash set.

内容的提问来源于stack exchange，提问作者fadedbee