散列表
1 前言
散列表(hash table)的出现是为了提高存储数据的访问速度，当数据采用数组或者链表进行存储时，要查找一个元素必须进行遍历(当然采用其他技术如时无需遍历)，当数据量大时耗时巨大；而散列表根据元素的
key可快速计算出元素所在位置，无需进行遍历，进而大大提高了数据的访问速度。
散列表的元素以键值(key-value)的形式存储。一般会有一块空间用于存储散列表的数据元素，基于元素的key根据一定的规则计算出该元素应该存放的位置并进行存储；因为关键字为key的元素所在的位置可以通过计算快速计算得到，因此可以实现快速访问。
2 直接寻址表
假设数据元素的关键字key的值取自全域*U={0, 1, 2, ..., m-1}，在直接寻址表(direct-address table)中一般会有一个大小为m的数组，以保证任意元素在直接寻址表中都会有一个位置(或成为槽slot)。在直接寻址表中，数组的下标即为元素的key，因此可根据key快速定位数组中的元素，且对所有的数据元素查找时间恒为O(1)*。
直接寻址表原理简单，实现也不复杂，但当key的全域*U很大但实际上需要存储的数据元素不多时，会造成空间的浪费：比如全域U的取值范围为0 ~ 9999，但数据元素的个数只有100个，根据直接寻址表的套路，其会申请一个大小为10000的数组，在这种情况下，数组的9900个元素空间就浪费了。因而直接寻址表比较适合全域U*范围比较小的情况。
***Note:***直接寻址表并不是散列表的一种，即直接寻址表和散列表是并列关系而非从属关系(有待考证)。
3 散列表
3.1 描述
由于直接寻址表存在以下几个问题：1)当key的全域*U的取值范围0 ~ m很大时，要存储一张大小为m的直接寻址表T可能不切实际；2)待存储的元素个数k可能不多，而key的全域U*的取值范围0 ~ m可能很大，这种情况下采用直接寻址表的方式存储性价比低，因为会浪费大量的存储空间。
相对于直接寻址表，散列表：1)多了一个散列函数(hash function)h(x)，散列函数以元素的key为输入，输出元素存放位置；2)直接寻址表把具有关键字k的元素存放在槽k中，而散列表把它存放在h(k)中，即散列表通过散列函数h(x)把元素映射到散列表*T[0 1, 2 ..., n-1]的各个槽(slot)中，因为散列表的映射位置是根据映射函数h(x)计算的，因而散列表的大小n可比全域U的大小m小得多，而直接寻址表的大小必须和全域U*的大小一样大。
散列表的大小n比*U*的大小m要小，把m个数存入n个槽中(n<=m)，那必然存在2个或多个元素映射到同一个槽中，这就产生了冲突(collision)，因此散列表需要有额外的方式处理冲突，主要有2种：链接法(chaining)和开放寻址法(open addressing)。
3.2 处理冲突
3.2.1 链接法
3.2.1.1 描述
链接法中散列表存储的是一个指向某个链表的指针，当产生冲突时，直接把数据元素追加到链表的末尾。
3.2.1.2 性能分析
看不懂《算法导论》里写的意思，TBC.