C++ 学习补充 1：短链算法

短链算法

短链算法：
将长链接 转化为 一个短key
之所以不是短url 是因为 ，url 短链不区分大小写，可用空间比较小。

短链算法通常用于将一个长网址转换成一个较短的字符串，以便于分享和存储。这种算法通常需要满足以下条件：

1. 唯一性：每个短链对应一个唯一的长网址。
2. 可逆性：能够从短链恢复到原始的长网址。
3. 简短性：生成的短链尽可能短。
4. 不区分大小写：短链在生成和使用时不区分大小写。

实现短链算法的一种常见方法是使用哈希函数。以下是一些基本步骤：

1. 哈希生成：对原始网址使用哈希函数生成一个哈希值。例如，可以使用MD5、SHA-1等。
2. 编码：将哈希值转换为一个较短的字符串。这可以通过截取哈希值的一部分，或者将哈希值转换为一个基数更小的数字系统（如62进制，使用0-9和a-z）来实现。
3. 冲突解决：如果两个不同的网址生成了相同的短链，需要有一种机制来解决冲突，例如尝试不同的哈希函数或在短链后添加额外的字符。
4. 存储映射：将原始网址和生成的短链存储在一个数据库或映射表中，以便于反向查找。

请注意，短链算法的设计和实现可能涉及到复杂的数据结构和算法知识，以及对安全性和性能的考虑。如果你需要具体的实现代码或者更详细的解释，请告诉我，我可以提供进一步的帮助。

下面是一个简单的C++实现短链算法的示例代码。这个示例使用了MD5哈希函数来生成短链，并将其转换为一个基于62进制的字符串，以实现短链的生成。请注意，这个示例仅用于教学目的，实际应用中可能需要考虑更多的安全性和性能问题。

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <openssl/md5.h>// 将MD5哈希值转换为62进制字符串
std::string toBase62(unsigned char hash[MD5_DIGEST_LENGTH]) {const std::string base62Chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";std::string base62Str;for (int i = 0; i < 6; ++i) { // 取MD5的前6个字节unsigned char byte = hash[i];base62Str += base62Chars[byte % 62];byte /= 62;while (byte != 0) {base62Str += base62Chars[byte % 62];byte /= 62;}}return base62Str;
}// 生成短链
std::string generateShortLink(const std::string& longUrl) {unsigned char hash[MD5_DIGEST_LENGTH];// 计算MD5哈希值MD5((unsigned char*)longUrl.c_str(), longUrl.size(), hash);// 将哈希值转换为62进制字符串return toBase62(hash);
}int main() {std::string longUrl = "https://www.example.com/some/very/long/url/that/needs/to/be/shortened";std::string shortLink = generateShortLink(longUrl);std::cout << "Original URL: " << longUrl << std::endl;std::cout << "Short Link: " << shortLink << std::endl;return 0;
}

代码解释：

1. 头文件包含：包括了必要的C++标准库和OpenSSL库的头文件。
2. toBase62 函数：将MD5哈希值转换为62进制的字符串。它首先定义了一个包含62个字符的字符串base62Chars，然后对MD5哈希值的每个字节进行处理，将其转换为62进制的字符。
3. generateShortLink 函数：接受一个长网址作为输入，使用MD5算法计算其哈希值，然后调用toBase62函数将哈希值转换为短链。
4. main 函数：演示了如何使用generateShortLink函数生成短链，并打印原始网址和生成的短链。

注意事项：

• 这个示例代码使用了OpenSSL库来计算MD5哈希值，你需要在你的系统上安装OpenSSL库并正确配置编译器以链接这个库。
• MD5虽然广泛用于示例和教学，但在实际应用中可能不够安全，因为它容易受到碰撞攻击。在实际应用中，你可能会考虑使用更安全的哈希算法，如SHA-256。
• 这个示例没有实现冲突解决机制。在实际应用中，如果两个不同的长网址生成了相同的短链，你需要有一种策略来解决这种冲突，例如使用不同的哈希函数或添加随机数。
• 这个示例没有实现短链到长网址的映射存储和反向查找功能，这在实际应用中是必需的。

在C++中实现SHA-256算法，我们可以使用OpenSSL库，它提供了SHA-256的实现。以下是一个使用OpenSSL库实现SHA-256哈希的示例代码：

#include <iostream>
#include <string>
#include <openssl/sha.h>// 将输入字符串进行SHA-256哈希处理
std::string sha256Hash(const std::string& input) {unsigned char hash[SHA256_DIGEST_LENGTH];SHA256_CTX sha256;SHA256_Init(&sha256);SHA256_Update(&sha256, input.c_str(), input.size());SHA256_Final(hash, &sha256);// 将哈希值转换为十六进制字符串std::stringstream ss;for (int i = 0; i < SHA256_DIGEST_LENGTH; i++) {ss << std::hex << std::setw(2) << std::setfill('0') << (int)hash[i];}return ss.str();
}int main() {std::string input = "Hello, World!";std::string hash = sha256Hash(input);std::cout << "Original String: " << input << std::endl;std::cout << "SHA-256 Hash: " << hash << std::endl;return 0;
}

代码解释：

1. 头文件包含：包括了iostream、string和OpenSSL的sha.h头文件。

2. sha256Hash 函数：

   • 定义了一个unsigned char数组hash，大小为SHA256_DIGEST_LENGTH，用于存储SHA-256哈希结果。
   • 使用SHA256_CTX结构体来维护SHA-256的上下文。
   • 调用SHA256_Init初始化SHA-256上下文。
   • 使用SHA256_Update更新上下文，传入要哈希的字符串和字符串的长度。
   • 调用SHA256_Final完成哈希计算，并将结果存储在hash数组中。
   • 使用std::stringstream和十六进制格式化输出将哈希值转换为字符串。

3. main 函数：

   • 定义了一个示例字符串input。
   • 调用sha256Hash函数计算字符串的SHA-256哈希值。
   • 打印原始字符串和其对应的SHA-256哈希值。

注意事项：

• 确保你的系统安装了OpenSSL库，并且你的编译器配置正确以链接OpenSSL库。
• SHA-256哈希是单向的，意味着你不能从哈希值恢复原始输入。
• 这个示例代码仅用于演示如何使用OpenSSL库计算SHA-256哈希值。在实际应用中，你可能需要考虑错误处理、安全性和性能优化等问题。

要编译和运行这段代码，你需要确保链接了OpenSSL库。例如，如果你使用的是g++编译器，可以使用以下命令：

g++ -o sha256_example sha256_example.cpp -lcrypto

这将编译代码并链接OpenSSL的加密库（-lcrypto）。