go语言数据结构第九篇-哈希表（散列）

概念

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做哈希表。

实际需求

google公司的一个上机题：基于哈希表的员工管理系统

有一个公司，当有新员工来报道时，要求将该员工的信息加入（id，名字），当输入该员工的id时，要求查找到该员工的所有信息。

要求：（1）不适用数据库，尽量节省内存，速度越快越好=>哈希表

           （2）添加时，保证按照员工的id从低到高插入

思路分析：

（1）使用链表来实现哈希表，该链表不带表头（即，链表的第一个结点就存放员工信息）

（2）示意图：

            说明：一个哈希表中存了7个链表。每个链表中包含了指向了自己的员工链表的头指针。每个员工链表的结点都是结构体，存储了id，名字。

         那么id该放入哪个链表中呢？使用散列函数，如散列函数为：key  =  id % 链表个数 。

        假设id=21，链表个数为7。则21%7=0，key就=0，这个id就放入LinkArr[0]的 链表中。再假设id=8，则8%7=1，key就=1，这个id就放入LinkArr[1]的链表中。

      当查询时id=28的员工信息时，得出key =  28%链表个数7 = 0，那么直接就在LinkArr[0]这个链表中查询就好了，搜索查询速度快了7倍。若使用10个链表，那就快10倍。链表个数越多，速度越快，但同时占用的空间就越大了。

代码实现：