如何在 C++ 中实现反向 DNS 查询缓存

2025 年 3 月 21 日 | 阅读 25 分钟

反向 DNS 查询 是根据 IP 地址检索关联域名。在 C++ 中实现反向 DNS 查询缓存涉及创建一个数据结构来存储先前查询的结果，这可以显著提高性能，避免重复查询。在深入解释实现之前，我们先来了解一下理论。

反向 DNS 查询涉及查询 DNS 服务器以 IP 地址获取相应的域名。这个过程可能非常耗时，尤其是在频繁执行的情况下。为了缓解这种情况，会使用缓存来存储先前解析过的 IP 地址到域名映射。

反向 DNS 查询缓存应考虑以下方面：

数据结构：使用合适的数据结构来高效地存储映射。哈希表因其对查找操作平均常数时间复杂度而成为常见的选择。

过期机制：实现一种机制来使过期的条目失效，以确保缓存的准确性。这可能涉及将时间戳与每个条目关联，并定期检查过期的记录。

并发性：如果应用程序是多线程的，则应考虑线程安全，以防止在并发访问和更新缓存时出现竞态条件。

方法 1：使用 LRU 缓存

最近最少使用 (LRU) 缓存是一种广泛采用的数据访问优化策略，尤其是在经常访问的项更有可能再次被访问的情况下。在 C++ 中使用 LRU 缓存实现反向 DNS 查询缓存的上下文中，主要目标是提高存储和检索与 IP 地址关联的域名的效率。

LRU 缓存维护一个固定容量，确保它存储最近访问的项，同时在缓存达到限制时驱逐最近最少使用的项。在反向 DNS 查询中，其中域名与 IP 地址关联，此方法优先保留最近查询的域名，以便快速检索。使用 LRU 缓存有助于在内存效率和响应能力之间取得平衡，因为更频繁访问的条目不太可能被驱逐。

C++ 实现涉及创建一个 LRU 缓存，该缓存将 IP 地址与域名关联，并确保缓存大小不超过指定容量。这样，反向 DNS 查询缓存就可以优化数据访问模式，提供一种根据相应 IP 地址关联和检索域名的简化机制。

程序

#include <iostream>
#include <unordered_map>
#include <list>
// Class representing the LRU Cache
class LRUCache {
private:
 int capacity; // Maximum capacity of the cache
 // Hash map to store key-value pairs (IP address - Domain name)
 std::unordered_map<std::string, std::pair<std::string, std::list<std::string>::iterator>> cache;
 // Doubly linked list to maintain the order of access
 std::list<std::string> lruList;
public:
 //Constructor to initialize the LRU Cache with a given capacity
 LRUCache(int capacity) : capacity(capacity) {}
 // Function to perform a reverse DNS lookup in the cache
 std::string lookup(const std::string& ipAddress) {
 auto it = cache.find(ipAddress);
 if (it != cache.end()) {
 // If the IP address is present in the cache
 // Move the corresponding node to the front of the list (indicating recent use)
 lruList.erase(it->second.second);
 lruList.push_front(ipAddress);
 it->second.second = lruList.begin();
 return it->second.first; // Return the cached domain name
 }
 // If the IP address is not present in the cache, perform an actual reverse DNS lookup
 std::string domainName = performLookup(ipAddress);
 // Update the cache with the new entry
 cache[ipAddress] = {domainName, lruList.insert(lruList.begin(), ipAddress)};
 // Manage the cache size
 if (cache.size() > capacity) {
 // If the cache size exceeds the capacity, evict the least recently used item
 evictLRU();
 }
 return domainName;
 }
private:
 //Function to perform the actual reverse DNS lookup
 std::string performLookup(const std::string& ipAddress) {
 // Implement your reverse DNS lookup logic here
 // This could involve using system calls or a library like getaddrinfo
 // For demonstration purposes, return a placeholder result
 return "example.com";
 }
 //Function to evict the least recently used item from the cache
 void evictLRU() {
 // Remove the least recently used item from the linked list
 std::string lruIpAddress = lruList.back();
 lruList.pop_back();
 // Remove the corresponding entry from the hash map
 cache.erase(lruIpAddress);
 }
};
int main() {
 // Example usage of the LRUCache
 LRUCache dnsCache(5);
 std::string ipAddress1 = "8.8.8.8";
 std::string domainName1 = dnsCache.lookup(ipAddress1);
 std::cout << "IP Address: " << ipAddress1 << " has domain name: " << domainName1 << std::endl;
 std::string ipAddress2 = "192.168.1.1";
 std::string domainName2 = dnsCache.lookup(ipAddress2);
 std::cout << "IP Address: " << ipAddress2 << " has domain name: " << domainName2 << std::endl;
 // Continue with additional lookup operations...
 return 0; 
}

