# 哈希链表

哈希链表又称散列表，是为了加快结点查询而设计的一种数据结构。

基本原理是：把需要查询的关键字通过映射函数(散列函数)映射到相应的存储地址，然后直接访问结点。需要存储或者查询的结点一般称为 关键字 （Key value），而这个映射函数一般称为散列函数，映射到的存储地址一般称为 散列表 。

哈希链表数据结构定义：

typedef struct __hlist_node {
        struct __hlist_node     *HNDE_phndeNext;
        struct __hlist_node    **HNDE_pphndePrev;
} LW_HLIST_NODE;
typedef struct __hlist_head {
        struct __hlist_node     *HLST_phndeFirst;
} LW_HLIST_HEAD;

• HNDE_phndeNext：前向指针。
• HNDE_pphndePrev：后向双指针。
• HLST_phndeFirst：第一个结点。

哈希链表的散列函数在 libsylixos/sylixos/shell/hashlib/hashHorner.c 文件中定义。

#include <SylixOS.h>
INT  __hashHorner (CPCHAR  pcKeyword, INT  iTableSize);

• 此函数返回为散列的结果。
• 参数 pcKeyword 是需要计算散列值的关键字。
• 参数 iTableSize 是散列表大小。

函数是哈希散列函数，使用 horner 多项式。哈希表的大小最好为素数，这样散列的效果最好。本算法专为变量管理器和 shell 管理器设计，采用一阶散列表进行搜索。

SylixOS 内核中系统查找全局符号表，查找、导出符号以及 shell 系统的关键字管理等多处地方使用到哈希一级散列表确定关键字位置，再通过其他链表的操作查找具体的内容。