1. 哈希表的通俗理解

我们知道，线性链表灵活性高，扩展性强，但是查找效率低；而数组虽然查找效率高，但是扩展性，灵活性都不高。哈希表则巧妙的结合了这两种数据结构的优点，不仅插入、删除数据高效，同时查找效率也高，但是内存占用也高，相当于用空间换时间。

1.1. 类比：快递仓库

想象你在一个快递仓库工作，

• 这个仓库有100个货架（0~99）。
• 每个快递都有一个快递名。
• 有一个hash牌的编码器，专门把这些快递名编码成0~99的数字，你根据这些数字把快递放在相应的货架。

Like this：

WTF？Alice 和 Carol 都被分到了37号架，怎么办？

聪明的你在37号架上放一个“小篮子”，把所有撞到这里的快递都放一起。
查找时，只需要在篮子里翻几下。

1.2. 理解：哈希表的原理

• hash表就是这个货架，可以理解为“链表数组”。

#define TABLE_SIZE 10
struct hash_node *table[TABLE_SIZE];  // 数组，每个槽位一个指针，初始全为NULL

• 整个快递包裹，我们可以看作一个结构体。结构体成员“快递名”即为“键”，它们用来索引对应的快递；当然，结构体成员”快递里装的物品“就是“值”。

struct hash_node {
    char *key;                // 键
    char *value;              // 值
    struct hash_node *next;   // 指向下一个节点的指针
};

• 编码器呢，就是所谓的哈希函数，它会计算出一个整数，用于将“键” 映射到数组（哈希表）的某一个槽位中，也就是某个内存块啦。

• 一槽不容两键？nonono！被伟大的hash神分配在同一槽的键值会形成链表啦~

void insert(char *key, char *value)
{
    int index = hash(key) % TABLE_SIZE;  // 计算槽位
    struct hash_node *new_node = malloc(sizeof(struct hash_node));
    new_node->key = strdup(key);
    new_node->value = strdup(value);

    // 将新节点插入到链表头部
    new_node->next = table[index];   // 指向原来的第一个节点
    table[index] = new_node;         // 数组该槽位现在指向新节点
}

更直观一点

[槽位2：链表首地址]---------[槽位3：链表首地址]---------[槽位4：空]---------
	| -> 最新添加的节点         | -> 节点
	| -> 后续添加的
	| -> 首次插入的节点

上文提供的链表插入方法是首插法，链表首地址由最新添加的节点地址呈现。

2. 哈希表在linux中的应用

在 Linux 里，每个设备（比如 /dev/sda, /dev/ttyS0）都有一个编号：
设备号 = 主号 + 次号。
你可以理解为：

• 主号：设备类别（比如“硬盘类”、“串口类”）
• 次号：同类中的编号（第1个、第2个）

设备号类型定义：

typedef unsigned long long dev_t;

主次设备号可以通过以下宏操作：

MAJOR(dev_t dev); // 获取主设备号
MINOR(dev_t dev); // 获取次设备号
MKDEV(int major, int minor); // 组合成一个dev_t

• 已注册的设备号可以使用cat /proc/devices查看
• 内核是希望一个设备驱动(file_operation)可以独自占有一个主设备号和多个次设备号，而通常一个设备文件绑定一个主设备号和一个次设备号，所以设备驱动与设备文件是一对一或者一对多的关系。

内核就像一个大仓库，存着成千上万个设备。
系统要根据设备号，快速找到对应的设备结构体（里面保存操作函数、状态等信息）。

于是它用哈希表来实现：
把设备号算一算 → 得出“货架号” → 直接找到设备对应的信息结构。

1. 1. 哈希表的通俗理解
   1. 1.1. 类比：快递仓库
   2. 1.2. 理解：哈希表的原理
2. 2. 哈希表在linux中的应用