链锁哈希：HashLink —— Rust 有序之钥，缓存诗章

“哈希如星辰散布，链表如银链串联。
一触即得，一序永存。
HashLink，Rust 之优雅容器，
序与速并舞，缓存梦成真。”

前言：为何选择 HashLink？

在 Rust 的世界里，std::collections::HashMap 是高效查找的王者，O(1) 平均时间复杂度令人叹服。但它有一个“隐痛”：迭代顺序不可预测，插入顺序如风中落叶，难以掌控。

HashLink 应运而生！它是 linked-hash-map 的现代化重铸之作，基于高性能 hashbrown 哈希表 + 双向链表，提供：

• LinkedHashMap：保持插入顺序的哈希映射。
• LinkedHashSet：保持插入顺序的哈希集合。
• LruCache：LRU（最近最少使用）缓存，一键搞定热门场景。

适用场景：

• LRU 缓存（Web 服务器、数据库查询）。
• 有序配置解析（TOML/JSON，保持字段顺序）。
• 日志/事件缓冲（FIFO + 快速查找）。
• 游戏状态机（有序键值对）。

性能承诺：继承 hashbrown 的极速（媲美 std::HashMap），内存低开销，raw entry API 零额外哈希。

由浅入深：我们从零基础起步，渐入实战巅峰。准备好 Rust 环境，一起诗意 coding！

第一章：理论基石 —— 哈希与链表的浪漫交响

1.1 HashMap 的“乱序之痛”

std::HashMap: 键 → 值 (O(1) 查找，但 iter() 顺序随机)

1.2 HashLink 的“双魂合一”

核心结构：
┌─────────────────┐
│   hashbrown     │  ← O(1) 查找/插入/删除
│   HashMap<K,V>  │
└─────────┬───────┘
          │ (指针/索引)
          ▼
┌─────────────────┐
│ Doubly Linked   │  ← 保持插入/MRU 顺序
│   List (Node)   │
└─────────────────┘

• 插入：哈希表存 (K,V) + 链表尾部新节点。
• 访问：get_mut() 自动移到尾部（LRU 友好）。
• 删除：原子更新两者。
• 迭代：按链表顺序遍历。

1.3 魔法：RawEntryMut API

传统：entry(key).or_insert() → 两次哈希（from_key + insert）。 HashLink：raw_entry_mut().from_key(&key) → 一次哈希，击中即 to_back()！

时间复杂度：

操作	HashMap	HashLink
插入/查找	O(1)	O(1)
迭代	O(n) 乱序	O(n) 有序
LRU 命中	-	O(1) 无重哈希

安全：纯 Rust，Miri/ sanitizer 测试，unsafe 仅限内部链表。

第二章：环境搭建 —— 一键入梦

Cargo.toml：

[dependencies]
hashlink = "0.8"  # 最新版，详见 crates.io

cargo new hashlink_demo
cd hashlink_demo
# 编辑 Cargo.toml，运行：
cargo build
cargo run

平台支持：Linux/macOS/Windows/Wasm，零依赖（仅 hashbrown）。

第三章：基础入门 —— 初尝甜头

3.1 LinkedHashMap：有序键值天堂

use hashlink::LinkedHashMap;

fn main() {
    let mut map = LinkedHashMap::new();
    map.insert("apple", 1);
    map.insert("banana", 2);
    map.insert("apple", 3);  // 更新值，顺序不变

    // 迭代：严格插入顺序！
    for (k, v) in map.iter() {
        println!("{}: {}", k, v);  // apple:3, banana:2
    }

    // 获取 & 自动移尾（LRU 准备）
    if let Some(val) = map.get_mut("apple") {
        *val += 10;  // apple 移到尾
    }
    println!("{:?}", map.keys());  // ["banana", "apple"]
}

3.2 LinkedHashSet：唯一有序集

use hashlink::LinkedHashSet;

fn main() {
    let mut set: LinkedHashSet<String> = ["a", "b", "a"].iter().cloned().collect();
    println!("{:?}", set);  // ["a", "b"] —— 去重，保持首次插入序
}

第四章：LRU 缓存实战 —— 核心杀手锏

4.1 简易 LRU（容量控制）

