java集合框架

1.treeset怎么去重

1. Arraylist jdk1.8源码和1.7源码的不同

size是数组中有效长度

ArrayList list = new ArrayList();

是一个Object类型的数组，什么样的都可以存放

无参构造

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

add方法

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    private static final int DEFAULT_CAPACITY = 10;
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

     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);
    }

jdk1.8 elementData初始化为空数组，只有当调用add方法然后调用扩容方法，才会初始化新的数组大小为10，并赋值过去。

jdk1.7 为大小为10

ArrayList实现了三种接口：Randomaccess，cloneable，和serializable

2. Vector源码

protected Object[] elementData;

    
    protected int elementCount;

调用构造器

    public Vector() {
        this(10);
    }

        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

扩容方法与ArrayList 不同，是之前的2倍

泛型Generic（Jdk1.5以后使用的）

没有泛型的时候使用集合：一般放进去的都是同一类型的数据，便于管理，所以什么类型都可以存进去不方便

ArrayList list = new ArrayList;

再放其他类型的不行了。

也改变了增强for循环

3. linkedList源码

    transient int size = 0;

    transient Node first;

    transient Node last;

//Node内部类
    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;
        }
    }

     public linkedList() {
    }

    public boolean add(E e) {
        linkLast(e);
        return true;
    }

     void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

底层链表

迭代器底层关系

Itr是ArrayList的内部类

具体实现：

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable{

    transient Object[] elementData;
    private int size;
    private class Itr implements Iterator {

        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }
        public E next() {
            int i = cursor;
            if (i >= size)
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
    }
}

ListIterator

List list = new ArrayList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        Iterator it =  list.iterator();
        while(it.hasNext()){
            if ("3".equals(it.next())){
                list.add("5");
            }
        }

//报错

原因：迭代器和list同时操作数组导致（ConcurrentModificationException）并发修改异常

但是两个都没有办法完成引入ListIterator

HashMap

    public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
    //默认的数组长度
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //负载因子 
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //底层主数组
    transient Entry[] table
    //
      transient int size;
    //数组扩容的界限
    int threshold;


    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
        }
    }

    public HashMap(Map m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        inflateTable(threshold);

        putAllForCreate(m);
    }


   public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }

        if (key == null)
            return putForNullKey(value);
//    获取key的hash码
        int hash = hash(key);
//得到元素在数组中的位置
        int i = indexFor(hash, table.length);
//如果放入的位置上有东西就直接放
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    final int hash(Object k) {
//没有直接使用Hashcode，又进行了一个二次散列
//防止出现哈希冲突
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

//扰动函数，增加不确定性
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

是Entry类型数组中对应的是Entry类的对象，包含：key，value，hashcode，下一个元素的位置

哈希碰撞：当两个键相同时

核心方法：元素在数组中的索引计算公式：h & (length-1) 等价于 h% length ；原因：与运算效率高

Clone和Cloneable接口

Cloneable接口是空的，但是要是调用clone方法必须继承Cloneable接口，然后重写clone方法。

两个注意点：

1. 如果没有实现接口会出现CloneNotSupportedException的异常。

2. 重写的clone方法必须调用super.clone()方法位于java.Object类中的。

 public Object clone() {
        try {
            ArrayList v = (ArrayList) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

public interface Cloneable {
}
//Object中的Clone方法
    protected native Object clone() throws CloneNotSupportedException;

Randomaccess接口

标志接口

Serializable接口

java集合框架

1.treeset怎么去重

Java相关栏目本月热门文章