java集合框架

Java集合框架.png

tips: Stack继承自Vector，实现一个后进先出的堆栈。
Hashtable实现了Map接口。
Properties继承自Hashtable。

1. Collection中的对象元素必须覆写equals()方法，否则remove()、contains()无法使用。

2. 创建HashMap，Hashtable，HashSet集合时，hashCode() 才有用。若某个类没有覆盖hashCode()方法，当它的通过hashCode()比较两个对象时，实际上是比较两个对象是不是同一个对象。这时，等价于通过“==”去比较这两个对象，即两个对象的内存地址是否相同。判断两个元素相等的标准是两个对象通过equals()方法比较相等，并且两个对象的hashCode()方法返回值也相等。

3. LinkedList、ArrayList、Set、HashMap均可存在null元素。Hashtable不允许存在null。

4. 在Java中，集合的输出操作有四种形式：Iterator输出、ListIterator输出（双向迭代）、Enumeration输出、foreach（加强型for循环）输出。

5. 集合中不是真正存入某个对象， 而是保存的是对象的引用。

6. 属性文件，后缀就必须是*.properties。Properties的key和value都是String类型，用来读取配置文件。

7. ArrayList：数组实现，查询快，增删慢，线程不安全，轻量级；get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
   LinkedList：链表实现，增删快，查询慢。LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
   Vector：数组实现，线程安全，重量级

8. HashMap数据结构为一个链表数组。它是线程不安全的，默认初始容量和负载因子为16和0.75。hash是与2的n次方进行与运算。rehash在多线程环境下可能会导致链表环。

9. Map输出步骤
   利用entrySet()方法将Map接口数据中的数据转换为Set接口实例进行保存，此时Set接口中所使用的泛型类型为Map.Entry，而Map.Entry中的K与V的泛型类型则与Map集合定义的K与V类型相同；
   利用Set接口中的iterator()方法将Set集合转化为Iterator接口实例；
   利用Iterator接口进行迭代输出，每一次迭代取得的都是Map.Entry接口实例，而后利用此接口实例进行key与value的分离。

10. TreeSet使用红黑树(red-black tree，由TreeMap实现)确保没有重复元素。
    红黑树是平衡二叉树。保证二叉树的平衡性，使得插入，删除和查找都比较快，时间复杂度都是O(log n)。不过它没有HashMap快，HashMap的时间复杂度是O(1)。

11. LinkedHashMap、LinkedHashSet： 能保持元素的插入顺序

12. 树和图这两种数据结构在Java中如何实现?