目录
一.List接口
二.Set接口
三.Set接口，判断元素是否重复的原理:
四.contains方法,判断是否包含某一个元素
List接口的特点
* a.有下标 * b.有序的(有序不是自然顺序,不是123,abc,有序指的是存和取的顺序一致) * c.可重复实现类:ArrayList,LinkedList,Vector * ArrayList:底层采用可扩容（50%）数组结构,查询快,增删慢，线程不安全 * LinkedList:底层采用链表结构,查询慢,增删快 * Vector:底层采用扩容（100%）数组结构,查询快,增删慢，线程安全List结构中具有的方法: * 增: add(E e);add(int index,E e); * 删: remove(Object obj);remove(int index); * 改: set(int index,E e); * 查: get(int index); * 其他: * size(),clear(),contains(Object obj),toArray() * iterator();isEmpty()实现类的方法: * 1.ArrayList:方法基本和List中定义的一模一样 * 2.LinkedList:除了和List接口中一样的方法之外 * LinkedList提供了大量首位操作的方法 * 第一组: * void addFirst(E e); * void addLast(E e); * 第二组: * E removeFirst();//删除首个元素,返回被删除的元素 * E removeLast();//删除尾部元素,返回被删除的元素 * 第三组: * E getFirst(); * E getLast(); * 第四组: * E pop();//弹出,删除集合中的某一个元素,和 removeFirst功能是一样的 * void push(E e);//推入,把一个元素添加到集合中, 和addFist功能是一样的
Set接口的特点: * a.无下标 * b.无序的(无序指的是存和取的顺序不一定一致,LinkedHashSet和TreeSet除外) * c.不可重复实现类:HashSet,LinkedHashSet,TreeSet（红黑树的有序结构） * HashSet:底层采用哈希表结构,查询快,增删快,无序的，线程不安全
ps：HashTable是线程安全的。 * LinkedHashSet:底层采用 链表+哈希表,查询快,增删快；对元素的访问和添加元素来说是有序的
ps：保证了加入和访问元素的顺序，类似于LRU缓存。
* TreeSet:底层采用红黑树，保证了元素的有序性。
ps：使用了Set的子接口SortedSet/NavigableSet。TreeSet进行了实现。Set接口中的特有方法: 没有,和父接口Collection基本一模一样实现类: * HashSet和LinkedHashSet中的方法基本和Set接口一模一样
1.先判断 新元素的哈希值 和 所有旧元素的哈希值是否相同 * 如果都不相同,直接判断不重复,添加 * 2.再调用 新元素 和 哈希值相同的旧元素的equals方法 * 如果返回是true 判定重复元素 ,不添加 * 如果返回是false 判定不重复,添加
判断原理：
HashSet通过hashCode值来确定元素在内存中的位置。一个hashCode位置上可以存放多个元素形成一个链表。
ps：Java8对链表进行了改进，当元素超过8，把链表转化为红黑树，否则就是单纯的链表。O(N)--O(logN)！
ps：因为链表查找的平均复杂度为O(N/2)，红黑树的平均查找长度为O(logN)。
总结: * 只有哈希值相同,并且equals返回true,才判定重复
* 利用这种判断方式（hashcode+equals），很好的解决了哈希冲突的问题，防止误判。
使用HashSet存储自定义元素(Dog对象)结论: * 如果我们自定义了类 要使用HashSet存储 * 如何保证元素的唯一性: * 必须重写自定义类的两个方法,hashCode和equals定义一个标准的类: * 1.封装(private+get/set) * 2.构造(无参+全参) * 3.toString(快速打印对象信息) * 4.hashCode和equals(保证元素使用哈希表结构存储时的唯一性)
ArrayList的contains方法: * names.contains("abc");//判断 names集合中是否包含 "abc" * 只比较 equals的返回值,如果某一个元素和要判断的元素equals方法true,那么就是包含该元素HashSet的contains方法:原理和add方法 * set.contains("abc"); * 先判断哈希值 * 再使用equals方法 * 只有旧元素和判断的元素 的哈希值相同 并且 euqals方法true 才判定包含
