如何将表示网格边的整数对哈希为数组索引？

嘿，你的思路完全找对了——网格里的边是无向的，不管顶点顺序是(v1, v2)还是(v2, v1)，本质都是同一条边，所以通过排序顶点来生成统一哈希的做法，刚好解决了键的唯一性问题。我来给你细化这个实现，再补充些实用的优化建议：

一、最简高效的哈希函数实现 #

直接把排序后的两个顶点拼接成一个64位整数，是性能最优的方案，毕竟没有额外的复杂运算，代码也简洁：

#include <algorithm> // 用于std::min和std::max

__int64 GetEdgeHash(int vertex1, int vertex2) {
    // 先固定顶点顺序，小的在前，大的在后
    const int min_v = std::min(vertex1, vertex2);
    const int max_v = std::max(vertex1, vertex2);
    
    // 将两个32位int拼接成64位哈希（假设你的int是32位）
    return static_cast<__int64>(min_v) << 32 | (static_cast<unsigned int>(max_v) & 0xFFFFFFFFLL);
}

这样一来，(0,2)和(2,0)都会生成0 << 32 | 2的哈希值，完全一致，完美解决无向边的键冲突问题。而且这个计算过程几乎是瞬时的，特别适合需要高频查找边的场景。

二、unordered_map的使用要点 #

• 用上面生成的__int64作为unordered_map的键，值存你的Edge类即可。因为哈希值已经保证了无向边的唯一性，unordered_map默认的整数相等判断完全够用，不需要额外自定义相等函数。
• 示例用法：

#include <unordered_map>

std::unordered_map<__int64, Edge> edgeLookupMap;

// 添加边
void AddEdge(int v1, int v2, const Edge& edge) {
    const __int64 hash = GetEdgeHash(v1, v2);
    edgeLookupMap[hash] = edge;
}

// 查询边
Edge* FindEdge(int v1, int v2) {
    const __int64 hash = GetEdgeHash(v1, v2);
    auto it = edgeLookupMap.find(hash);
    return it != edgeLookupMap.end() ? &(it->second) : nullptr;
}

三、备选方案：用pair<int, int>作为键 #

如果觉得用64位整数不够直观，也可以直接用std::pair<int, int>作为键，但需要自定义哈希和相等判断：

#include <unordered_map>
#include <functional> // 用于std::hash

struct EdgeHash {
    size_t operator()(const std::pair<int, int>& edge) const {
        const int min_v = std::min(edge.first, edge.second);
        const int max_v = std::max(edge.first, edge.second);
        
        // 组合哈希值，这里用经典的hash_combine思路
        size_t result = std::hash<int>()(min_v);
        result ^= std::hash<int>()(max_v) + 0x9e3779b9 + (result << 6) + (result >> 2);
        return result;
    }
};

struct EdgeEqual {
    bool operator()(const std::pair<int, int>& e1, const std::pair<int, int>& e2) const {
        // 判断两条边是否是同一条无向边
        return (e1.first == e2.first && e1.second == e2.second) ||
               (e1.first == e2.second && e1.second == e2.first);
    }
};

// 使用方式
std::unordered_map<std::pair<int, int>, Edge, EdgeHash, EdgeEqual> edgeMap;

不过要注意，这个方案的性能会比64位整数键稍差一些，因为哈希计算和相等判断都多了几步操作，适合对性能要求没那么极致，但更看重代码可读性的场景。

总结 #

你一开始想到的“排序顶点生成统一哈希”是处理无向边键唯一性的标准做法，两种方案各有侧重：追求极致性能选64位整数键，追求直观可读选pair键，根据你的实际需求来就行。

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