集合体系与源码分析

1. 集合类存储的是方法的引用，不存储对象本身
2. 集合分为两大类
   1. collection list、set、queue
   2. map

1. 特征：元素可以重复
2. ArrayList 基于数组实现，数组的特点是具有索引，随机存取性能好，但是删除、插入涉及到数据移位，性能低
3. Vector ArrayList的线程安全版本。ArrayList扩容0.5倍，vecto扩容1倍
4. LinkedList 基于双向链表实现 。。

1. 特征：元素不可以重复
2. 判断元素需要用hashcode和equals方法比较 为什么？
   1. hashcode判断hash值是否相同——第一层判断
   2. equals比较key值内容——第二层判断

1. 除了map以外的集合都可以使用迭代器

1. comparable:可比较的实现,该接口表示：这个类的实例可以比较大小，可以进行自然排序,定义了默认的比较规则,其实现类需要实现compareTo()方法,compareTo()方法返回正数表示大，负数表示小0表示相等
2. Comparator接口:比较工具接口用于定义临时比较规则，而不是默认比较规则,其实现类需要实现compare()方法,Comparable和Comparator都是Java集合框架的成员

1. HashMap构造器
   1. HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
   2. HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
   3. HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。
   4. HashMap(Map<? extends K, ? extends V> m)：传入一个map以构造一个新的map，使用默认加载因子（0.75）。
2. 存值（Put）
   1. ① 判断当前桶是否为空，空的就需要初始化数组（resize（） 中会判断是否进行初始化）。
   2. ② 根据当前key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
   3. ③ 如果当前桶有值（Hash 冲突），那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key 是否相等，相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。
   4. ④ 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
   5. ⑤ 如果是个链表，就需要将当前的key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
   6. ⑥ 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
   7. ⑦ 如果在遍历过程中找到key 相同时直接退出遍历。
   8. ⑧ 如果e != null 就相当于存在相同的 key,那就需要将值覆盖。
   9. ⑨ 最后判断是否需要进行扩容。
3. 取值（Get）
   1. l 首先将key hash 之后取得所定位的桶。
   2. l 如果桶为空则直接返回null 。
   3. l 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
   4. l 如果第一个不匹配，则判断它的下一个是红黑树还是链表。
   5. l 红黑树就按照树的查找方式返回值。
   6. l 不然就按照链表的方式遍历匹配返回值。

什么是Hash冲突？

1. 如果通过hash运算计算出来的index值与数组中某个index值相同，说明此存储地址已经被其他元素所占有，这种现象称之为hash碰撞或hash冲突。 HashMap底层采用数组加链表加红黑树的方式，当存储地址index相同的时候，判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。

如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果相同，这时就是产生了hash冲突。
Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。
系统只能必须按顺序遍历每个Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。