自学嵌入式第二十六天：数据结构-哈希表、内核链表

一、哈希表

        1.提供一种可以存储和查找的数据结构，为了提高查找的速度而生；时间复杂度是(O(1)-O(logn));

        2.对需要统计的数字直接定址；

        fun(key)=存储位置；key是要存储的数据；

        fun叫哈希函数，把key值转成存储的下标；

        key可以是数可以是其他数据；

        用于存储数据的空间一般是一段连续的存储空间；

        3.哈希函数（fun）设计的要求：计算尽量快捷方便，地址尽量均匀；

        对于数字一般是求余；

        冲突：fun(key1)==fun(key2)

                线性探测，+1，+2...

                二次探测，+1，-1，+2，-2....

                随机探测，rand()

二、快速排序

        取中间值，把小于中间值的数调到左边，大于中间值的数调到右边；

        连续递归；

三、内核链表

        1.在内核中链表结点仅有两个指针，且是双向循环链表；

        2.数据域和指针域分离；链表的功能扩展能力变强

        3.container_of(tmp，per，node)

        使用container_of带参宏可以得到指向数据的指针；

        4.list_for_each_entry_safe(pos,n,head,member)

        遍历

        pos:当前要访问的数据的结构体指针，n是pos的下一个，head是链表的头结点,member是自定义的结构体中结点的变量名；

        5.head头结点不包含有效元素，head->next是链表中第一个有效数据；