Java集合源码分析

原创
2017/05/22 16:16
阅读数 327

工作了3年多,一直都没花心思去看看jdk常用类的源码。以前大学的数据结构和算法课程在刚接触java时候感觉好像无用武之地。像c语言直接使用基础类型,可能需要去实现链表,栈,队列等。jdk都已经提供了实现类。趁最近有时间看看源码实现。

1.ArrayList

成员属性

elementData:数据存储的数组,任何操作都是基于这个数组。
size:集合现在实际的大小。为什么不直接使用elementData.length,如果直接使用elementData,每次插入,删除都要操作数组的空间(代价大),所以elementData并非每个空间都实际用到,因此不能使用length表示大小。(后面的其他集合对象也都是一样的道理)

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    private transient Object[] elementData;

    private int size;
    
初始化

1.默认数组长度10
2.指定数组长度
3.传入现用集合复制的数组

    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    
    public ArrayList() {
        this(10);
    }
    
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
操作

get:判断坐标是否超出SIZE,并非数组长度,不过只判断是否超出,没有判断是否小于0,这点也奇怪。然后返回读取数组的数据。
set:同get,判断坐标,替换数组中的元素。
add(E e):判断当前大小是否超出数组长度或者小于0,(这里又判断了),超出进行扩容grow(int minCapacity),扩容大小->原来长度位移1位,实际就是*1.5,然后就是往数组[size]赋值
add(int index, E element):同上,检查位置,不过区别在于指定坐标,就要把坐标之后的元素全部后移一位(这就是和LinkedList的效率差别,花销太大),使用System.arraycopy移动,最后一样赋值。
remove:同上,检查位置,判断是否最后一个元素,是的情况,置空最后一个元素。否的情况,一样进行位移,把坐标后面的元素全部前移一位(花销大)。

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // Let gc do its work

        return oldValue;
    }

额外说明:这里限制数组的最大长度使用了-8,按说明是为了给vms保留字头

  /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

2.LinkedList

成员属性

first,last:记录链表的第一个和最后一个元素,Node双向链表(next,prev)
size:集合实际大小,node的个数

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    
    transient Node<E> first;
 
    transient Node<E> last;

    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;
        }
    }
操作

get:判断位置是否超出size和小于0(ArrayList就没判断小于0),然后计算index是在size/2的前面还是后面,如果前面就使用first进行一个个遍历,如果大于就使用last遍历(类似二分查找,这里的相对于Arraylist直接使用数组坐标查找的开销就大很多)
set:同get操作获取node,把node的值赋成新的element。(与ArrayList相同)
add(E e):直接在尾部追加,newNode.pre = last, last.next=newNode, last=newNode;(数据结构链表添加)
add(int index, E element):判断位置合法性,判断index==size,满足就直接使用last进行追加,不满足就进行查找,添加Node进行插入(newNode在前面)
remove:判断位置合法,查找node,node.next和node.prev(node.prev.next=node.next,node.next.prev=node.prev,代码实现还需要一些额外判断)

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
    
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

两个List对比,其实和数据结构课程归纳类似:ArrayList胜在get,LinkedList胜在add,remove。不过查看代码在add(index,e),也需要使用get,这里可能就涉及到到底查找开销大还是数组位移开销大。

3.HashMap

由于HashMap涉及到hash表的构造,以及哈希冲突等以前数据结构学过的知识,就先把几种解决哈希冲突的方法说一下
1.开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1))
2.再哈希法(有多个不同的Hash函数)
3.链地址法(HashMap使用这种)
4.建立一个公共溢出区

成员属性

DEFAULT_INITIAL_CAPACITY :默认容量
MAXIMUM_CAPACITY :最大容量
DEFAULT_LOAD_FACTOR:加载因子,是一个比例,当HashMap的数据大小>=容量*加载因子时,HashMap会将容量扩容(加载因子:防止冲突过多,如果加载因子太大,导致容量一直没有扩容,元素的冲突就非常多)
table :存储数据的数组
size:大小(同ArrayList的size)

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{

    static final int DEFAULT_INITIAL_CAPACITY = 16;

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    transient Entry<K,V>[] table;

    transient int size;

初始化

1.直接使用默认16大小,0.75加载因子初始化
2.指定大小,默认加载因子
3.指定大小,指定加载因子

顺便提一个大小的问题:我们传入10,初始化后大小也不会是10,在 while (capacity < initialCapacity) capacity <<= 1;通过一直位移来确定大小,所以传入10最后会是16。

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

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }
   
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
   
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
操作