输出

IP Address: 8.8.8.8 has domain name: example.com
IP Address: 192.168.1.1 has domain name: example.com

解释

提供的 C++ 代码实现了一个用于管理反向 DNS 查询的 LRU 缓存，它结合使用了哈希映射和双向链表。

类定义

LRUCache 类封装了 LRU 缓存逻辑。它包含私有数据成员：
容量：一个整数，指示缓存可以容纳的最大条目数。
cache：一个无序映射，存储键值对，其中键是 IP 地址，值是包含域名和指向链表中相应节点的迭代器的对。
lruList：一个双向链表，表示IP 地址的访问顺序，最近使用的在前面，最少使用的在后面。

构造函数

构造函数使用指定的容量初始化 LRUCache，从而在管理内存使用方面具有灵活性。LRUCache 的构造函数使用用户指定的容量初始化缓存，提供了管理内存使用的灵活性。
这使得开发人员可以根据其应用程序的要求调整缓存的大小，在有效数据访问的需求和可用的内存资源之间取得平衡。

查找函数

查找函数是 LRU 缓存机制的核心。当请求特定IP 地址 (ipAddress) 的反向 DNS 查询时，该函数首先检查该地址是否存在于缓存中 (cache.find(ipAddress))。如果找到，它会通过将相应节点移动到链表的前面来更新访问顺序，表示最近使用。该函数返回缓存的域名。
如果 IP 地址不在缓存中，它将使用 performLookup 函数执行实际的反向 DNS 查询。然后，缓存将使用新条目进行更新，包括域名和一个插入链表前端的新节点。为了管理缓存大小，如果超过指定容量，将调用 evictLRU 函数来删除最近最少使用的项。

Perform Lookup 函数

performLookup 函数作为应用程序特定的反向 DNS 查询逻辑的占位符。在此函数中，开发人员可以根据其应用程序检索与IP 地址关联的域名的要求实现自定义代码。
这是集成域名解析算法或外部服务的关键自定义点，允许 LRUCache 基于其 LRU 驱逐策略有效地处理反向DNS 查询，同时适应应用程序域名解析过程的特定需求和复杂性。

Evict LRU 函数

evictLRU 函数负责维护缓存大小。如果缓存中的条目数超过容量，它将删除最近最少使用的项。这包括从链表中弹出最后一个节点，并从哈希映射中删除相应的条目。

示例主函数

主函数演示了LRUCache 类的用法。它创建了具有 5 个容量的缓存实例 (dnsCache)，并对两个示例 IP 地址（"8.8.8.8" 和 "192.168.1.1"）执行了反向 DNS 查询。然后将结果打印到控制台。

总之，此代码提供了一个针对反向 DNS 查询定制的 LRU 缓存的全面实现。哈希映射和双向链表的组合允许高效且动态地管理频繁访问的 IP 地址，在涉及重复反向 DNS 查询的场景中优化了可用资源的使用并提高了整体性能。

复杂度分析

时间复杂度分析

查找操作（缓存命中）

当对给定的IP 地址执行反向 DNS 查询并且在缓存中找到它（缓存命中）时，时间复杂度主要由两个操作决定：

搜索哈希映射：平均（摊销）为O(1)。

更新链表：O(1)，因为它涉及常数时间的指针操作。

这两个操作都贡献了总体的常数时间复杂度，使得缓存条目的查找操作非常高效。

查找操作（缓存未命中）

在缓存未命中（未在缓存中找到 IP 地址）的情况下，时间复杂度受反向 DNS 查询操作本身的影响。

实际的反向 DNS 查询（performLookup 函数）可能涉及系统调用或外部库，其时间复杂度取决于底层实现。我们将此表示为O(L)，其中 L 是查询操作的复杂度。

驱逐操作（缓存大小管理）

当缓存大小超过其容量时，会发生驱逐操作。

删除最近最少使用的项涉及链表和哈希映射上的操作：

从链表中删除节点：O(1)。

从哈希映射中删除条目：平均O(1)。

驱逐操作的总时间复杂度为常数。

