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

在基本的数据结构中，数组的查询效率最高，可以通过下标实现随机查找。而哈希表本质就是一个数组，通过对数组进行再加工，成了一种新的数据结构，有了自己的特点，然后就自立门户，叫散列表。
一般实现哈希表我们可以采用两种方式：

  1. 数组+链表
  2. 数组+二叉树

一个常见的列子

为了查找电话簿里面某人的号码，可以创建一个按照人名首字母排序的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为w的表中查找 “王”姓的电话号码，显然比直接查找就要快得多。这里使用的是人名作为关键字，取首字母这个例子中散列函数就是F(x)，存放首字母的表对应散列表。

image.png
如上图，假设定一个散列函数(一个规则)F(x)，作用是把数据的id分类，怎么分呢？我建一个大小16的数组，数组里面装链表，然后把这些数据的 id%16。得到多少就去对应下标的数组元素里面，插入数据到链表里面。
这样当要通过id查找某个数据时，先id%16，然后去对应的下标的数组里面进行查找，这样比直接查找全部数据效率成倍的提高。

数组+链表实现哈希表

先创建一个链表。创建链表看关于链表的文章

这里是哈希表的代码

直白的说哈希表就链表用来存储数据，而数组则管理这些链表，每次查找，添加，删除等操作，都是对哈希表进行，哈希表根据散列函数算出这条数据在哪条链表，然后在调用该条链表执行对应操作。

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  5. namespace ConsoleApp1
  6. {
  7.     public class HashTable
  8.     {
  9.         private SingleLinkList[] linklistarray;//用来存放链表
  10.         int size;//链表个数
  12.         //这个数组管理size条链表
  13.         public HashTable(int size)
  14.         {
  15.             this.size = size;
  16.             //初始化链表数组linklistarray
  17.             linklistarray = new SingleLinkList[size];
  18.             for(int i = 0; i < size; i++)
  19.             {
  20.                 linklistarray[i] = new SingleLinkList();
  21.             }
  22.         }
  24.         //添加
  25.         public void add(LinkNode node)
  26.         {
  27.             //根据node.index分配要添加到哪条链表
  28.             //通过自定义的散列函数得到对应链表的在数组中的下标
  29.             int aindex = hashFun(node.index);
  30.             //添加node到对应的链表
  31.             linklistarray[aindex].AddLast(node);
  32.         }
  34.         //遍历所有链表
  35.         public void list()
  36.         {
  37.             for(int i = 0; i < size; i++)
  38.             {
  39.                 linklistarray[i].Show();
  40.             }
  41.         }
  43.         //边写一个散列函数，使用一个简单的取模法
  44.         public int hashFun(int index)
  45.         {
  46.             return index % size;
  47.         }
  49.         //根据index查找数据
  50.         public void findNode(int index)
  51.         {
  52.             //根据散列函数得到这个index在哪条链表，直接查找对应的链表即可
  53.             LinkNode node = linklistarray[hashFun(index)].Select(index);
  54.             Console.WriteLine(node.index+" "+node.str); ;
  55.         }
  56.     }
  57. }