何谓集合

• 基于数组的拓展，无长度限制。
• 列表：有序集合。链表、队列、栈。使用数组实现。
• 集：无序、数据不能重复。使用散列表实现。
• 多重集：无序、数据可重复。可通过排序转换为列表。（不知道是什么鬼，没用过）
• 数、图：略。

  列表特点（变长数组）

• 变长。在不够长的时候通过数组拷贝的方式创建新数组。
• 拷贝的方式会造成性能耗损。
• 查询欠佳。
• 查询、修改的时间复杂度为O(n)。
• 查找顺序存储的结构类型，在数据量大的情况下，依旧是从0开始，一个个的去访问。效率很低。

何谓散列表

• 又称“哈希表”，能够通过key直接访问到具体元素。通过key访问一个映射表来得到value的地址。这个映射表也称为“散列函数”或者“哈希函数”。存放记录的数组叫做“散列表”。
• 通过不同的key，可能映射到相同的地址，这种现象叫做 “碰撞” 。
• 散列表有两种用法，一种是k=v，即set。另一种即map。

哈希函数的实现

考虑因素：关键字的长度、哈希表的大小、关键字的分布情况、记录的查找频率等

• 直接寻址法：取关键字或者关键字的某个线性函数值作为散列地址。

• 数字分析法：通过对数据的分析，发现冲突较小的部分，构造散列地址。

• 取随机数法：取关键字的随机值作为散列地址。适用于关键字长度不一致的情况。

哈希函数冲突处理

对不同的key进行hash运算，可能会出现相同的结果。处理如下：

• 开放地址法： 简单地讲，也就是说，一间厕所，来了一个顾客就蹲其对应的位置，如果又来一个顾客，把厕所单间门拉开，一看里面有位童鞋正在用劲，那么怎么办？很自然的，拉另一个单间的门，看看有人不，有的话就继续找坑。当然了，一般来说，这个顾客不会按顺序一个一个地拉厕所门，而是会去拉他认为有可能没有被占用的单间的门，这可以通过闻味道，听声音来辨别，这就是寻址查找算法。

• 再哈希法：产生冲突后使用关键字的其他部分再次进行计算取址，如还是冲突则再用其它的部分hash。缺点：时间增加了。

• 链地址法：在地址上做一个链表，存储。
• 公共溢出区：建立一个公共溢出区。

散列表存储结构

• 一个好的散列设计，除了一个良好的hash函数外，还要有好的冲突处理方式。一般选择链地址法。
• 数组 + 链表

散列表的特点

• 访问速度快：通过散列函数将key指定到一个地址上，所以在访问的时候不需要一个一个查找。增删改查都很快。（！！！！存疑，hash方法到底是得到一个数组index还是内存地址）
• 需要额外的空间：散列表实际上不太可能满载；额外空间处理冲突。
• 无序。
• 可能会产生碰撞，使得散列复杂。
• 数据量大（map快满载）时，性能下降。（冲突太多，在链表中太麻烦）

散列表的适用场景

适合无序的，需要快速访问的情况。

• 缓存。
• 快速查找。判断set中是否存在某指定元素

散列表性能分析

• 如果没有冲突，通过对key进行hash寻址，完全是O(1)的效率，但是冲突在所难免。通常使用链地址法来处理冲突。碰撞之后需要遍历链表，时间复杂度为O(L)，L为链表长度。

• 当map负载很大的时候，说明大部分地址已经有值了，此时再添加元素，势必碰撞，势必走链表，于是性能下降。此时应当扩容，java的hashMap扩容因子为0.75，当负载达到75%的时候进行扩容。扩容之后进行大排版，也许之前在链表中存储，现在在数组中存储。