查找操作的总时间复杂度（无论是缓存命中还是未命中）取决于反向 DNS 查询操作的复杂性，而缓存命中操作平均（摊销）均为常数时间。

空间复杂度分析

哈希映射

哈希映射（缓存）存储键值对（IP 地址 - 域名），并且预计其大小与缓存条目的数量成正比。

哈希映射的空间复杂度为O(N)，其中 N 是缓存中不同 IP 地址的数量。

链表

双向链表(lruList)维护 IP 地址的访问顺序，并且预计其大小与缓存条目的数量成正比。

链表的空间复杂度为O(N)，其中 N 是缓存中不同 IP 地址的数量。

总空间复杂度由哈希映射和链表所需的空间所决定。

总空间复杂度为O(N)，其中 N 是缓存中不同 IP 地址的数量。

总之，提供的LRU 缓存实现展示了一种高效且动态的结构，用于管理反向 DNS 查询。时间复杂度针对缓存命中进行了优化，提供常数时间操作，而空间复杂度则随缓存中不同 IP 地址的数量线性缩放。

方法 2：固定大小缓存，无过期

在这种具有固定大小且无过期机制的简化缓存方法中，主要目标是高效地管理 IP 地址和域名之间的映射，同时保持缓存大小恒定。与最近最少使用 (LRU) 缓存等更复杂的缓存不同，此方法不跟踪条目的访问顺序。

缓存设计为固定容量，确保其不超过指定限制。当添加新条目且缓存达到容量时，会发挥作用简单的驱逐策略。该策略通常涉及删除最旧或最近添加最少的条目，以为新条目腾出空间。

这种简化的缓存设计很有优势，适用于必须严格控制内存占用量且应用程序不需要对访问模式进行复杂跟踪的场景。虽然它缺乏 LRU 策略的复杂性，但它为基本缓存需求提供了轻量级且简单的解决方案，最大限度地减少了开销。

使用此方法的开发人员必须意识到，缓存中的条目没有访问新近度的概念。因此，驱逐策略仅基于条目添加的顺序。当主要关注点是保持缓存大小不变而不必复杂地记账时，这种简单性是有益的。

简化的缓存方法为 IP 地址到域名映射的高效存储和检索提供了一个简单的解决方案。凭借其固定大小和驱逐策略，它在内存效率和简单性之间取得了平衡，使其适用于基本缓存需求就足够的情况。

程序

#include <iostream>
#include <unordered_map>
class SimpleCache {
private:
 static const int capacity = 5; // Fixed capacity of the cache
 std::unordered_map<std::string, std::string> cache; // Hash map to store IP address - Domain name mappings
public:
 //Function to perform a reverse DNS lookup in the cache
 std::string lookup(const std::string& ipAddress) {
 // Check if the IP address is present in the cache
 auto it = cache.find(ipAddress);
 if (it != cache.end()) {
 // If found, return the cached domain name
 return it->second;
 }
 // If not found, perform an actual reverse DNS lookup
 std::string domainName = performLookup(ipAddress);
 // Update the cache with the new entry
 cache[ipAddress] = domainName;
 // Manage cache size
 if (cache.size() > capacity) {
 // If the cache size exceeds the capacity, evict the least recently used item
 evictLRU(); // This example uses a simple fixed-size cache with no specific eviction strategy
 }
 return domainName;
 }
private:
 //Function to perform the actual reverse DNS lookup
 std::string performLookup(const std::string& ipAddress) {
 // Implement your reverse DNS lookup logic here
 // This could involve using system calls or a library like getaddrinfo

 // For demonstration purposes, return a placeholder result
 return "example.com";
 }
 //Function to evict the least recently used item from the cache
 void evictLRU() {
 // Optional eviction strategy (not implemented in this example)
 // This could involve selecting and removing the least recently used item
 // For simplicity, this example does not implement a specific eviction strategy
 std::cout << "Cache eviction: Implement your eviction strategy here." << std::endl;
 }
};
int main() {
 SimpleCache dnsCache; // Create an instance of the SimpleCache
 // Example usage
 std::string ipAddress1 = "8.8.8.8";
 std::string domainName1 = dnsCache.lookup(ipAddress1);
 std::cout << "IP Address: " << ipAddress1 << " has domain name: " << domainName1 << std::endl;
 std::string ipAddress2 = "192.168.1.1";
 std::string domainName2 = dnsCache.lookup(ipAddress2);
 std::cout << "IP Address: " << ipAddress2 << " has domain name: " << domainName2 << std::endl;
 // Continue with additional lookup operations...
 return 0; 
}

