Java集合

ArrayList源码分析

（jdk7和jdk8有所不同）
jdk7的时候在调用构造函数的时候就创造出长度为10的数组，而在jdk1.8中没有，在第一次调用add方法的时候才创造数组。

构造器

ArrayList 提供了三种方式的构造器，可以构造一个默认初始容量为 10 的空列表、构造
一个指定初始容量的空列表以及构造一个包含指定 collection 的元素的列表，这些元素按照
该 collection 的迭代器返回它们的顺序排列的。

ArrayList list = new ArrayList();  // 默认初始容量为 10  底层elementData初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}，并没有创建长度为10的数组

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};   //初始为空，在调用add方法的时候才进行创造
public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

public ArrayList(int initialCapacity) {   //传入数据长度，避免在中间环节扩容，效率更高
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
 
public ArrayList(Collection c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

扩容

扩容为原来容量的1.5倍，如果此次添加导致底层elementData数组容量不够，则扩容，默认情况下，扩容为原来容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。

建议开发中使用带参构造器

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //确认容量是否足够
        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 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);   //造好新的数组
    }

HashMap源码分析

jdk7:
HashMap map = new HashMap();
在实例化以后底层创建了长度为16的一维数组，类型为Entry[] table，所有数据都放在这里。
map.put(key1,value1)；
首先，计算key1所在类的hashcode方法，计算key1的哈希值，此哈希值经过某种算法计算之后，得到在Entry数组中的存放位置。

如果此位置上的数据为空，此使key1 -value1添加成功。 -----情况1
如果此位置数据不为空，（意味着存在一个或多个数据（以链表形式存在）），比较key1和已经存在的一个或多个数据的哈希值：
- 如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。 —情况2
- 如果key1的哈希值和已经存在的某一个数据的哈希值相同，继续比较，调用key1所在类的equals方法。
- 如果equals返回false,此时key1-value1添加成功。 ----情况3
- 如果equals返回true，使用value1替换相同的key的value值

对于情况2和情况3，此时key1-value1和原来的数据以链表的方式存储

扩容：默认扩容方式：当超出临界值并且所存放位置非空扩容为原来容量的2倍，并将原有的数据复制过来。

jdk8:

new HashMap()：底层并没有创建一个长度为16的数组
底层数组为Node[] ，而非Entry[]
首次调用put方法的时候，底层创建长度为16的数组
jdk底层只有数组+链表。jdk8：数组+链表+红黑树
当数组的某一个索引位置上的元素以链表形式存在的数据个数大于8且当前数组长度超过64时，此时索引位置上的所有数据改为使用红黑树存储

HashMap源码中的重要常量

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
MAXIMUM_CAPACITY ： HashMap的最大支持容量，2^30
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树
UNTREEIFY_THRESHOLD：Bucket中红黑树存储的Node小于该默认值，转化为链表
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。（当桶中Node的
数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行
resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4
倍。）
table：存储元素的数组，总是2的n次幂
entrySet：存储具体元素的集
size：HashMap中存储的键值对的数量
modCount：HashMap扩容和结构改变的次数。
threshold：扩容的临界值，=容量*填充因子 //链表尽可能少，又要保证利用率高
loadFactor：填充因子

//放值
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)  //首次调用
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)   //判断在新数组中的位置，如果为空，直接添加
        tab[i] = newNode(hash, key, value, null);   //添加
    else {    //如果存放位置有值
        Node e; K k;
        if (p.hash == hash &&  //首先判断hash值是否相等
            ((k = p.key) == key || (key != null && key.equals(k))))   //之后在看值是否相等
            e = p;  //更新值
        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(tab, hash);
                    break;
                }
                if (e.hash == hash &&   //当前位置不是一个元素,继续比较hash值和equals，找到相同了就替换
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;   //都符合，寻找下一个元素
            }
        }
        if (e != null) { // existing mapping for key   替换旧的value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

//造好数组
final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;   //临界值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;   //16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  //12
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;   //临界值赋值
    @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];   //创造Node类型数组 16
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

final void treeifyBin(Node[] tab, int hash) {
      int n, index; Node e;
      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  //当前数组长度和64比较，小于扩容，大于变为树
          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);
      }
  }

面试题

1、ArrayList、linkedList、Vector异同
同：三个类都是先了List的接口，存储数据的特点相同：存储有序的、可重复的数据
不同：
- ArrayList：作为list接口的主要实现类，执行效率高、线程不安全；底层使用Object[]存储
- linkedList：底层使用双向链表存储；对于频繁插入和删除操作使用效率较高
- Vector：作为list接口的古老实现类，线程安全；效率低；底层使用Object[]存储

Java集合

Java相关栏目本月热门文章