use hashlink::LruCache;

fn main() {
    let mut cache: LruCache<String, i32> = LruCache::new(3);  // 容量 3
    cache.put("a".to_string(), 1);
    cache.put("b".to_string(), 2);
    cache.put("c".to_string(), 3);

    println!("{:?}", cache.get(&"a".to_string()));  // Some(1)，a 移尾

    cache.put("d".to_string(), 4);  // b 被逐（最旧）
    println!("{:?}", cache.keys());  // ["c", "a", "d"]
}

4.2 高效 RawEntryMut —— 零重哈希 神技

use hashlink::{LinkedHashMap, RawEntryMut};

fn main() {
    let mut lru = LinkedHashMap::new();
    let key = "foo".to_string();

    // 神操作：命中 → to_back()，未命中 → insert，一次哈希！
    let val = lru.raw_entry_mut()
        .from_key(&key)
        .or_insert_with(|| (key.clone(), 42));

    println!("Val: {}, Order preserved!", val.1);
}

or_insert_with 闭包：懒计算，miss 时才执行！

第五章：高级实战 —— 项目级应用

5.1 完整项目：Web 缓存代理（Actix-Web + HashLink）

Cargo.toml 添加：

[dependencies]
actix-web = "4"
tokio = { version = "1", features = ["full"] }

src/main.rs：

use actix_web::{get, web, App, HttpResponse, HttpServer, Result};
use hashlink::LruCache;
use std::sync::Arc;
use tokio::sync::Mutex;

struct AppState {
    cache: Arc<Mutex<LruCache<String, String>>>,
}

#[get("/cache/{key}")]
async fn get_cache(
    path: web::Path<String>,
    state: web::Data<AppState>,
) -> Result<HttpResponse> {
    let key = path.into_inner();
    let mut cache = state.cache.lock().await;

    let value = cache.raw_entry_mut()
        .from_key(&key)
        .or_insert_with(|| {
            println!("Cache MISS: {}", key);
            (key.clone(), format!("Computed: {}", key))  // 模拟计算
        })
        .1
        .clone();

    Ok(HttpResponse::Ok().body(value))
}

#[actix_web::main]
async fn main() -> std::io::Result<()> {
    let cache = LruCache::new(100);
    let state = web::Data::new(AppState {
        cache: Arc::new(Mutex::new(cache)),
    });

    HttpServer::new(move || {
        App::new()
            .app_data(state.clone())
            .service(get_cache)
    })
    .bind("127.0.0.1:8080")?
    .run()
    .await
}

运行：cargo run

• curl http://localhost:8080/cache/foo → MISS，缓存。
• 重复 → HIT，O(1) + 移尾！

扩展：加 put API，序列化（serde 支持）。

5.2 配置文件有序解析

use hashlink::LinkedHashMap;
use serde::{Deserialize, Serialize};

#[derive(Serialize, Deserialize)]
struct Config(LinkedHashMap<String, i32>);

fn main() {
    let config_toml = r#"
    [data]
    a = 1
    b = 2
    "#;
    // TOML → LinkedHashMap，保持顺序！
    // 输出：a=1, b=2
}

第六章：性能巅峰与优化

• 基准：hashlink ≈ std::HashMap，LRU 场景快 2x（无重哈希）。
• 容量预设：with_capacity(1024) 避 resize。
• no_std：default-features = false。
• 多线程：Arc<Mutex<LruCache>> 或 dashmap 替代。

第七章：常见陷阱与诗意收尾

• 陷阱：drain() 后顺序失效 —— 重建！
• 调试：peek() 查看不移尾。
• 诗意：HashLink 非容器，乃时空桥梁。序如诗行，速如闪电。

恭喜！ 你已精通。Fork 仓库，贡献 PR，共铸 Rust 传奇！

参考资料

• [官方仓库]：https://github.com/djc/hashlink
• [文档]：https://docs.rs/hashlink
• [Crates.io]：https://crates.io/crates/hashlink
• 相关：hashbrown（底层）、linked-hash-map（前身）
• 社区：Rust Forum、Reddit r/rust（搜索“hashlink lru”）

鸣谢：djc 开发者，Rust 生态之星！🌟