输出

IP Address: 8.8.8.8 has domain name: example.com
IP Address: 192.168.1.1 has domain name: example.com

解释

提供的 C++ 代码举例说明了用于存储和检索反向 DNS 查询结果的固定大小缓存的实现，该缓存没有过期机制。这种方法以简单高效为特征，在需要限制内存使用而不考虑访问顺序或采用高级驱逐策略时提供基本解决方案。

类定义

SimpleCache 类封装了固定大小缓存的逻辑。它包含一个定义最大容量（capacity）的静态常量和一个无序映射（cache），用于存储键值对，其中键是IP 地址，值是相应的域名。

查找函数

核心功能在于查找函数，当请求特定 IP 地址的反向 DNS 查询时会调用该函数。该函数首先通过搜索哈希映射来检查 IP 地址是否已存在于缓存中。如果找到，则返回相应的域名，从而提供快速的缓存命中响应。
在缓存未命中的情况下，即 IP 地址不在缓存中，该函数会使用 performLookup 函数执行实际的反向 DNS 查询。然后将结果添加到缓存中，将IP 地址与其域名关联。
该函数还包括管理缓存大小的逻辑。如果条目数超过固定容量，则通过 evictLRU 函数调用可选的驱逐策略。在此示例中，驱逐策略没有明确定义，而是作为开发人员实现特定策略的占位符。

Perform Lookup 函数

performLookup 函数是此缓存方法中的一个关键自定义点，充当反向 DNS 查询逻辑的占位符。在此空间中，开发人员可以灵活地实现满足其特定需求的域名检索机制。这包括集成外部库、系统调用或任何对查询操作至关重要的自定义逻辑。
该函数充当缓存和底层域名解析过程之间的桥梁，能够无缝适应各种应用程序需求。无论是利用专有算法、第三方服务还是系统级功能，此自定义点都使开发人员能够将反向 DNS 查询过程与应用程序的独特复杂性保持一致，同时确保从关联的IP 地址高效可靠地检索域名。

驱逐函数

evictLRU 函数在此缓存设计中作为可选的驱逐策略。当缓存达到其预定容量时；调用此函数来驱逐最近最少使用的项。其实现是开放式的，允许开发人员根据其应用程序的特定需求定制驱逐策略。这种灵活性使开发人员能够集成符合其应用程序用例和访问模式的驱逐机制。
为简单起见，提供的示例包含一个占位符消息，指示开发人员应实现其驱逐策略。这种方法鼓励自定义，并认识到不同应用程序在缓存已满时选择要驱逐的项目时可能有不同的考虑。
开发人员可以在 evictLRU 函数中使用各种策略，从基本的FIFO（先进先出）或LIFO（后进先出）方法到基于访问频率或应用程序特定标准的更复杂的算法。这种适应性允许缓存针对不同场景的独特需求进行精细调整，确保驱逐策略与应用程序的总体目标保持一致。

主函数

主函数作为使用SimpleCache 类的示例。它创建了缓存实例 (dnsCache)，并对两个示例 IP 地址（"8.8.8.8" 和 "192.168.1.1"）执行了反向 DNS 查询。然后将结果打印到控制台。

用例

这种方法适用于只需要基本固定大小缓存且无需跟踪访问模式或实现复杂驱逐策略的场景。它提供了一种限制内存使用量的简单解决方案，适用于涉及重复反向 DNS 查询的应用程序，在简单性和效率之间取得了平衡。

总之，提供的代码提供了固定大小缓存的全面实现，该缓存没有过期机制，突出了缓存结构、查找操作、驱逐策略和用于自定义的占位符函数的关键组成部分。开发人员可以根据特定需求和使用场景扩展和调整此代码。

复杂度分析

时间复杂度分析

查找操作（缓存命中）

当调用查找函数并且 IP 地址在缓存中找到（缓存命中）时，时间复杂度主要取决于无序映射的查找操作，其平均时间复杂度为O(1)。这是一个高效的常数时间操作。

查找操作（缓存未命中）

在缓存未命中的情况下，时间复杂度受实际反向 DNS 查询操作的影响，表示为O(L)，其中 L 是查询操作的复杂度。这里的复杂度取决于具体的实现细节和获取与 IP 地址关联的域名的外部调用。

