Java集合

Set,List,Map,Dqueqe,Queue,Stack,以及一系列常用子类，以及方法 Collection接口

Set和List的为Collection接口的两个重要实现

Collection的方法

add(obj):添加一个对象
remove(obj):删除一个对象
removeAll(Collection):可以删除多个元素，传入Collection的子类
clear():清空Collection
size():返回Collection的大小
contains():是否包含某个对象

Set

不是线程安全的

Set容器的特点:

Set里面的元素不能重复
添加的元素和取出的元素不一致
可以添加一个null

Set容器的常用方法:

Set set=new HashSet();
add(obj):添加一个对象
remove(obj):直接删除一个元素
clear():清空容器
size():容器的大小
isEmpty():判断是否为空
equal():判断两个集合是否相等，若两个集合里面的元素相等，则它们的hashCode()相等，两个集合也相等

Set接口的遍历方式

迭代器
增强for
不能使用索引的方式获取

for (Object o : set) {
    System.out.println(o);
}

Iterator iterator = set.iterator();
while (iterator.hasNext()){
     System.out.println(iterator.next());
}

HashSet

Set的一个实现接口,不需要借助子类实现

HashSet的特点:

元素不能重复
添加的元素和取出的元素不一致
可以添加一个null

常用的方法:

HashSet set=new HashSet();
add(obj):添加一个对象
remove(obj):直接删除一个元素
clear():清空容器
size():容器的大小
isEmpty():判断是否为空
equal():判断两个集合是否相等，若两个集合里面的元素相等，则它们的hashCode()相等，两个集合也相等

底层:

HashSet的底层使用HashMap实现，添加元素和删除元素也是利用map的方法实现

构造函数
public HashSet() {
    map = new HashMap<>();
}
添加元素
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

LinkedHashSet

LinkedHashSet是HashSet的子类，利用数组+双端链表实现

特点:

元素不能重复
添加的元素和取出的元素一致
可以添加一个null

常用方法:常用方法和HashSet一致

底层:底层使用LinkedHashMap实现,实现了元素的插入和取出一致

在构造LinkedHashSet时候，调用父类的HashSet的构造函数，得到LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

其他和HashSet一致

TreeSet

TreeSet是Set的一个实现子类

特点:

不允许添加null元素
元素不能重复
集合里面的元素有序，元素是排好序的

常用方法：常用方法和以上相同

底层:底层使用TreeMap实现

public TreeSet() {
    this(new TreeMap());
}

List

List实现了Collection接口,需要借助子类实现

List容器的特点；

元素可以重复
元素的放入和取出有序
可以添加null

常用方法:

add(obj);添加一个对象
remove(index):将索引对应的元素删除
size()
clear()
addAll();加入一个集合
contains();是否包含某个对象
containsAll();是否包含某个集合
isEmpty();判断集合是否为空
indexOf();返回元素的第一个索引
lastIndexOf():返回元素最后出现的索引

list遍历:

增强for
迭代器

for (Object o : list) {
    System.out.println(o);
}
Iterator iterator = list.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}

Vector

线程安全的:synchronized，其他基本和List一样，底层用数组实现

Vector扩容:

初始化集合的大小是10
public Vector() {
   this(initialCapity:10);
}

添加元素时候的代码
public synchronized boolean add(E e) {
      modCount++;
      //这里确定是否需要扩容
      ensureCapacityHelper(elementCount + 1);
      elementData[elementCount++] = e;
      return true;
}

private void ensureCapacityHelper(int minCapacity) {
    //当大于数组的长度时候，扩容
     if (minCapacity - elementData.length > 0)
          grow(minCapacity);
}

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //这里的capacityIncrement默认构造时为0，即每次扩容时增加一倍
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
}

//这里的Vector构造函数中，可以指定initialCapacity数组的初始容量，capacityIncrement这里是每次扩容的大小，若为0的话，每次扩容int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);即是加上原来数组的大小，扩容一倍
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

ArrayList

线程不安全，速度快，基本的方法相同，底层数组实现

ArrayList扩容原理:

基本和上面的Vector相同，不同点在grow, int newCapacity = oldCapacity + (oldCapacity >> 1);这里每次扩容的扩容的时候oldCapacity >> 1，这里加上原来容量的一半，既是每次扩容原来数组大小的1.5倍
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList

实现了List接口，同时实现了Queue接口(一会儿说)，底层使用链表实现

特点：

链表实现
增删效率高
查改效率低

常用方法（实现了List接口的）：