get:null特殊处理,存储位置0。其他计算key对应的hash值(hash算法可以研究一下),然后和table长度取余数,最后遍历这个坐标下面的链表(解决哈希冲突)进行hash值,key值比较,得到value。
put:计算hash,计算在数组的位置(同get操作),查看该位置是否存在改key,有就替换value,没有就新增entry(在新增的时候会判断是否扩容,原来2倍,transfer:重新计算hash的存储位置),每次扩容都要重新计算全部元素hash,开销很大,所以恰当的加载因子非常重要
remove:找出坐标(同get操作),遍历链表找出元素,然后就是单链表删除操作(pre.next=next)。

    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
    
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> 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;
    }
    
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
额外说明

indexFor:得到hash值后与长度做一个&运算,为什么会在前面说成取余数了?在前面说过table的长度只会是2的倍数,-1之后剩余的二进制全是1,这时候&运算就变成和取余数一模一样。很多地方的位运算都很神奇。

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

4.HashTable

HashTable于HashMap作比较说明

成员属性

loadFactor:加载因子(同HashMap)
table :存储数据的数组
count:大小(同HashMap的size)

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    private transient Entry<K,V>[] table;

    private transient int count;

    private float loadFactor;

初始化

默认加载因子:0.75(HashMap相同)
默认大小:11(HashMap:16)
计算实际大小也没有像HashMap那样位移计算直接根据传入的长度进行初始化。

  public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        useAltHashing = sun.misc.VM.isBooted() &&
                (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    }

    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    public Hashtable() {
        this(11, 0.75f);
    }

    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }
操作(方法加了synchronized保证线程安全)

get:计算hash值(在useAltHashing上的处理与HashMap有区别),直接与长度求余数(HashMap通过&运算),遍历链表,判断key和hash值,返回value(基本等同)。少了null的特殊判断(不支持put.null)
put:value空异常判断,key如果为null在hash(key)也会抛出异常(不支持key,value为null)。计算hash值,遍历链表,如果存在就替换value,返回。不存在,新增entry(在新增的时候会判断是否扩容rehash: newCapacity = (oldCapacity << 1) + 1;)(基本等同HashMap)
remove:计算hash值(等同get),移除元素,也是链表移除操作(等同HashMap)

    private int hash(Object k) {
        if (useAltHashing) {
            if (k.getClass() == String.class) {
                return sun.misc.Hashing.stringHash32((String) k);
            } else {
                int h = hashSeed ^ k.hashCode();

                // This function ensures that hashCodes that differ only by
                // constant multiples at each bit position have a bounded
                // number of collisions (approximately 8 at default load factor).
                h ^= (h >>> 20) ^ (h >>> 12);
                return h ^ (h >>> 7) ^ (h >>> 4);
             }
        } else  {
            return k.hashCode();
        }
    }
    
    public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }
    
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }

        modCount++;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }
    
    public synchronized V remove(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                modCount++;
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }
                count--;
                V oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
        return null;
    }
    

总的来说HashTable:不允许null键值,方法都加了synchronized,默认长度11,计算hash (hash & 0x7FFFFFFF) % tab.length;
不过现在有时候为了保证HashMap线程安全直接使用Collections.synchronizedMap(m),比较少使用HashTable。

5.HashSet

HashSet是Collection接口的子类,HashMap是Map接口的子类,两者在继承上没有关联,但是内部又使用。

成员属性

map:使用HashMap,说明所有操作都是基于HashMap,也就可以存储null值
PRESENT:定义了一个Object实体来当做每次操作HashMap的value值

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

初始化

全部基于HashMap的初始化方法,提供一一对应的初始化

    public HashSet() {
        map = new HashMap<>();
    }

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

操作

全部基于HashMap的操作方法,进行操作。

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

   
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

主要的几个常用的Collection,Map都大概看了源码,其实内部实现都是以前数据结构上学过的那些常用的数据结构,不过在看源码的时候发现很多地方都是使用了位运算,毕竟位运算效率高,而且很多地方都尽量契合二进制的计算规律。所以在看源码的时候,可以重点抓住:数据结构的使用,位运算的使用。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部