驱逐操作

当由于缓存超过其固定容量而触发驱逐时，驱逐操作涉及从无序映射中删除一个条目。此操作的平均时间复杂度也为O(1)。驱逐策略本身可能会根据所选策略引入额外的复杂性，但在本示例中，它仅作为一个占位符，没有具体的实现。

无论缓存命中还是未命中，反向 DNS 查询的总时间复杂度都由查找操作和实际反向 DNS 查询的复杂性决定。如果我们表示查找复杂度为O(L)，其中 L 是查找操作的复杂度，则总时间复杂度可以表示为O(1 + L)。

空间复杂度分析

哈希映射

此缓存实现中使用的主要数据结构是无序映射（cache）。哈希映射的空间复杂度为O(N)，其中 N 是缓存中的条目数。在最坏情况下，条目数可能等于缓存的固定容量。

额外内存

除了无序映射之外，还有恒定的额外内存用于其他变量和函数，这构成了恒定的空间复杂度。

总空间复杂度由无序映射所需的空间决定。在此示例中，空间复杂度为O(N)，其中 N 是缓存中的条目数，并且相对于缓存的固定容量保持相对恒定。

用例注意事项

这种固定大小且无过期机制的缓存适用于优先级为简单性和可预测内存占用量，而不是复杂的驱逐策略或跟踪访问模式的场景。

时间复杂度高效，尤其是对于缓存命中，但实际的反向 DNS 查询复杂度可能因应用程序的具体要求而异。

开发人员应仔细考虑驱逐策略，这取决于应用程序的特性以及在缓存中保留某些条目的重要性。

方法 3：基于时间的过期缓存

在基于时间的过期缓存中，主要思想是将时间戳与缓存中的每个条目关联起来，指示条目何时添加或最后一次访问。超过预定义时间阈值的条目被视为过期，这意味着它们不再被视为有效或相关，因此会被驱逐。

关键组件

时间戳

每个缓存条目都添加了一个时间戳，该时间戳反映了其添加时间或最后访问时间。此时间戳对于确定条目的年龄至关重要。

时间阈值

建立一个预定义的时间阈值来确定缓存中条目的最大允许年龄。超过此阈值的条目被视为过期。

驱逐机制

采用一种驱逐机制来定期检查缓存条目的时间戳。已超过定义的时限的条目将被识别并随后被驱逐，为新数据腾出空间。

可选的访问更新

在条目添加到缓存后访问它们的情况下，可以更新时间戳以反映最近的访问时间。这可以防止条目被过早驱逐，如果它们继续被积极使用。

操作流程

添加条目

当新条目添加到缓存时，其时间戳设置为当前时间。此时间戳表示条目的创建时间。

查找操作

在查找操作期间，如果找到条目且其时间戳表明未超过时间阈值，则该条目被视为有效并返回。否则，它被视为已过期，并启动驱逐过程。

驱逐过程

驱逐过程涉及定期扫描缓存条目。对于每个条目，将时间戳与当前时间以及预定义的时间阈值进行比较。

如果条目的时间戳表明它已超过阈值，则将其标记为驱逐。

驱逐过程可能由特定事件触发，例如添加新条目或查找操作。

缓存维护

定期缓存维护对于确保及时识别和删除过期的条目至关重要。维护频率取决于数据访问速率和对数据集变化的预期响应能力等因素。

优点

自动管理：缓存根据时间自动处理过时条目的删除。

相关性控制：适用于数据相关性随时间而减弱的情况。

可预测的行为：缓存的行为是可预测的，使其适用于具有明确数据有效性期限的场景。

缺点

潜在数据丢失：条目可能在它们真正过时之前就被驱逐，如果访问模式是零星的，则可能导致数据丢失。

附加开销：添加时间戳会在空间和计算复杂性方面引入开销。

程序

