关于Java中的容器
在实际编程中经常会需要用某种工具来存储数据，通常就会很自然的想到利用数组来存储数据。但是数组的长度和数据类型必须事先确定，也无法存储更复杂的数据结构。所以 Java 提供了一组容器类来完成这个功能，其实容器本质上就是数据结构里面研究的内容，如何组织和存储数据。
集合内容太多，太复杂，这只是初级版本。后续肯定是要不断扩充修改，将这个笔记拆开来的。
Java 容器层次结构图如下(当然是简略版)：
_Java集合类继承层次图.png
Java 容器集合类主要分为三块，分别是 List 、Set 、Map ，所有容器都不是直接存储对象，而是直接存储对象的引用。List 底层采用的是顺序表做存储，Set 底层是直接采用的 Map 对应的容器类做存储，List 和 Set 都是单值容器。Map 则是以键值对形式组织数据，HashMap 采用散列表存储数据，TreeMap 采用红黑树存储数据。
关于 java.lang.Iterable 接口
「英文时间」：Iterable 网络释义. 可迭代的
Iterable 接口位于 java.lang 包中，它设计的目的就是为了对容器进行迭代，它内部有一个 iterator() 方法非常重要。
Iterator<T> iterator();这是接口中的抽象方法，所以实现这个接口的子类必须提供对应的实现方式。通过这种方式来保证它的实现类都必须提供 iterator() 方法返回 Iterator 迭代器对象来实现迭代、遍历容器的功能。Collection 接口的子类都可以通过 iterator() 方法返回 Iterator 对象来迭代其自身，就是因为Collection 接口继承了 Iterable 接口，所以Collection 的所有实现类都必须提供对应的 iterator() 方法的实现。这才是根本原因！
关于 java.util.Iterator 接口
「英文时间」：Iterator n. 迭代器
Iterator 接口定义了迭代器对象的功能规范，提供了boolean hasNext()和 E next()两个方法的组合来实现迭代遍历容器对象的功能。具体使用方式太简单，不做记录。
此方法返回的使用 Iterator 接口引用指向的对象其实是其对应的容器对象的一个私有内部类对象，并不是所谓的集合。回忆一下内部类对象的内存图？点这里查看内部类笔记。私有内部类对象当然能够访问其外部类对象的属性和方法，由此才能够实现一个迭代、遍历容器的功能。得到这种认知来源是自己之前阅读《数据结构与算法分析Java语言描述》一书中，自己亲自动手实现过，配合查看 JDK 源码得以验证。JDK 源码中涉及到的内容非常多，查看源码的过程一定要学会抛弃那些干扰的细节，抓住自己需要学习的主线内容。
关于 java.util.List 接口
List 接口的实现类中有几个容器类应用的非常广泛，分别是 ArrayList 、LinkedList 、Vector 、Stack 。所有实现了 List 接口的容器类都是有序可重复的，有序的意思是容器内部元素排列的先后顺序是和添加进容器中顺序一样的。List 不就是叫做顺序表嘛，当然会是有序的，理解了本质相应的知识点真的是随口就来的，并不需要去记忆。
关于 ArrayList 容器
ArrayList 底层是采用数组来存储数据的，内部实现了自动扩容的机制。查找效率高，增加、删除数据效率低(数组的操作必然会导致这种使用特点)，线程不安全。
下面是之前自己仿照 ArrayList 手动实现的 MyArrayList 容器类。
[图片上传失败...(image-6c6853-1537516189702)]
关于 LinkedList 容器
LinkedList 底层采用双向链表实现，查找效率低，插入、删除效率高，线程不安全。
下面是之前自己仿照 LinkedList 手动实现的 MyLinkedList 容器类。
[图片上传失败...(image-92790d-1537516189703)]
关于 Vector 容器
Vector 和 ArrayList 一样都是采用数组作为底层存储模型，所以和 ArrayList 其实是差不多的。但是 ArrayList 是线程不安全的， Vector 是线程安全的，线程安全就必然导致效率低下，因为要加锁嘛，加锁就不得不等待。
关于 Stack 容器
java.util.Stack 类直接继承了 java.util.Vector 类，仔细思考下什么是继承，体会下？所以可以直接利用其父类 Vector 提供的方法和存储模型来实现堆栈的这个数据结构，栈用的太广泛了，后进先出，不需要说了吧。
其实采用组合方式也可以实现这种功能，继承当然也可以。不记得在哪里看到过，说要优先使用组合方式，而不是继承，因为继承破坏了封装性。
关于 java.util.HashMap 容器
HashMap 底层数据结构采用的是散列表，早期的散列表是用的一维数组加上多个链表来实现的，自己在脑海中想想那个结构图。散列表的增删和查询效率相对而言都很高。
使用 HashMap 类的public V put(K key, V value) 方法添加元素时，会先将 key 和 value 封装到 Node 节点对象中，将其作为一个整体来存放到散列表中去，这个 Node 节点就是链表的节点啊。然后调用 key 的 hashCode() 方法获得哈希值，这个哈希值就作为一维数组的下标值，然后再根据 equals() 方法判断元素的 value 值是否相同，如果相同，就会覆盖之前的元素 value 值，不同就直接依次在后面加上去。这种内部存储方式决定了数据是无序不可重复的！
java.util.HashMap 的负载因子(一维数组中所拥有的元素个数 / 一维数组容量)默认是 0.75 ，而且数组默认容量为 16 ，这在 HashMap 源码中是以注释的形式标明了的。负载因子越大，碰撞越多，会降低效率，负载因子越小，就浪费了空间。散列表优不优秀就取决于负载因子优不优秀！其实谁不是
这里还要总结下 keySet() 和 entrySet() 方法
下面是之前自己仿照 HashSet 手动实现的 SeparatedChainingHashTable 容器类，这里并不是采用一个固定大小的一维数组，而是采用了 LinkedList 作为数组存储。
[图片上传失败...(image-cf2d44-1537516189703)]
关于 java.util.HashTable 容器
HashTable 和 HashMap 是一样的，只是它是线程安全的，效率自然低，它们的关系就类似于 ArrayList 和 Vector 的关系一样。
关于 java.util.Properties 容器
Properties 类直接继承 HashTable 类，它是专门设计来操作 .properties 文件的。它的 key 和 value通过 get/set 方法存放的都是 String 类型。点击这里查看 Properties 类笔记
关于 java.util.TreeMap 容器
TreeMap 底层采用红黑树做存储，要让自己动手实现，目前还真的是写不出来，毕竟它也属于高级数据结构的范畴了。SortedMap 接口直接继承 Map 接口， SortedMap 中有一个Comparator<?super K> comparator()的抽象方法，所以它的实现类 TreeMap 必须提供对应的Comparator 比较器对象，以完成内部排序的功能。点击此处查看 Comparable 和 Comparator 的笔记
真正实现排序的关键点就在public V put(K key, V value)方法中会调用Comparable 接口的public int compareTo(T o)方法来进行比较，再决定该如何放置新添加的元素到合适的树节点中去。
所以说添加进 TreeMap 容器中的 key 必须是实现 Comparable 接口的类的对象，否则内部就无法进行排序。所以没有实现 Comparable 接口的 key 是无法成功插入到 TreeMap 中去的。
所以 TreeMap 容器中的元素是无序不可重复，但是它是排序的。也就是因为它内部是自动排序的，所以它是无序的，而且 key 相同时，后者的 value 值会覆盖前者的 value 值。
关于 java.util.Set 接口
Set 和 Map 有着很紧密的关系。HashSet 底层就是采用了 HashMap 做底层存储，TreeSet 底层是采用的 TreeMap 作存储。它们都是采用的组合方式实现此功能！如果把 Map 中的 key 值单独拿出来，那就是 Set 容器了。Map 中是键值对合起来作为一个独立的链表的 Node 节点，Set 中的 key值就是自己作为一个独立存储单元。两者道理是一样的，所以 Map 才会有 keySet() 方法能够将所有 key 放到一个 Set 中去存储。这一块以前也自己动手实现过的，代码找不到了，可见使用同一个笔记系统做存储有多重要，而不是这里一点，那里一点。
理解了Set 和 Map 的组合关系，HashSet 与 HashMap 和TreeSet 与TreeMap的特点都是一样的，那就没啥好说的了。Set 同样是无序不可重复的，这里的不可重复意思是，当 key 的值相同时，后来者无法插入进去，Map 则是后来者覆盖前者。
