已知T:Borrow<Q>，如何使Rc<T>实现Borrow<Q>以支持HashMap泛型查询？

首先给出原定义的结构体：

use std::collections::HashMap;
use std::rc::Rc;
use std::hash::Hash;

pub struct Container<T: Ord + Hash> {
    contents: Vec<Rc<T>>,
    index: HashMap<Rc<T>, usize>,
}

初始可用的contains方法：

impl<T: Ord + Hash> Container<T> {
    pub fn contains(&self, val: &T) -> bool {
        self.index.contains_key(val)
    }
}

当尝试泛化方法以支持T的借用类型（例如Container<String>接受&str参数）时，修改后的代码无法编译——因为即使T: Borrow<Q>，Rc<T>也没有实现Borrow<Q>，无法直接传入&Q调用contains_key。以下是两种可行的解决方案：

方案1：线性遍历查询（简单直接，适用于小数据集） #

调整泛型约束，通过遍历HashMap的keys匹配目标值：

impl<T: Ord + Hash> Container<T> {
    pub fn contains<Q>(&self, val: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Hash + Ord + ?Sized + PartialEq,
    {
        self.index.keys().any(|rc_val| rc_val.borrow().borrow() == val)
    }
}

利用Rc<T>实现的Borrow<T>特性，先将Rc<T>转为&T，再通过T: Borrow<Q>转为&Q后与参数比较。缺点是查询时间复杂度为O(n)，无法利用HashMap的O(1)哈希查找优势。

方案2：自定义代理类型实现O(1)查询（高效，适用于大数据集） #

定义辅助代理类型，模拟Rc<T>的哈希与相等性判断，从而直接使用HashMap的contains_key方法：

use std::hash::{Hash, Hasher};

// 包装查询参数的代理类型
struct KeyRef<'a, Q: ?Sized>(&'a Q);

// 让代理类型复用Q的哈希逻辑
impl<'a, Q: Hash + ?Sized> Hash for KeyRef<'a, Q> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.hash(state);
    }
}

// 实现代理类型与Rc<T>的相等性判断
impl<'a, T, Q: ?Sized> PartialEq<Rc<T>> for KeyRef<'a, Q>
where
    T: Borrow<Q>,
    Q: PartialEq<T>,
{
    fn eq(&self, other: &Rc<T>) -> bool {
        self.0 == other.borrow()
    }
}

impl<T: Ord + Hash> Container<T> {
    pub fn contains<Q>(&self, val: &Q) -> bool
    where
        T: Borrow<Q>,
        Q: Hash + Ord + ?Sized + PartialEq<T>,
    {
        self.index.contains_key(&KeyRef(val))
    }
}

这种方法通过代理类型让HashMap识别&Q参数，保持了O(1)的查询效率，缺点是需要额外定义辅助类型。

补充说明 #

原代码编译失败的核心原因是：HashMap的contains_key要求键类型K（此处为Rc<T>）必须实现Borrow<Q>，而Rust不会自动链式推导Rc<T>: Borrow<Q>——即使T: Borrow<Q>。上述两种方案分别从遍历匹配和代理类型的角度解决了这一约束问题。

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