#include <iostream>
#include <unordered_map>
#include <chrono>
#include <thread> // Include the thread header
class TimeBasedCache {
private:
 using Clock = std::chrono::high_resolution_clock;
 using TimePoint = std::chrono::time_point<Clock>;
 struct CacheEntry {
 std::string value;
 TimePoint timestamp;
 };
 std::unordered_map<std::string, CacheEntry> cache;
 std::chrono::seconds timeThreshold;
public:
 TimeBasedCache(int secondsThreshold) : timeThreshold(secondsThreshold) {}
 //Function to add a new entry to the cache
 void addEntry(const std::string& key, const std::string& value) {
 cache[key] = {value, Clock::now()};
 }
 // Function to perform a lookup in the cache
 std::string lookup(const std::string& key) {
 auto it = cache.find(key);
 if (it != cache.end()) {
 CacheEntry& entry = it->second;
 // Check if the entry has not exceeded the time threshold
 if (isEntryValid(entry.timestamp)) {
 return entry.value;
 } else {
 evictEntry(key);
 }
 }
 return ""; // Return empty string for cache miss
 }
private:
 //Function to check if an entry is still valid based on the time threshold
 bool isEntryValid(const TimePoint& timestamp) {
 auto currentTime = Clock::now();
 auto elapsedTime = std::chrono::duration_cast<std::chrono::seconds>(currentTime - timestamp);
 return elapsedTime <= timeThreshold;
 }
 //Function to evict an expired entry from the cache
 void evictEntry(const std::string& key) {
 cache.erase(key);
 std::cout << "Entry with key '" << key << "' evicted due to expiration." << std::endl;
 }
};
int main() {
 // Example usage of TimeBasedCache with a time threshold of 10 seconds
 TimeBasedCache timeBasedCache(10);
 // Add entries to the cache
 timeBasedCache.addEntry("Key1", "Value1");
 timeBasedCache.addEntry("Key2", "Value2");
 // Lookup entries in the cache
 std::cout << "Lookup result for Key1: " << timeBasedCache.lookup("Key1") << std::endl;
 std::cout << "Lookup result for Key2: " << timeBasedCache.lookup("Key2") << std::endl;
 // Wait for more than 10 seconds (time threshold) to simulate expiration
 std::this_thread::sleep_for(std::chrono::seconds(11));
 // Attempt to lookup the expired entry
 std::cout << "Lookup result for Key1 after expiration: " << timeBasedCache.lookup("Key1") << std::endl;
 return 0; 
}

输出

Lookup result for Key1: Value1
Lookup result for Key2: Value2
Lookup result for Key1 after expiration: Entry with key 'Key1' evicted due to expiration

解释

类定义

引入了TimeBasedCache类来封装基于时间的缓存逻辑。它使用 std::chrono 来管理与时间相关的操作。构造函数和初始化
TimeBasedCache 的构造函数接受一个整数参数，表示秒为单位的时间阈值。此参数用于定义缓存条目的最大允许年龄。
在类内部，定义了一个 CacheEntry 结构，代表缓存中的每个条目。它包括条目的实际值（value）和指示条目何时添加或最后访问的时间戳（timestamp）。
缓存本身实现为std::unordered_map，其中键是字符串（代表缓存条目标识符），值是 CacheEntry 实例。

函数：addEntry

addEntry 函数将新条目添加到缓存中。它接受键和值作为参数，创建一个带有当前时间戳的新CacheEntry，并将其存储在缓存中。

函数：lookup

lookup 函数负责为给定键在缓存中执行查找。它检查键是否在缓存中。
如果找到键，它会检查关联的条目的时间戳是否表明它未超过时间阈值。如果有效，则返回缓存的值。
如果时间戳表明已过期，则调用evictEntry函数删除过期条目，并返回一个空字符串。

函数：isEntryValid

isEntryValid 函数根据条目的时间戳和时间阈值确定条目是否仍然有效。它计算自条目时间戳以来经过的时间，并将其与时间阈值进行比较。函数：evictEntry
evictEntry 函数使用无序映射的 erase 方法从缓存中删除过期条目。打印相应的消息以指示驱逐。

主函数：示例用法

主函数演示了 TimeBasedCache 类的用法。它使用10 秒的时间阈值初始化一个实例，并将条目添加到缓存中。
执行查找操作，并包含模拟的等待超过 10 秒以触发条目过期。
该实现利用 C++ 功能来高效地管理基于时间的过期缓存。它演示了时间戳管理、缓存查找、驱逐的关键组件，并提供了一个结构化的类来封装这些功能。主函数中的示例用法展示了缓存如何随时间处理条目。

复杂度分析

时间复杂度分析

查找操作（有效条目）

在查找函数中，当缓存包含有效条目（即缓存命中）时，时间复杂度主要由 isEntryValid 函数决定。isEntryValid 函数计算自条目时间戳以来经过的时间，此操作的时间复杂度为O(1)。

查找操作（过期条目）

