目录数组
一.List接口缓存
二.Set接口安全
List接口的特色 code
* 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缓存。rem
* 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 才断定包含