一、哈希表
哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
优缺点：
数组的特点是：寻址容易，插入和删除困难；
链表的特点是：寻址困难，插入和删除容易
链表的特点是：查找的时间复杂度为O（1）(不考虑冲突)，它是基于数组的，数组创建后难于扩展
构造哈希函数
1、直接定址法
取关键字的某个线性函数值为散列地址。f(key) = a × key + b
2、除留余数法
f( key ) = key mod p ( p ≤ m )（若散列表表长为m，通常p为小于或等于表长（最好接近m)的最小质数）
处理哈希冲突:
1、开放定址法
线性探测法：f(key) = key mod m（m为表长），找不到就key+1 mod m，指导找到为止。
二次探测法：fi(key) = (f(key)+di) MOD m (di = 12, -12, 22, -22,……, q2, -q2, q <= m/2)
随机探测法：在冲突时，对于位移量 di 采用随机函数计算得到，我们称之为随机探测法。（伪随机数，如果我们设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，我们在査找时，用同样的随机种子，它每次得到的数列是相同的）
2、链地址法（拉链法）
二、链表
链式存储结构就是两个相邻的元素在内存中可能不是相邻的，每一个元素都有一个指针域，指针域一般是存储着到下一个元素的指针。这种存储方式的优点是插入和删除的时间复杂度为O(1)，不会浪费太多内存，添加元素的时候才会申请内存，删除元素会释放内存，。缺点是访问的时间复杂度最坏为O(n)，关于查找的算法很少，一般只能遍历，这样时间复杂度也是线性（O(n)）的了,频繁的申请和释放内存也会消耗时间。
1、单向链表
链表中最简单的一种是单向链表，每个元素包含两个域，值域和指针域，我们把这样的元素称之为节点。每个节点的指针域内有一个指针，指向下一个节点，而最后一个节点则指向一个空值。
2、双向链表
双向链表的指针域有两个指针，每个数据结点分别指向直接后继和直接前驱。
3、循环链表
循环链表就是让链表的最后一个节点指向第一个节点，这样就形成了一个圆环，可以循环遍历。（单向循环链表,双向循环链表）