在找到条目但已过期的情况下，将调用 evictEntry 函数，该函数涉及从无序映射中删除条目。无序映射上的 erase 操作的平均时间复杂度为O(1)。

添加操作（addEntry）

addEntry 函数涉及创建一个带有当前时间戳的新条目并将其插入无序映射。这两个操作（插入和时间戳分配）的平均时间复杂度均为O(1)。

驱逐操作（evictEntry）

驱逐过程涉及从无序映射中删除条目，erase 操作的平均时间复杂度为O(1)。

该代码的总时间复杂度由O(1)操作决定，使其对于查找和添加等常见缓存操作非常高效。但是，需要注意的是，实际效率可能取决于无序映射的特定实现和系统特性等因素。

空间复杂度分析

缓存存储

用于缓存的主要数据结构是 std::unordered_map，它存储具有键和关联值的条目。缓存的空间复杂度为O(N)，其中 N 是缓存中的条目数。在最坏情况下，条目数可能接近缓存的固定容量。

附加数据

缓存中的每个条目由 CacheEntry 结构表示，该结构包括一个用于值的字符串和一个用于时间戳的 TimePoint。每个条目的空间复杂度为 O(1)，因为它存储了恒定的数据量。

总空间复杂度由无序映射所需的空间决定，使其为 O(N)，其中 N 是条目数。此空间复杂度相对于缓存的固定容量保持相对恒定。

用例注意事项

提供的代码为常见缓存操作提供了高效的时间复杂度。

空间复杂度是合理的，因为它与缓存中的条目数成正比。

开发人员应考虑应用程序的特性，例如预期的缓存大小和访问模式，以确定空间复杂度是否符合其用例。

总之，代码提供了一种高效且可扩展的基于时间的过期缓存实现，为常见操作提供了 O(1) 时间复杂度，并且O(N) 空间复杂度与缓存中的条目数成正比。

方法 4：基于频率的驱逐缓存

在基于频率的驱逐缓存中，驱逐决策受每个缓存条目的访问频率影响。当缓存达到其容量时，访问频率较低的条目被视为驱逐候选。此方法能够适应不断变化的访问模式，在某些条目比其他条目访问更频繁的情况下可能很有益。

关键组件

访问频率跟踪

每个缓存条目都包含一个计数器或频率值，用于跟踪该条目被访问的次数。每次对条目执行查找或访问操作时都会更新频率。

驱逐策略

当缓存达到满容量且需要添加新条目时，驱逐策略包括识别并驱逐访问频率最低的项。这确保了访问频率较低的条目更有可能被驱逐。

优点

适应不断变化的模式

缓存动态地适应不断变化的访问模式。过去经常访问的条目更有可能被保留，从而适应不断发展的用法模式。

针对特定条目进行了优化

当某些条目比其他条目访问更频繁时很有用。这可以防止高频率条目被过早驱逐。

缺点

附加跟踪开销

需要维护其他数据结构（例如计数器）来跟踪每个条目的访问频率。这会带来内存和计算需求的开销。

具有尖峰的性能问题

在访问频率突然出现峰值的情况下，性能可能不是最优的。如果以前访问频率较低的条目突然受到欢迎，驱逐策略可能无法快速响应，从而影响缓存效果。

程序

#include <iostream>
#include <unordered_map>
#include <algorithm>
class FrequencyBasedCache {
private:
 struct CacheEntry {
 std::string value;
 int accessFrequency;
 };
 std::unordered_map<std::string, CacheEntry> cache;
 size_t capacity;
public:
 FrequencyBasedCache(size_t cacheCapacity) : capacity(cacheCapacity) {}
 void addEntry(const std::string& key, const std::string& value) {
 if (cache.size() >= capacity) {
 evictLeastFrequentlyAccessed();
 }
 cache[key] = {value, 0}; // Initialize access frequency to 0 for new entries
 }
 std::string lookup(const std::string& key) {
 auto it = cache.find(key);
 if (it != cache.end()) {
 CacheEntry& entry = it->second;
 entry.accessFrequency++;
 return entry.value;
 }
 return ""; // Return empty string for cache miss
 }
private:
 void evictLeastFrequentlyAccessed() {
 auto minFreqIt = std::min_element(
 cache.begin(), cache.end(),
 [](const auto& a, const auto& b) {
 return a.second.accessFrequency < b.second.accessFrequency;
 });
 if (minFreqIt != cache.end()) {
 cache.erase(minFreqIt);
 }
 }
};
int main() {
 // Example usage of FrequencyBasedCache with a capacity of 2
 FrequencyBasedCache frequencyBasedCache(2);
 // Add entries to the cache
 frequencyBasedCache.addEntry("Key1", "Value1");
 frequencyBasedCache.addEntry("Key2", "Value2");
 // Lookup entries in the cache
 std::cout << "Lookup result for Key1: " << frequencyBasedCache.lookup("Key1") << std::endl;
 std::cout << "Lookup result for Key2: " << frequencyBasedCache.lookup("Key2") << std::endl;
 // Add another entry to trigger eviction (capacity is 2)
 frequencyBasedCache.addEntry("Key3", "Value3");
 // Attempt to lookup the evicted entry (Key1 has the least access frequency)
 std::cout << "Lookup result for Key1 after eviction: " << frequencyBasedCache.lookup("Key1") << std::endl;
 return 0; 
}