add(obj);添加一个对象
remove(index):将索引对应的元素删除
size()
clear()
addAll();加入一个集合
contains();是否包含某个对象
containsAll();是否包含某个集合
isEmpty();判断集合是否为空
indexOf();返回元素的第一个索引
lastIndexOf():返回元素最后出现的索引
addFirst():在第一个添加元素
addLast():在最后一个添加元素

Stack

Stack继承了Vector，所以所以拥有LIst的相关方法

Stack自己的常用方法:

push();往栈里push一个元素
pop();弹出栈顶元素
peek();返回栈顶元素
empty();判断栈是否为空

Queue

队列，扩展了Collecion接口，有自己的方法，LinkedList实现了该接口

Queue常用方法：

Queue queue=new LinkedList();
offer(obj):从队尾添加一个元素
poll():出队操作
peek():返回队头元素

Deque

双端队列，扩展了Queue接口，LinkedList实现了该接口

Deque常用方法:

addFirst();在头部添加元素
addLast():在尾部添加元素
getFirst():返回第一个元素
getLast():返回最后一个元素

offerFirst():在头部添加元素
offerLast():在尾部添加元素
pollFirst():删除第一个元素
pollLast():删除最后一个元素
peekFirst():返回第一个元素
peekLast():返回最后一个元素

removeFirst():删除第一个元素
removeLast():删除最后一个元素

offer():从队尾添加一个元素
poll():出队操作
peek():返回队头元素

Map

Map容器的特点:

存放的是键值对 key-value
key不允许重复，value可以重复
key和value都可以为null

Map常用的方法:

put(key,value):放入一个键值对
get(key):由key得到value,若不存在，返回null
remove():删除元素
size():返回大小
clear():清空

Set keySet():返回key的集合

Map中的key-value存放在Map的内部类Entry中，这个函数返回（entrySet）key-value的集合
Set> entrySet()

Map的遍历方式:

增强for(keySet)
Map.entrySet()

for (Object o : map.keySet()) {
    System.out.println("key="+o+",value="+map.get(o));
}

for (Object o : map.entrySet()) {
    Map.Entry res = (Map.Entry)o;
    System.out.println("key="+res.getKey()+",value="+res.getValue());
}

HashMap

map的重要实现子类

特点:

存放的是键值对 key-value
key不允许重复，value可以重复
key和value都可以为null

底层实现:数组+链表

HashMap的扩容机制:

1、HashMap底层维护了一个Node类型的数组table,默认为null
2、当创建对象时，将加载因子(loadfactor)初始化为0.75
3、当添加key-value时候，通过key的hash指定得到在talbe的索引。然后判断索引处是否有元素，若没有的话，直接添加，若该处有元素，若加入的key和该位置key相等，直接替换val。若不相等得话需要判断是树结构还是链表结构，做出相应处理，如果添加的时候发现容量不够，则需要扩容
4、若第一次添加，则需要扩容table的容量为16，临界值(threshold)为12 16*0.75
5、以后扩容，需要扩容table容量为原来的2倍(32),临界值为原来的2倍(24),依此类推
6、java8中，如果一条链表的个数超过TREEIFY_THRESHOLD(默认为8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认为64)，则会进行树化(红黑树)

底层维护的table表
transient Node[] table;
//装载因子0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
put的调用
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
存放元素时
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    //如果底层的table 数组为null, 或者 length =0 , 就扩容到16
        n = (tab = resize()).length;
     //取出hash值对应的table的索引位置的Node, 如果为null, 就直接把加入的k-v
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            //如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
            //调用红黑树的putTreeVal加入元素
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
        	//如果结点后面是链表，就循环比较
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                //如果找到最后一个结点，把它加载最后一个结点
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    //加入后，判断当前链表的个数，是否已经到8个，到8个，后
                    //就调用 treeifyBin 方法进行红黑树的转换
                        treeifyBin(tab, hash);
                    break;
                }
                //如果在循环比较过程中，发现有相同,就break,就只是替换value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
            //value的替换
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
    //size大于临界值的时候，扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}
树化
final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    //当表为null，或表的长度小于MIN_TREEIFY_CAPACITY(64)时候，只是进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //否则进行树化
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode hd = null, tl = null;
        do {
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

HashTable

HashTable实现了Map接口，方法和Map基本相同

特点:

key或value都不允许为null
线程安全的

Properties

继承HashTable类，常用于配置文件

常用方法：

load():加载配置文件
getProperty(key):得到key的属性值
setProperty(key):设置属性值

TreeMap

特点：

key不允许为null,value允许为null
key按从小到大排序
key不允许重复

其他和Map基本方法相同

 p.prev = tl;
            tl.next = p;
        }
        tl = p;
    } while ((e = e.next) != null);
    if ((tab[index] = hd) != null)
        hd.treeify(tab);
}