集合框架
Collection接口：单列集合，用来存储一个一个的对象
List接口：存储有序的可重复的数组 —>“动态”数组
常用方法
- 增：add(Object obj)
- 删：remove(int index) / remove(Object obj)
- 改：set(int index, Object ele)
- 差：get(int index)
- 插入：add(int index,Object ele)
- 长度：size()
- 遍历：Iterator迭代器方式、增强for循环、普通的循环
ArrayList、LinkerList、Vector
ArrayList的源码分析
| JDK7 | JDK8 | |
|---|
| 构造器 | 实例化即开辟数组长度为10的内存空间 | 实例化时不开辟内存空间 | | add()方法 | 直接添加 | 第一次调用add方法时，开辟数组长度为10的内存空间 |
如果调用add()方法时，底层elementData数组容量不够，则扩容：默认情况下，扩容为原来的1.5倍，同时将原有数组中的数据复制到新的数组中。
建议使用有参构造器指定ArrayList（int capacity）的容量。
LinkedList的源码分析
LinkedList linkedList = new LinkedList();
linkedList.add(123);
其中：Node定义为：体现了LinkedList的双向链表的说法
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Vector的源码分析
jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组，在扩容方面，默认扩容为原来的数组长度的2倍
Set接口：存储无序的、不可重复的数据 —>高中讲的“集合”
- 无序性，不等于随机性
- 不可重复性
HashSet、LinkerHashSet、TreeSet
Set两道面试题
题目1：在List内去除重复数字值，要求尽量简单
public List duplicateList(List list) {
HashSet set = new HashSet();
set.addAll(list);
return new ArrayList(set);
}
@Test
public void test19() {
List list = new ArrayList();
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(2));
list.add(new Integer(4));
list.add(new Integer(4));
List list2 = duplicateList(list);
for (Object integer : list2) {
System.out.println(integer);
}
}
基于Set接口存储的是无序的、不可重复的数据，那么咱们可以把带有重复数据的list传入set中，相当于进行了一次过滤操作。
这道题目对list添加的都是Integer类型的元素。但如果添加的是 自定义的类所造的对象 并且还要去除重复的内容，除了要重写equals()方法，还应重写HashCode()方法。
因为：虽然咱们把元素添加到list中了，好像只需要重写equals()方法。但在调用duplicateList()方法时，里面还调用了set的addAll()方法，又因为向Set（主要指：HashSet、LinkedHashSet）中添加数据，其所在的类一定要重写hashCode()方法和equals()方法，所以要重写两个方法。
题目2：以下代码的输出结果
public class HashSetTest {
@Test
public void test1(){
HashSet hashSet = new HashSet();
Person p1 = new Person(1, "AA");
Person p2 = new Person(2, "BB");
hashSet.add(p1);
hashSet.add(p2);
System.out.println(hashSet);
p1.name = "CC";
hashSet.remove(p1);
System.out.println(hashSet);
hashSet.add(new Person(1,"CC"));
System.out.println(hashSet);
hashSet.add(new Person(1,"AA"));
System.out.println(hashSet);
}
}
HashSet讲解：底层为数组+链表的结构
存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值添加，体现了无序性。
添加的元素按照eauals()判断，返回值为true则不能添加，体现了不可重复性。
添加元素的过程：
我们向HashSet中添加元素a，首先调用a所在类的hashCode()，计算a的哈希值，此哈希值接着通过某种算法算出在HashSet数组中的存放位置（即为索引位置），判断数组此位置上是否已有元素：
- 若无元素，则 a 添加成功。
- 若有元素（或以链表形式存在的多个元素），则比较 a 与 b 的 hash 值：
- 若不相同，则 a 添加成功。
- 若相同，则调用 a 所在类的 equals()， 返回 true，a添加失败。 返回 false，a添加成功。
jdk7：元素a放到数组中，指向原来的元素
jdk8：原来的元素在数组中，指向元素a
总结：七上八下
LinkedHashSet讲解
作为HashSet的子类，LinkedHashSet每个数据添加了两个引用（双向链表），记录此数据的前一个数据和后一个数据。
遍历其内部数据时，可以按照添加的顺序来遍历。对于频繁的遍历操作，这个子类的效率高于他的父类。
TreeSet讲解
-
向TreeSet中添加的数据，要求是相同类的对象。 -
两种排序方式：自然排序（自定类实现Comparable接口） ? 定制排序（Comparator） TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ;
}
throw new RuntimeException("");
}
Map接口：双列集合，用来存储一对（key - value）一对的数据 —> 高中函数 y = f（x）
Map的结构理解：
- Map中的key：可以无序的、不可重复的，使用Set存储所有key ----->所在的类必须要重新equals()和hashCode()方法 因为key必须不可重复 （以HashMap为例）
- Map中的value：无序的、可重复的，使用Collection存储所有value ------>value所在的类要重写equals（）方法
- 一个键值对：key-value 构成了一个Entry对象。
- Map中的Entry:无序的、不可重复的，使用Set存储所有的Entry
Map的常用方法：
-
添加、删除、修改操作： Object put(Object key , Object value) void putAll(Map m) Object remove(Object key) void clear( ) -
元素查询的操作： Object get(Object key) boolean containsKey(Object key) boolean containsValue(Object value) int size( ) boolean isEmpty( ) boolean equals(Object obj) -
元视图操作的方法： Set keySet( ) Collection values( ) Set entrySet( )
Set keySet = hashMap.keySet();
Iterator iterator = keySet.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
System.out.println();
Collection values = hashMap.values();
for (Object value : values) {
System.out.println(value);
}
System.out.println();
Set entrySet = hashMap.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object next = iterator1.next();
Map.Entry entry = (Map.Entry) next;
System.out.println(entry.getKey()+"---->"+entry.getValue());
}
System.out.println();
Set set = hashMap.keySet();
Iterator iterator2 = set.iterator();
while (iterator2.hasNext()){
Object key = iterator2.next();
Object value = hashMap.get(key);
System.out.println(key+"--------"+value);
}
-
总结
- 添加：put(Object key, Object value)
- 删除：remove(Object key)
- 修改：put(Object key, Object value)
- 查询：get(Object key)
- 长度：size()
- 遍历： keySet( ) / values( ) / entrySet( )
HashMap、LinkedHashMap、TreeMap、Hashtable、Properties
HashMap的底层：数组+链表+红黑树
-
jdk7底层实现原理 HashMap map=new HashMap（）；
在实例化以后，底层创建了长度是16的一维数组，Entry[ ] table.
… 可能已经执行过多次put…
map.put(key1,value1):
首先，调用key1所在类的hashCode（） 计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置
如果此位置的数据为空，此时key1-value1 添加成功-------->情况1
如果此位置上的数据不为空，（意味着此位置上存在一个或多个数据（以链表形式存在）），比较key1和已经存在的一个或多个数据的哈希值：
如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。-------->情况2
如果key1的哈希值与已经存在的数据（key2-value2）的哈希值相同，那么此时继续比较：调用key1所在类的equals方法，比较：
如果equals（） 返回false ：key1-value1添加成功-------->情况3
如果equals（） 返回true ：key1-value1 使用value1替换key2的value值
补充：关于情况2和情况3：此时key1-value1 和原来的数据以链表的方式存储
在不断的添加过程中，会涉及到扩容问题，当超出临界值时（且要存放的位置为空），扩容。 默认的扩容方式为原来容量的2倍，并将原来的数据复制过来。
-
JDK8 相比较于JDK7在底层实现方面的不同：
-
new HashMap(): 底层没有创建长度为16的数组 -
JDK8 底层的数组是：Node[]，而非Entry[] -
首次调用put(）方法时，底层创建长度为16的数组 -
jdk7底层结构只有：数组+链表。jdk8中底层结构：数组+链表+红黑树
当数组的某个索引位置上元素以链表形式存在的数据个数>8 且当前数组的长度>64,此时索引位置上的所有数据改为红黑树存储(核心修改)为了遍历快，方便查找 DEFAULT_INITIAL_CAPACITY: HashMap的默认容量为16
DEFAULT_LOAD_FACTOR:HashMap的默认加载因子:0.75
threshold:扩容的临界值，=容量填充因子（160.15=12）
TREEIF_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树：8
MIN_TREEIF_CAPACITY:桶中的Node被树化时最小的hash表容量:64
LinkedHashMap的底层实现原理
源码中：
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
|