输出

Lookup result for Key1: Value1
Lookup result for Key2: Value2
Lookup result for Key1 after eviction: Value1

解释

类定义

代码以FrequencyBasedCache 类的定义开始，该类封装了基于频率的驱逐缓存逻辑。它包含一个私有的 CacheEntry 结构，代表每个缓存条目，其中包含一个值和一个访问频率计数器。

构造函数和初始化

构造函数接受缓存容量参数，并初始化私有成员变量 capacity 以表示缓存可以容纳的最大条目数。

addEntry 函数

addEntry 函数负责将新条目添加到缓存中。它检查缓存是否已达到容量。如果达到，它将调用 evictLeastFrequentlyAccessed 函数来为新条目腾出空间。然后，该条目将以0 的初始访问频率添加到缓存中。

查找函数

lookup 函数旨在为给定键在缓存中执行查找。如果键在缓存中找到，则增加相应条目的访问频率以反映其最近使用。然后返回与键关联的值。如果未找到键，则返回一个空字符串，表示缓存未命中。

evictLeastFrequentlyAccessed 函数

evictLeastFrequentlyAccessed 函数负责在缓存达到容量时识别和驱逐缓存中访问频率最低的条目。它使用 std::min_element 算法查找访问频率最低的条目，然后从缓存中删除该条目。

main 函数：示例用法

主函数作为FrequencyBasedCache 类的示例用法。使用容量为 2 的类实例化一个实例。将条目添加到缓存中，并执行查找以演示缓存行为。
添加第三个条目会触发驱逐过程，随后的查找突出了驱逐结果。

示例场景

在示例中，“Key1”、“Key2”和“Key3”代表键，“Value1”、“Value2”和“Value3”代表相应的值。缓存的容量为 2，因此添加第三个条目将触发最不常访问条目的驱逐。

输出显示

在整个主函数中，std::cout 语句用于显示查找操作和驱逐结果。这有助于说明频率驱动的驱逐缓存对不同访问模式的响应行为。
该代码提供了频率驱动的驱逐缓存的清晰简洁的实现。它演示了缓存如何适应访问模式，在必要时驱逐访问频率最低的条目，并针对访问频率较高的条目进行优化。

主函数中的示例用法突出了频率驱动的驱逐策略在缓存上下文中的实际应用。开发人员可以根据特定需求和使用场景来利用和扩展此实现。

下一个主题Trampoline-in-cpp

← 上一个下一个 →

如何在 C++ 中实现反向 DNS 查询缓存

方法 1：使用 LRU 缓存

程序

方法 2：固定大小缓存，无过期

程序

方法 3：基于时间的过期缓存

程序

方法 4：基于频率的驱逐缓存

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

如何在 C++ 中实现反向 DNS 查询缓存

方法 1：使用 LRU 缓存

程序

方法 2：固定大小缓存，无过期

程序

方法 3：基于时间的过期缓存

程序

方法 4：基于频率的驱逐缓存

程序

相关帖子

C++ 烟花算法

C++ std::start_lifetime_as, std::start_lifetime_as_array 函数

C++ 中的对象池设计模式

为什么 C++ 中的 std::vector 不能声明 AbstractClass

C++ 所有后缀的 Trie

C++ 中使用 Pell 数查找

C++ std::tuple_cat() 函数

C++ 中的 std::ios_base::pword

C++ 封装索引

C++ 中的前向声明是什么

订阅 Tpoint Tech

联系信息