Java集合

集合框架 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();
//内部声明了Node类型的first和last属性，默认值为null
linkedList.add(123);
//将123封装到Node中，创建了Node对象

其中：Node定义为：体现了linkedList的双向链表的说法

private static class Node {
         E item;
         Node next;
         Node prev;

         Node(Node prev, E element, Node 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);//通过id：1和name：CC所构成的哈希值去寻找要删除的位置，结果该位置上没有值，所以删除失败
        System.out.println(hashSet);

        hashSet.add(new Person(1,"CC"));
        System.out.println(hashSet);//成功添加,通过id：1和name：CC所构成的哈希值在数组上该有的位置
        hashSet.add(new Person(1,"AA"));
        System.out.println(hashSet);//成功添加，在p1的下方，虽然他和p1的哈希值相同，但是内容不一样，所以成功添加
    }
}

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( )

//遍历所有的key集：keySet()
Set keySet = hashMap.keySet();
Iterator iterator = keySet.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}
System.out.println();
//遍历所有的value集：values()
Collection values = hashMap.values();
for (Object value : values) {
    System.out.println(value);
}
System.out.println();
//遍历所有的key-value
//方式一：entrySet()
Set entrySet = hashMap.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
    Object next = iterator1.next();
    //entrySet集合的元素都是entry
    Map.Entry entry = (Map.Entry) next;
    System.out.println(entry.getKey()+"---->"+entry.getValue());
}
System.out.println();
//方式二：先获取key，在用HashMap的get(Object key)方法获取value
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 extends HashMap.Node {
    Entry before, after;//能够记录添加的元素的先后顺序
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

Java集合

Java相关栏目本月热门文章