常用数据结构底层实现及源码

  • 时间:
  • 浏览:3
  • 来源:跟我学网络

ArrayList、HashMap、Collection、LinkedList、Redis 底层实现及源码

Redis简介

Redis是一种key/value型数据库,其中,每个key和value都是使用对象表示的。

SET message "Hello"

其中,字符串 “message” 这个对象 就是 key , “Hello” 这个对象 就是 value

Redis有5种对象的类型

REDIS_STRINGstring字符串对象
REDIS_LISTlist列表对象
REDIS_HASHhash哈希对象
REDIS_SETset集合对象
REDIS_ZSETzset有序集合对象

Redis对象底层数据结构

intlong类型的整数
embstrembstr编码的简单动态字符串
raw简单动态字符串
ht字典
linkedlist双端链表
ziplist压缩列表
intset整数集合
skiplist跳跃表和字典

字符串对象

字符串对象的编码可以是int、raw、embstr

如果字符串对象的长度小于39字节,就用embstr

否则用传统的raw对象

# define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39  
robj *createStringObject(char *ptr, size_t len) {  
    if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT)  
        return createEmbeddedStringObject(ptr,len);  
    else  
        return createRawStringObject(ptr,len);  
}  

embstr的优点:

  • 创建只需分配一次内存,raw为两次
  • 释放内存也是一次
  • embstr的objet和sds放在一起,更好地利用缓存带来的优势

列表对象

列表对象的编码可以是 ziplist or LinkedList

ziplist 是一种压缩链表,好处是更能节省内存空间,存储的内容都是在连续的内存区域中的

LinkedList是一种双向链表,没增加一个node,都要重新分配一个内存


哈希对象

哈希对象的底层实现用ziplist or hashtable

ziplist : 对象数目不多且内容不大,这种方式效率很高

HashTable由dict这个结构实现


集合对象

集合对象编码可以是 intset or HashTable


有序集合对象

编码一种是 ziplist ,一种是skipList 与 dict 的结合

ziplist作为集合和作为哈希对象是一样的,member和score顺序存放。按照score从小到大顺序排列。它的结构不再复述。

skiplist是一种跳跃表,它实现了有序集合中的快速查找,在大多数情况下它的速度都可以和平衡树差不多。但它的实现比较简单,可以作为平衡树的替代品。


ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长(1.5+1)。

非线程安全

源码:

package java.util;    
   
public class ArrayList<E> extends AbstractList<E>    
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable    
{    
    // 序列版本号    
    private static final long serialVersionUID = 8683452581122892189L;    
   
    // ArrayList基于该数组实现,用该数组保存数据   
    private transient Object[] elementData;    
   
    // ArrayList中实际数据的数量    
    private int size;    
   
    // ArrayList带容量大小的构造函数。    
    public ArrayList(int initialCapacity) {    
        super();    
        if (initialCapacity < 0)    
            throw new IllegalArgumentException("Illegal Capacity: "+    
                                               initialCapacity);    
        // 新建一个数组    
        this.elementData = new Object[initialCapacity];    
    }    
   
    // ArrayList无参构造函数。默认容量是10。    
    public ArrayList() {    
        this(10);    
    }    
   
    // 创建一个包含collection的ArrayList    
    public ArrayList(Collection<? extends E> c) {    
        elementData = c.toArray();    
        size = elementData.length;    
        if (elementData.getClass() != Object[].class)    
            elementData = Arrays.copyOf(elementData, size, Object[].class);    
    }    
   
   
    // 将当前容量值设为实际元素个数    
    public void trimToSize() {    
        modCount++;    
        int oldCapacity = elementData.length;    
        if (size < oldCapacity) {    
            elementData = Arrays.copyOf(elementData, size);    
        }    
    }    
   
   
    // 确定ArrarList的容量。    
    // 若ArrayList的容量不足以容纳当前的全部元素,设置 新的容量=“(原始容量x3)/2 + 1”    
    public void ensureCapacity(int minCapacity) {    
        // 将“修改统计数”+1,该变量主要是用来实现fail-fast机制的    
        modCount++;    
        int oldCapacity = elementData.length;    
        // 若当前容量不足以容纳当前的元素个数,设置 新的容量=“(原始容量x3)/2 + 1”    
        if (minCapacity > oldCapacity) {    
            Object oldData[] = elementData;    
            int newCapacity = (oldCapacity * 3)/2 + 1;    
            //如果还不够,则直接将minCapacity设置为当前容量  
            if (newCapacity < minCapacity)    
                newCapacity = minCapacity;    
            elementData = Arrays.copyOf(elementData, newCapacity);    
        }    
    }    
   
    // 添加元素e    
    public boolean add(E e) {    
        // 确定ArrayList的容量大小    
        ensureCapacity(size + 1);  // Increments modCount!!    
        // 添加e到ArrayList中    
        elementData[size++] = e;    
        return true;    
    }    
   
    // 返回ArrayList的实际大小    
    public int size() {    
        return size;    
    }    
   
    // ArrayList是否包含Object(o)    
    public boolean contains(Object o) {    
        return indexOf(o) >= 0;    
    }    
   
    //返回ArrayList是否为空    
    public boolean isEmpty() {    
        return size == 0;    
    }    
   
    // 正向查找,返回元素的索引值    
    public int indexOf(Object o) {    
        if (o == null) {    
            for (int i = 0; i < size; i++)    
            if (elementData[i]==null)    
                return i;    
            } else {    
                for (int i = 0; i < size; i++)    
                if (o.equals(elementData[i]))    
                    return i;    
            }    
            return -1;    
        }    
   
    // 反向查找(从数组末尾向开始查找),返回元素(o)的索引值    
    public int lastIndexOf(Object o) {    
        if (o == null) {    
            for (int i = size-1; i >= 0; i--)    
            if (elementData[i]==null)    
                return i;    
        } else {    
            for (int i = size-1; i >= 0; i--)    
            if (o.equals(elementData[i]))    
                return i;    
        }    
        return -1;    
    }    
     
   
    // 返回ArrayList的Object数组    
    public Object[] toArray() {    
        return Arrays.copyOf(elementData, size);    
    }    
   
    // 返回ArrayList元素组成的数组  
    public <T> T[] toArray(T[] a) {    
        // 若数组a的大小 < ArrayList的元素个数;    
        // 则新建一个T[]数组,数组大小是“ArrayList的元素个数”,并将“ArrayList”全部拷贝到新数组中    
        if (a.length < size)    
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());    
   
        // 若数组a的大小 >= ArrayList的元素个数;    
        // 则将ArrayList的全部元素都拷贝到数组a中。    
        System.arraycopy(elementData, 0, a, 0, size);    
        if (a.length > size)    
            a[size] = null;    
        return a;    
    }    
   
    // 获取index位置的元素值    
    public E get(int index) {    
        RangeCheck(index);    
   
        return (E) elementData[index];    
    }    
   
    // 设置index位置的值为element    
    public E set(int index, E element) {    
        RangeCheck(index);    
   
        E oldValue = (E) elementData[index];    
        elementData[index] = element;    
        return oldValue;    
    }    
   
    // 将e添加到ArrayList中    
    public boolean add(E e) {    
        ensureCapacity(size + 1);  // Increments modCount!!    
        elementData[size++] = e;    
        return true;    
    }    
   
    // 将e添加到ArrayList的指定位置    
    public void add(int index, E element) {    
        if (index > size || index < 0)    
            throw new IndexOutOfBoundsException(    
            "Index: "+index+", Size: "+size);    
   
        ensureCapacity(size+1);  // Increments modCount!!    
        System.arraycopy(elementData, index, elementData, index + 1,    
             size - index);    
        elementData[index] = element;    
        size++;    
    }    
   
    // 删除ArrayList指定位置的元素    
    public E remove(int index) {    
        RangeCheck(index);    
   
        modCount++;    
        E oldValue = (E) 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;    
    }    
   
    // 删除ArrayList的指定元素    
    public boolean remove(Object o) {    
        if (o == null) {    
                for (int index = 0; index < size; index++)    
            if (elementData[index] == null) {    
                fastRemove(index);    
                return true;    
            }    
        } else {    
            for (int index = 0; index < size; index++)    
            if (o.equals(elementData[index])) {    
                fastRemove(index);    
                return true;    
            }    
        }    
        return false;    
    }    
   
   
    // 快速删除第index个元素    
    private void fastRemove(int index) {    
        modCount++;    
        int numMoved = size - index - 1;    
        // 从"index+1"开始,用后面的元素替换前面的元素。    
        if (numMoved > 0)    
            System.arraycopy(elementData, index+1, elementData, index,    
                             numMoved);    
        // 将最后一个元素设为null    
        elementData[--size] = null; // Let gc do its work    
    }    
   
    // 删除元素    
    public boolean remove(Object o) {    
        if (o == null) {    
            for (int index = 0; index < size; index++)    
            if (elementData[index] == null) {    
                fastRemove(index);    
            return true;    
            }    
        } else {    
            // 便利ArrayList,找到“元素o”,则删除,并返回true。    
            for (int index = 0; index < size; index++)    
            if (o.equals(elementData[index])) {    
                fastRemove(index);    
            return true;    
            }    
        }    
        return false;    
    }    
   
    // 清空ArrayList,将全部的元素设为null    
    public void clear() {    
        modCount++;    
   
        for (int i = 0; i < size; i++)    
            elementData[i] = null;    
   
        size = 0;    
    }    
   
    // 将集合c追加到ArrayList中    
    public boolean addAll(Collection<? extends E> c) {    
        Object[] a = c.toArray();    
        int numNew = a.length;    
        ensureCapacity(size + numNew);  // Increments modCount    
        System.arraycopy(a, 0, elementData, size, numNew);    
        size += numNew;    
        return numNew != 0;    
    }    
   
    // 从index位置开始,将集合c添加到ArrayList    
    public boolean addAll(int index, Collection<? extends E> c) {    
        if (index > size || index < 0)    
            throw new IndexOutOfBoundsException(    
            "Index: " + index + ", Size: " + size);    
   
        Object[] a = c.toArray();    
        int numNew = a.length;    
        ensureCapacity(size + numNew);  // Increments modCount    
   
        int numMoved = size - index;    
        if (numMoved > 0)    
            System.arraycopy(elementData, index, elementData, index + numNew,    
                 numMoved);    
   
        System.arraycopy(a, 0, elementData, index, numNew);    
        size += numNew;    
        return numNew != 0;    
    }    
   
    // 删除fromIndex到toIndex之间的全部元素。    
    protected void removeRange(int fromIndex, int toIndex) {    
    modCount++;    
    int numMoved = size - toIndex;    
        System.arraycopy(elementData, toIndex, elementData, fromIndex,    
                         numMoved);    
   
    // Let gc do its work    
    int newSize = size - (toIndex-fromIndex);    
    while (size != newSize)    
        elementData[--size] = null;    
    }    
   
    private void RangeCheck(int index) {    
    if (index >= size)    
        throw new IndexOutOfBoundsException(    
        "Index: "+index+", Size: "+size);    
    }    
   
   
    // 克隆函数    
    public Object clone() {    
        try {    
            ArrayList<E> v = (ArrayList<E>) super.clone();    
            // 将当前ArrayList的全部元素拷贝到v中    
            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();    
        }    
    }    
   
   
    // java.io.Serializable的写入函数    
    // 将ArrayList的“容量,所有的元素值”都写入到输出流中    
    private void writeObject(java.io.ObjectOutputStream s)    
        throws java.io.IOException{    
    // Write out element count, and any hidden stuff    
    int expectedModCount = modCount;    
    s.defaultWriteObject();    
   
        // 写入“数组的容量”    
        s.writeInt(elementData.length);    
   
    // 写入“数组的每一个元素”    
    for (int i=0; i<size; i++)    
            s.writeObject(elementData[i]);    
   
    if (modCount != expectedModCount) {    
            throw new ConcurrentModificationException();    
        }    
   
    }    
   
   
    // java.io.Serializable的读取函数:根据写入方式读出    
    // 先将ArrayList的“容量”读出,然后将“所有的元素值”读出    
    private void readObject(java.io.ObjectInputStream s)    
        throws java.io.IOException, ClassNotFoundException {    
        // Read in size, and any hidden stuff    
        s.defaultReadObject();    
   
        // 从输入流中读取ArrayList的“容量”    
        int arrayLength = s.readInt();    
        Object[] a = elementData = new Object[arrayLength];    
   
        // 从输入流中将“所有的元素值”读出    
        for (int i=0; i<size; i++)    
            a[i] = s.readObject();    
    }    
}  

HashMap是基于哈希表实现,每一个元素都是一个key-value对,其内部通过单链表解决冲突问题,容量不足时,会自动增长。

非线程安全,只是用于单线程环境下,多线程用concurrentHashMap

实现了Serializable接口,因此支持序列化,实现了Cloneable接口,能被克隆。

源码:

package java.util;    
import java.io.*;    
   
public class HashMap<K,V>    
    extends AbstractMap<K,V>    
    implements Map<K,V>, Cloneable, Serializable    
{    
   
    // 默认的初始容量(容量为HashMap中槽的数目)是16,且实际容量必须是2的整数次幂。    
    static final int DEFAULT_INITIAL_CAPACITY = 16;    
   
    // 最大容量(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换)    
    static final int MAXIMUM_CAPACITY = 1 << 30;    
   
    // 默认加载因子为0.75   
    static final float DEFAULT_LOAD_FACTOR = 0.75f;    
   
    // 存储数据的Entry数组,长度是2的幂。    
    // HashMap采用链表法解决冲突,每一个Entry本质上是一个单向链表    
    transient Entry[] table;    
   
    // HashMap的底层数组中已用槽的数量    
    transient int size;    
   
    // HashMap的阈值,用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子)    
    int threshold;    
   
    // 加载因子实际大小    
    final float loadFactor;    
   
    // HashMap被改变的次数    
    transient volatile int modCount;    
   
    // 指定“容量大小”和“加载因子”的构造函数    
    public HashMap(int initialCapacity, float loadFactor) {    
        if (initialCapacity < 0)    
            throw new IllegalArgumentException("Illegal initial capacity: " +    
                                               initialCapacity);    
        // HashMap的最大容量只能是MAXIMUM_CAPACITY    
        if (initialCapacity > MAXIMUM_CAPACITY)    
            initialCapacity = MAXIMUM_CAPACITY;    
        //加载因此不能小于0  
        if (loadFactor <= 0 || Float.isNaN(loadFactor))    
            throw new IllegalArgumentException("Illegal load factor: " +    
                                               loadFactor);    
   
        // 找出“大于initialCapacity”的最小的2的幂    
        int capacity = 1;    
        while (capacity < initialCapacity)    
            capacity <<= 1;    
   
        // 设置“加载因子”    
        this.loadFactor = loadFactor;    
        // 设置“HashMap阈值”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。    
        threshold = (int)(capacity * loadFactor);    
        // 创建Entry数组,用来保存数据    
        table = new Entry[capacity];    
        init();    
    }    
   
   
    // 指定“容量大小”的构造函数    
    public HashMap(int initialCapacity) {    
        this(initialCapacity, DEFAULT_LOAD_FACTOR);    
    }    
   
    // 默认构造函数。    
    public HashMap() {    
        // 设置“加载因子”为默认加载因子0.75    
        this.loadFactor = DEFAULT_LOAD_FACTOR;    
        // 设置“HashMap阈值”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。    
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);    
        // 创建Entry数组,用来保存数据    
        table = new Entry[DEFAULT_INITIAL_CAPACITY];    
        init();    
    }    
   
    // 包含“子Map”的构造函数    
    public HashMap(Map<? extends K, ? extends V> m) {    
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,    
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);    
        // 将m中的全部元素逐个添加到HashMap中    
        putAllForCreate(m);    
    }    
   
    //求hash值的方法,重新计算hash值  
    static int hash(int h) {    
        h ^= (h >>> 20) ^ (h >>> 12);    
        return h ^ (h >>> 7) ^ (h >>> 4);    
    }    
   
    // 返回h在数组中的索引值,这里用&代替取模,旨在提升效率   
    // h & (length-1)保证返回值的小于length    
    static int indexFor(int h, int length) {    
        return h & (length-1);    
    }    
   
    public int size() {    
        return size;    
    }    
   
    public boolean isEmpty() {    
        return size == 0;    
    }    
   
    // 获取key对应的value    
    public V get(Object key) {    
        if (key == null)    
            return getForNullKey();    
        // 获取key的hash值    
        int hash = hash(key.hashCode());    
        // 在“该hash值对应的链表”上查找“键值等于key”的元素    
        for (Entry<K,V> e = table[indexFor(hash, table.length)];    
             e != null;    
             e = e.next) {    
            Object k;    
            //判断key是否相同  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))    
                return e.value;    
        }  
        //没找到则返回null  
        return null;    
    }    
   
    // 获取“key为null”的元素的值    
    // HashMap将“key为null”的元素存储在table[0]位置,但不一定是该链表的第一个位置!    
    private V getForNullKey() {    
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
            if (e.key == null)    
                return e.value;    
        }    
        return null;    
    }    
   
    // HashMap是否包含key    
    public boolean containsKey(Object key) {    
        return getEntry(key) != null;    
    }    
   
    // 返回“键为key”的键值对    
    final Entry<K,V> getEntry(Object key) {    
        // 获取哈希值    
        // HashMap将“key为null”的元素存储在table[0]位置,“key不为null”的则调用hash()计算哈希值    
        int hash = (key == null) ? 0 : hash(key.hashCode());    
        // 在“该hash值对应的链表”上查找“键值等于key”的元素    
        for (Entry<K,V> e = table[indexFor(hash, table.length)];    
             e != null;    
             e = e.next) {    
            Object k;    
            if (e.hash == hash &&    
                ((k = e.key) == key || (key != null && key.equals(k))))    
                return e;    
        }    
        return null;    
    }    
   
    // 将“key-value”添加到HashMap中    
    public V put(K key, V value) {    
        // 若“key为null”,则将该键值对添加到table[0]中。    
        if (key == null)    
            return putForNullKey(value);    
        // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。    
        int hash = hash(key.hashCode());    
        int i = indexFor(hash, table.length);    
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
            Object k;    
            // 若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!    
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {    
                V oldValue = e.value;    
                e.value = value;    
                e.recordAccess(this);    
                return oldValue;    
            }    
        }    
   
        // 若“该key”对应的键值对不存在,则将“key-value”添加到table中    
        modCount++;  
        //将key-value添加到table[i]处  
        addEntry(hash, key, value, i);    
        return null;    
    }    
   
    // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置    
    private V putForNullKey(V value) {    
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
            if (e.key == null) {    
                V oldValue = e.value;    
                e.value = value;    
                e.recordAccess(this);    
                return oldValue;    
            }    
        }    
        // 如果没有存在key为null的键值对,则直接题阿见到table[0]处!    
        modCount++;    
        addEntry(0, null, value, 0);    
        return null;    
    }    
   
    // 创建HashMap对应的“添加方法”,    
    // 它和put()不同。putForCreate()是内部方法,它被构造函数等调用,用来创建HashMap    
    // 而put()是对外提供的往HashMap中添加元素的方法。    
    private void putForCreate(K key, V value) {    
        int hash = (key == null) ? 0 : hash(key.hashCode());    
        int i = indexFor(hash, table.length);    
   
        // 若该HashMap表中存在“键值等于key”的元素,则替换该元素的value值    
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
            Object k;    
            if (e.hash == hash &&    
                ((k = e.key) == key || (key != null && key.equals(k)))) {    
                e.value = value;    
                return;    
            }    
        }    
   
        // 若该HashMap表中不存在“键值等于key”的元素,则将该key-value添加到HashMap中    
        createEntry(hash, key, value, i);    
    }    
   
    // 将“m”中的全部元素都添加到HashMap中。    
    // 该方法被内部的构造HashMap的方法所调用。    
    private void putAllForCreate(Map<? extends K, ? extends V> m) {    
        // 利用迭代器将元素逐个添加到HashMap中    
        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {    
            Map.Entry<? extends K, ? extends V> e = i.next();    
            putForCreate(e.getKey(), e.getValue());    
        }    
    }    
   
    // 重新调整HashMap的大小,newCapacity是调整后的容量    
    void resize(int newCapacity) {    
        Entry[] oldTable = table;    
        int oldCapacity = oldTable.length;   
        //如果就容量已经达到了最大值,则不能再扩容,直接返回  
        if (oldCapacity == MAXIMUM_CAPACITY) {    
            threshold = Integer.MAX_VALUE;    
            return;    
        }    
   
        // 新建一个HashMap,将“旧HashMap”的全部元素添加到“新HashMap”中,    
        // 然后,将“新HashMap”赋值给“旧HashMap”。    
        Entry[] newTable = new Entry[newCapacity];    
        transfer(newTable);    
        table = newTable;    
        threshold = (int)(newCapacity * loadFactor);    
    }    
   
    // 将HashMap中的全部元素都添加到newTable中    
    void transfer(Entry[] newTable) {    
        Entry[] src = table;    
        int newCapacity = newTable.length;    
        for (int j = 0; j < src.length; j++) {    
            Entry<K,V> e = src[j];    
            if (e != null) {    
                src[j] = null;    
                do {    
                    Entry<K,V> next = e.next;    
                    int i = indexFor(e.hash, newCapacity);    
                    e.next = newTable[i];    
                    newTable[i] = e;    
                    e = next;    
                } while (e != null);    
            }    
        }    
    }    
   
    // 将"m"的全部元素都添加到HashMap中    
    public void putAll(Map<? extends K, ? extends V> m) {    
        // 有效性判断    
        int numKeysToBeAdded = m.size();    
        if (numKeysToBeAdded == 0)    
            return;    
   
        // 计算容量是否足够,    
        // 若“当前阀值容量 < 需要的容量”,则将容量x2。    
        if (numKeysToBeAdded > threshold) {    
            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);    
            if (targetCapacity > MAXIMUM_CAPACITY)    
                targetCapacity = MAXIMUM_CAPACITY;    
            int newCapacity = table.length;    
            while (newCapacity < targetCapacity)    
                newCapacity <<= 1;    
            if (newCapacity > table.length)    
                resize(newCapacity);    
        }    
   
        // 通过迭代器,将“m”中的元素逐个添加到HashMap中。    
        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {    
            Map.Entry<? extends K, ? extends V> e = i.next();    
            put(e.getKey(), e.getValue());    
        }    
    }    
   
    // 删除“键为key”元素    
    public V remove(Object key) {    
        Entry<K,V> e = removeEntryForKey(key);    
        return (e == null ? null : e.value);    
    }    
   
    // 删除“键为key”的元素    
    final Entry<K,V> removeEntryForKey(Object key) {    
        // 获取哈希值。若key为null,则哈希值为0;否则调用hash()进行计算    
        int hash = (key == null) ? 0 : hash(key.hashCode());    
        int i = indexFor(hash, table.length);    
        Entry<K,V> prev = table[i];    
        Entry<K,V> e = prev;    
   
        // 删除链表中“键为key”的元素    
        // 本质是“删除单向链表中的节点”    
        while (e != null) {    
            Entry<K,V> next = e.next;    
            Object k;    
            if (e.hash == hash &&    
                ((k = e.key) == key || (key != null && key.equals(k)))) {    
                modCount++;    
                size--;    
                if (prev == e)    
                    table[i] = next;    
                else   
                    prev.next = next;    
                e.recordRemoval(this);    
                return e;    
            }    
            prev = e;    
            e = next;    
        }    
   
        return e;    
    }    
   
    // 删除“键值对”    
    final Entry<K,V> removeMapping(Object o) {    
        if (!(o instanceof Map.Entry))    
            return null;    
   
        Map.Entry<K,V> entry = (Map.Entry<K,V>) o;    
        Object key = entry.getKey();    
        int hash = (key == null) ? 0 : hash(key.hashCode());    
        int i = indexFor(hash, table.length);    
        Entry<K,V> prev = table[i];    
        Entry<K,V> e = prev;    
   
        // 删除链表中的“键值对e”    
        // 本质是“删除单向链表中的节点”    
        while (e != null) {    
            Entry<K,V> next = e.next;    
            if (e.hash == hash && e.equals(entry)) {    
                modCount++;    
                size--;    
                if (prev == e)    
                    table[i] = next;    
                else   
                    prev.next = next;    
                e.recordRemoval(this);    
                return e;    
            }    
            prev = e;    
            e = next;    
        }    
   
        return e;    
    }    
   
    // 清空HashMap,将所有的元素设为null    
    public void clear() {    
        modCount++;    
        Entry[] tab = table;    
        for (int i = 0; i < tab.length; i++)    
            tab[i] = null;    
        size = 0;    
    }    
   
    // 是否包含“值为value”的元素    
    public boolean containsValue(Object value) {    
    // 若“value为null”,则调用containsNullValue()查找    
    if (value == null)    
            return containsNullValue();    
   
    // 若“value不为null”,则查找HashMap中是否有值为value的节点。    
    Entry[] tab = table;    
        for (int i = 0; i < tab.length ; i++)    
            for (Entry e = tab[i] ; e != null ; e = e.next)    
                if (value.equals(e.value))    
                    return true;    
    return false;    
    }    
   
    // 是否包含null值    
    private boolean containsNullValue() {    
    Entry[] tab = table;    
        for (int i = 0; i < tab.length ; i++)    
            for (Entry e = tab[i] ; e != null ; e = e.next)    
                if (e.value == null)    
                    return true;    
    return false;    
    }    
   
    // 克隆一个HashMap,并返回Object对象    
    public Object clone() {    
        HashMap<K,V> result = null;    
        try {    
            result = (HashMap<K,V>)super.clone();    
        } catch (CloneNotSupportedException e) {    
            // assert false;    
        }    
        result.table = new Entry[table.length];    
        result.entrySet = null;    
        result.modCount = 0;    
        result.size = 0;    
        result.init();    
        // 调用putAllForCreate()将全部元素添加到HashMap中    
        result.putAllForCreate(this);    
   
        return result;    
    }    
   
    // Entry是单向链表。    
    // 它是 “HashMap链式存储法”对应的链表。    
    // 它实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数    
    static class Entry<K,V> implements Map.Entry<K,V> {    
        final K key;    
        V value;    
        // 指向下一个节点    
        Entry<K,V> next;    
        final int hash;    
   
        // 构造函数。    
        // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"    
        Entry(int h, K k, V v, Entry<K,V> n) {    
            value = v;    
            next = n;    
            key = k;    
            hash = h;    
        }    
   
        public final K getKey() {    
            return key;    
        }    
   
        public final V getValue() {    
            return value;    
        }    
   
        public final V setValue(V newValue) {    
            V oldValue = value;    
            value = newValue;    
            return oldValue;    
        }    
   
        // 判断两个Entry是否相等    
        // 若两个Entry的“key”和“value”都相等,则返回true。    
        // 否则,返回false    
        public final boolean equals(Object o) {    
            if (!(o instanceof Map.Entry))    
                return false;    
            Map.Entry e = (Map.Entry)o;    
            Object k1 = getKey();    
            Object k2 = e.getKey();    
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {    
                Object v1 = getValue();    
                Object v2 = e.getValue();    
                if (v1 == v2 || (v1 != null && v1.equals(v2)))    
                    return true;    
            }    
            return false;    
        }    
   
        // 实现hashCode()    
        public final int hashCode() {    
            return (key==null   ? 0 : key.hashCode()) ^    
                   (value==null ? 0 : value.hashCode());    
        }    
   
        public final String toString() {    
            return getKey() + "=" + getValue();    
        }    
   
        // 当向HashMap中添加元素时,绘调用recordAccess()。    
        // 这里不做任何处理    
        void recordAccess(HashMap<K,V> m) {    
        }    
   
        // 当从HashMap中删除元素时,绘调用recordRemoval()。    
        // 这里不做任何处理    
        void recordRemoval(HashMap<K,V> m) {    
        }    
    }    
   
    // 新增Entry。将“key-value”插入指定位置,bucketIndex是位置索引。    
    void addEntry(int hash, K key, V value, int bucketIndex) {    
        // 保存“bucketIndex”位置的值到“e”中    
        Entry<K,V> e = table[bucketIndex];    
        // 设置“bucketIndex”位置的元素为“新Entry”,    
        // 设置“e”为“新Entry的下一个节点”    
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
        // 若HashMap的实际大小 不小于 “阈值”,则调整HashMap的大小    
        if (size++ >= threshold)    
            resize(2 * table.length);    
    }    
   
    // 创建Entry。将“key-value”插入指定位置。    
    void createEntry(int hash, K key, V value, int bucketIndex) {    
        // 保存“bucketIndex”位置的值到“e”中    
        Entry<K,V> e = table[bucketIndex];    
        // 设置“bucketIndex”位置的元素为“新Entry”,    
        // 设置“e”为“新Entry的下一个节点”    
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
        size++;    
    }    
   
    // HashIterator是HashMap迭代器的抽象出来的父类,实现了公共了函数。    
    // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。    
    private abstract class HashIterator<E> implements Iterator<E> {    
        // 下一个元素    
        Entry<K,V> next;    
        // expectedModCount用于实现fast-fail机制。    
        int expectedModCount;    
        // 当前索引    
        int index;    
        // 当前元素    
        Entry<K,V> current;    
   
        HashIterator() {    
            expectedModCount = modCount;    
            if (size > 0) { // advance to first entry    
                Entry[] t = table;    
                // 将next指向table中第一个不为null的元素。    
                // 这里利用了index的初始值为0,从0开始依次向后遍历,直到找到不为null的元素就退出循环。    
                while (index < t.length && (next = t[index++]) == null)    
                    ;    
            }    
        }    
   
        public final boolean hasNext() {    
            return next != null;    
        }    
   
        // 获取下一个元素    
        final Entry<K,V> nextEntry() {    
            if (modCount != expectedModCount)    
                throw new ConcurrentModificationException();    
            Entry<K,V> e = next;    
            if (e == null)    
                throw new NoSuchElementException();    
   
            // 注意!!!    
            // 一个Entry就是一个单向链表    
            // 若该Entry的下一个节点不为空,就将next指向下一个节点;    
            // 否则,将next指向下一个链表(也是下一个Entry)的不为null的节点。    
            if ((next = e.next) == null) {    
                Entry[] t = table;    
                while (index < t.length && (next = t[index++]) == null)    
                    ;    
            }    
            current = e;    
            return e;    
        }    
   
        // 删除当前元素    
        public void remove() {    
            if (current == null)    
                throw new IllegalStateException();    
            if (modCount != expectedModCount)    
                throw new ConcurrentModificationException();    
            Object k = current.key;    
            current = null;    
            HashMap.this.removeEntryForKey(k);    
            expectedModCount = modCount;    
        }    
   
    }    
   
    // value的迭代器    
    private final class ValueIterator extends HashIterator<V> {    
        public V next() {    
            return nextEntry().value;    
        }    
    }    
   
    // key的迭代器    
    private final class KeyIterator extends HashIterator<K> {    
        public K next() {    
            return nextEntry().getKey();    
        }    
    }    
   
    // Entry的迭代器    
    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {    
        public Map.Entry<K,V> next() {    
            return nextEntry();    
        }    
    }    
   
    // 返回一个“key迭代器”    
    Iterator<K> newKeyIterator()   {    
        return new KeyIterator();    
    }    
    // 返回一个“value迭代器”    
    Iterator<V> newValueIterator()   {    
        return new ValueIterator();    
    }    
    // 返回一个“entry迭代器”    
    Iterator<Map.Entry<K,V>> newEntryIterator()   {    
        return new EntryIterator();    
    }    
   
    // HashMap的Entry对应的集合    
    private transient Set<Map.Entry<K,V>> entrySet = null;    
   
    // 返回“key的集合”,实际上返回一个“KeySet对象”    
    public Set<K> keySet() {    
        Set<K> ks = keySet;    
        return (ks != null ? ks : (keySet = new KeySet()));    
    }    
   
    // Key对应的集合    
    // KeySet继承于AbstractSet,说明该集合中没有重复的Key。    
    private final class KeySet extends AbstractSet<K> {    
        public Iterator<K> iterator() {    
            return newKeyIterator();    
        }    
        public int size() {    
            return size;    
        }    
        public boolean contains(Object o) {    
            return containsKey(o);    
        }    
        public boolean remove(Object o) {    
            return HashMap.this.removeEntryForKey(o) != null;    
        }    
        public void clear() {    
            HashMap.this.clear();    
        }    
    }    
   
    // 返回“value集合”,实际上返回的是一个Values对象    
    public Collection<V> values() {    
        Collection<V> vs = values;    
        return (vs != null ? vs : (values = new Values()));    
    }    
   
    // “value集合”    
    // Values继承于AbstractCollection,不同于“KeySet继承于AbstractSet”,    
    // Values中的元素能够重复。因为不同的key可以指向相同的value。    
    private final class Values extends AbstractCollection<V> {    
        public Iterator<V> iterator() {    
            return newValueIterator();    
        }    
        public int size() {    
            return size;    
        }    
        public boolean contains(Object o) {    
            return containsValue(o);    
        }    
        public void clear() {    
            HashMap.this.clear();    
        }    
    }    
   
    // 返回“HashMap的Entry集合”    
    public Set<Map.Entry<K,V>> entrySet() {    
        return entrySet0();    
    }    
   
    // 返回“HashMap的Entry集合”,它实际是返回一个EntrySet对象    
    private Set<Map.Entry<K,V>> entrySet0() {    
        Set<Map.Entry<K,V>> es = entrySet;    
        return es != null ? es : (entrySet = new EntrySet());    
    }    
   
    // EntrySet对应的集合    
    // EntrySet继承于AbstractSet,说明该集合中没有重复的EntrySet。    
    private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {    
        public Iterator<Map.Entry<K,V>> iterator() {    
            return newEntryIterator();    
        }    
        public boolean contains(Object o) {    
            if (!(o instanceof Map.Entry))    
                return false;    
            Map.Entry<K,V> e = (Map.Entry<K,V>) o;    
            Entry<K,V> candidate = getEntry(e.getKey());    
            return candidate != null && candidate.equals(e);    
        }    
        public boolean remove(Object o) {    
            return removeMapping(o) != null;    
        }    
        public int size() {    
            return size;    
        }    
        public void clear() {    
            HashMap.this.clear();    
        }    
    }    
   
    // java.io.Serializable的写入函数    
    // 将HashMap的“总的容量,实际容量,所有的Entry”都写入到输出流中    
    private void writeObject(java.io.ObjectOutputStream s)    
        throws IOException    
    {    
        Iterator<Map.Entry<K,V>> i =    
            (size > 0) ? entrySet0().iterator() : null;    
   
        // Write out the threshold, loadfactor, and any hidden stuff    
        s.defaultWriteObject();    
   
        // Write out number of buckets    
        s.writeInt(table.length);    
   
        // Write out size (number of Mappings)    
        s.writeInt(size);    
   
        // Write out keys and values (alternating)    
        if (i != null) {    
            while (i.hasNext()) {    
            Map.Entry<K,V> e = i.next();    
            s.writeObject(e.getKey());    
            s.writeObject(e.getValue());    
            }    
        }    
    }    
   
   
    private static final long serialVersionUID = 362498820763181265L;    
   
    // java.io.Serializable的读取函数:根据写入方式读出    
    // 将HashMap的“总的容量,实际容量,所有的Entry”依次读出    
    private void readObject(java.io.ObjectInputStream s)    
         throws IOException, ClassNotFoundException    
    {    
        // Read in the threshold, loadfactor, and any hidden stuff    
        s.defaultReadObject();    
   
        // Read in number of buckets and allocate the bucket array;    
        int numBuckets = s.readInt();    
        table = new Entry[numBuckets];    
   
        init();  // Give subclass a chance to do its thing.    
   
        // Read in size (number of Mappings)    
        int size = s.readInt();    
   
        // Read the keys and values, and put the mappings in the HashMap    
        for (int i=0; i<size; i++) {    
            K key = (K) s.readObject();    
            V value = (V) s.readObject();    
            putForCreate(key, value);    
        }    
    }    
   
    // 返回“HashMap总的容量”    
    int   capacity()     { return table.length; }    
    // 返回“HashMap的加载因子”    
    float loadFactor()   { return loadFactor;   }    
}   

基于哈希表实现,每个元素都是key-value对,内部通过单链表解决冲突问题,容量不足时,自动增长

是线程安全的,能用于多线程

实现了Serializable接口,支持序列号

实现了Cloneable接口,能被克隆

package java.util;    
import java.io.*;    
   
public class Hashtable<K,V>    
    extends Dictionary<K,V>    
    implements Map<K,V>, Cloneable, java.io.Serializable {    
   
    // 保存key-value的数组。    
    // Hashtable同样采用单链表解决冲突,每一个Entry本质上是一个单向链表    
    private transient Entry[] table;    
   
    // Hashtable中键值对的数量    
    private transient int count;    
   
    // 阈值,用于判断是否需要调整Hashtable的容量(threshold = 容量*加载因子)    
    private int threshold;    
   
    // 加载因子    
    private float loadFactor;    
   
    // Hashtable被改变的次数,用于fail-fast机制的实现    
    private transient int modCount = 0;    
   
    // 序列版本号    
    private static final long serialVersionUID = 1421746759512286392L;    
   
    // 指定“容量大小”和“加载因子”的构造函数    
    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)(initialCapacity * loadFactor);    
    }    
   
    // 指定“容量大小”的构造函数    
    public Hashtable(int initialCapacity) {    
        this(initialCapacity, 0.75f);    
    }    
   
    // 默认构造函数。    
    public Hashtable() {    
        // 默认构造函数,指定的容量大小是11;加载因子是0.75    
        this(11, 0.75f);    
    }    
   
    // 包含“子Map”的构造函数    
    public Hashtable(Map<? extends K, ? extends V> t) {    
        this(Math.max(2*t.size(), 11), 0.75f);    
        // 将“子Map”的全部元素都添加到Hashtable中    
        putAll(t);    
    }    
    
    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 int size() {    
        return count;    
    }    
   
    public synchronized boolean isEmpty() {    
        return count == 0;    
    }    
   
    // 返回“所有key”的枚举对象    
    public synchronized Enumeration<K> keys() {    
        return this.<K>getEnumeration(KEYS);    
    }    
   
    // 返回“所有value”的枚举对象    
    public synchronized Enumeration<V> elements() {    
        return this.<V>getEnumeration(VALUES);    
    }    
   
    // 判断Hashtable是否包含“值(value)”    
    public synchronized boolean contains(Object value) {    
        //注意,Hashtable中的value不能是null,    
        // 若是null的话,抛出异常!    
        if (value == null) {    
            throw new NullPointerException();    
        }    
   
        // 从后向前遍历table数组中的元素(Entry)    
        // 对于每个Entry(单向链表),逐个遍历,判断节点的值是否等于value    
        Entry tab[] = table;    
        for (int i = tab.length ; i-- > 0 ;) {    
            for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {    
                if (e.value.equals(value)) {    
                    return true;    
                }    
            }    
        }    
        return false;    
    }    
   
    public boolean containsValue(Object value) {    
        return contains(value);    
    }    
   
    // 判断Hashtable是否包含key    
    public synchronized boolean containsKey(Object key) {    
        Entry tab[] = table;    
        //计算hash值,直接用key的hashCode代替  
        int hash = key.hashCode();      
        // 计算在数组中的索引值   
        int index = (hash & 0x7FFFFFFF) % tab.length;    
        // 找到“key对应的Entry(链表)”,然后在链表中找出“哈希值”和“键值”与key都相等的元素    
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {    
            if ((e.hash == hash) && e.key.equals(key)) {    
                return true;    
            }    
        }    
        return false;    
    }    
   
    // 返回key对应的value,没有的话返回null    
    public synchronized V get(Object key) {    
        Entry tab[] = table;    
        int hash = hash(key);
        // 计算索引值,    
        int index = (hash & 0x7FFFFFFF) % tab.length;    
        // 找到“key对应的Entry(链表)”,然后在链表中找出“哈希值”和“键值”与key都相等的元素    
        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;    
    }    
   
    // 调整Hashtable的长度,将长度变成原来的2倍+1   
    protected void rehash() {    
        int oldCapacity = table.length;    
        Entry[] oldMap = table;    
   
        //创建新容量大小的Entry数组  
        int newCapacity = oldCapacity * 2 + 1;    
        Entry[] newMap = new Entry[newCapacity];    
   
        modCount++;    
        threshold = (int)(newCapacity * loadFactor);    
        table = newMap;    
          
        //将“旧的Hashtable”中的元素复制到“新的Hashtable”中  
        for (int i = oldCapacity ; i-- > 0 ;) {    
            for (Entry<K,V> old = oldMap[i] ; old != null ; ) {    
                Entry<K,V> e = old;    
                old = old.next;    
                //重新计算index  
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;    
                e.next = newMap[index];    
                newMap[index] = e;    
            }    
        }    
    }    
   
    // 将“key-value”添加到Hashtable中    
    public synchronized V put(K key, V value) {    
        // Hashtable中不能插入value为null的元素!!!    
        if (value == null) {    
            throw new NullPointerException();    
        }    
   
        // 若“Hashtable中已存在键为key的键值对”,    
        // 则用“新的value”替换“旧的value”    
        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;    
                }    
        }    
   
        // 若“Hashtable中不存在键为key的键值对”,  
        // 将“修改统计数”+1    
        modCount++;    
        //  若“Hashtable实际容量” > “阈值”(阈值=总的容量 * 加载因子)    
        //  则调整Hashtable的大小    
        if (count >= threshold) {  
            rehash();    
   
            tab = table;    
            index = (hash & 0x7FFFFFFF) % tab.length;    
        }    
   
        //将新的key-value对插入到tab[index]处(即链表的头结点)  
        Entry<K,V> e = tab[index];           
        tab[index] = new Entry<K,V>(hash, key, value, e);    
        count++;    
        return null;    
    }    
   
    // 删除Hashtable中键为key的元素    
    public synchronized V remove(Object key) {    
        Entry tab[] = table;    
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;    
          
        //从table[index]链表中找出要删除的节点,并删除该节点。  
        //因为是单链表,因此要保留带删节点的前一个节点,才能有效地删除节点  
        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;    
    }    
   
    // 将“Map(t)”的中全部元素逐一添加到Hashtable中    
    public synchronized void putAll(Map<? extends K, ? extends V> t) {    
        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())    
            put(e.getKey(), e.getValue());    
    }    
   
    // 清空Hashtable    
    // 将Hashtable的table数组的值全部设为null    
    public synchronized void clear() {    
        Entry tab[] = table;    
        modCount++;    
        for (int index = tab.length; --index >= 0; )    
            tab[index] = null;    
        count = 0;    
    }    
   
    // 克隆一个Hashtable,并以Object的形式返回。    
    public synchronized Object clone() {    
        try {    
            Hashtable<K,V> t = (Hashtable<K,V>) super.clone();    
            t.table = new Entry[table.length];    
            for (int i = table.length ; i-- > 0 ; ) {    
                t.table[i] = (table[i] != null)    
                ? (Entry<K,V>) table[i].clone() : null;    
            }    
            t.keySet = null;    
            t.entrySet = null;    
            t.values = null;    
            t.modCount = 0;    
            return t;    
        } catch (CloneNotSupportedException e) {     
            throw new InternalError();    
        }    
    }    
   
    public synchronized String toString() {    
        int max = size() - 1;    
        if (max == -1)    
            return "{}";    
   
        StringBuilder sb = new StringBuilder();    
        Iterator<Map.Entry<K,V>> it = entrySet().iterator();    
   
        sb.append('{');    
        for (int i = 0; ; i++) {    
            Map.Entry<K,V> e = it.next();    
            K key = e.getKey();    
            V value = e.getValue();    
            sb.append(key   == this ? "(this Map)" : key.toString());    
            sb.append('=');    
            sb.append(value == this ? "(this Map)" : value.toString());    
   
            if (i == max)    
                return sb.append('}').toString();    
            sb.append(", ");    
        }    
    }    
   
    // 获取Hashtable的枚举类对象    
    // 若Hashtable的实际大小为0,则返回“空枚举类”对象;    
    // 否则,返回正常的Enumerator的对象。   
    private <T> Enumeration<T> getEnumeration(int type) {    
    if (count == 0) {    
        return (Enumeration<T>)emptyEnumerator;    
    } else {    
        return new Enumerator<T>(type, false);    
    }    
    }    
   
    // 获取Hashtable的迭代器    
    // 若Hashtable的实际大小为0,则返回“空迭代器”对象;    
    // 否则,返回正常的Enumerator的对象。(Enumerator实现了迭代器和枚举两个接口)    
    private <T> Iterator<T> getIterator(int type) {    
        if (count == 0) {    
            return (Iterator<T>) emptyIterator;    
        } else {    
            return new Enumerator<T>(type, true);    
        }    
    }    
   
    // Hashtable的“key的集合”。它是一个Set,没有重复元素    
    private transient volatile Set<K> keySet = null;    
    // Hashtable的“key-value的集合”。它是一个Set,没有重复元素    
    private transient volatile Set<Map.Entry<K,V>> entrySet = null;    
    // Hashtable的“key-value的集合”。它是一个Collection,可以有重复元素    
    private transient volatile Collection<V> values = null;    
   
    // 返回一个被synchronizedSet封装后的KeySet对象    
    // synchronizedSet封装的目的是对KeySet的所有方法都添加synchronized,实现多线程同步    
    public Set<K> keySet() {    
        if (keySet == null)    
            keySet = Collections.synchronizedSet(new KeySet(), this);    
        return keySet;    
    }    
   
    // Hashtable的Key的Set集合。    
    // KeySet继承于AbstractSet,所以,KeySet中的元素没有重复的。    
    private class KeySet extends AbstractSet<K> {    
        public Iterator<K> iterator() {    
            return getIterator(KEYS);    
        }    
        public int size() {    
            return count;    
        }    
        public boolean contains(Object o) {    
            return containsKey(o);    
        }    
        public boolean remove(Object o) {    
            return Hashtable.this.remove(o) != null;    
        }    
        public void clear() {    
            Hashtable.this.clear();    
        }    
    }    
   
    // 返回一个被synchronizedSet封装后的EntrySet对象    
    // synchronizedSet封装的目的是对EntrySet的所有方法都添加synchronized,实现多线程同步    
    public Set<Map.Entry<K,V>> entrySet() {    
        if (entrySet==null)    
            entrySet = Collections.synchronizedSet(new EntrySet(), this);    
        return entrySet;    
    }    
   
    // Hashtable的Entry的Set集合。    
    // EntrySet继承于AbstractSet,所以,EntrySet中的元素没有重复的。    
    private class EntrySet extends AbstractSet<Map.Entry<K,V>> {    
        public Iterator<Map.Entry<K,V>> iterator() {    
            return getIterator(ENTRIES);    
        }    
   
        public boolean add(Map.Entry<K,V> o) {    
            return super.add(o);    
        }    
   
        // 查找EntrySet中是否包含Object(0)    
        // 首先,在table中找到o对应的Entry链表    
        // 然后,查找Entry链表中是否存在Object    
        public boolean contains(Object o) {    
            if (!(o instanceof Map.Entry))    
                return false;    
            Map.Entry entry = (Map.Entry)o;    
            Object key = entry.getKey();    
            Entry[] tab = table;    
            int hash = hash(key);
            int index = (hash & 0x7FFFFFFF) % tab.length;    
   
            for (Entry e = tab[index]; e != null; e = e.next)    
                if (e.hash==hash && e.equals(entry))    
                    return true;    
            return false;    
        }    
   
        // 删除元素Object(0)    
        // 首先,在table中找到o对应的Entry链表  
        // 然后,删除链表中的元素Object    
        public boolean remove(Object o) {    
            if (!(o instanceof Map.Entry))    
                return false;    
            Map.Entry<K,V> entry = (Map.Entry<K,V>) o;    
            K key = entry.getKey();    
            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.equals(entry)) {    
                    modCount++;    
                    if (prev != null)    
                        prev.next = e.next;    
                    else   
                        tab[index] = e.next;    
   
                    count--;    
                    e.value = null;    
                    return true;    
                }    
            }    
            return false;    
        }    
   
        public int size() {    
            return count;    
        }    
   
        public void clear() {    
            Hashtable.this.clear();    
        }    
    }    
   
    // 返回一个被synchronizedCollection封装后的ValueCollection对象    
    // synchronizedCollection封装的目的是对ValueCollection的所有方法都添加synchronized,实现多线程同步    
    public Collection<V> values() {    
    if (values==null)    
        values = Collections.synchronizedCollection(new ValueCollection(),    
                                                        this);    
        return values;    
    }    
   
    // Hashtable的value的Collection集合。    
    // ValueCollection继承于AbstractCollection,所以,ValueCollection中的元素可以重复的。    
    private class ValueCollection extends AbstractCollection<V> {    
        public Iterator<V> iterator() {    
        return getIterator(VALUES);    
        }    
        public int size() {    
            return count;    
        }    
        public boolean contains(Object o) {    
            return containsValue(o);    
        }    
        public void clear() {    
            Hashtable.this.clear();    
        }    
    }    
   
    // 重新equals()函数    
    // 若两个Hashtable的所有key-value键值对都相等,则判断它们两个相等    
    public synchronized boolean equals(Object o) {    
        if (o == this)    
            return true;    
   
        if (!(o instanceof Map))    
            return false;    
        Map<K,V> t = (Map<K,V>) o;    
        if (t.size() != size())    
            return false;    
   
        try {    
            // 通过迭代器依次取出当前Hashtable的key-value键值对    
            // 并判断该键值对,存在于Hashtable中。    
            // 若不存在,则立即返回false;否则,遍历完“当前Hashtable”并返回true。    
            Iterator<Map.Entry<K,V>> i = entrySet().iterator();    
            while (i.hasNext()) {    
                Map.Entry<K,V> e = i.next();    
                K key = e.getKey();    
                V value = e.getValue();    
                if (value == null) {    
                    if (!(t.get(key)==null && t.containsKey(key)))    
                        return false;    
                } else {    
                    if (!value.equals(t.get(key)))    
                        return false;    
                }    
            }    
        } catch (ClassCastException unused)   {    
            return false;    
        } catch (NullPointerException unused) {    
            return false;    
        }    
   
        return true;    
    }    
   
    // 计算Entry的hashCode    
    // 若 Hashtable的实际大小为0 或者 加载因子<0,则返回0。    
    // 否则,返回“Hashtable中的每个Entry的key和value的异或值 的总和”。    
    public synchronized int hashCode() {    
        int h = 0;    
        if (count == 0 || loadFactor < 0)    
            return h;  // Returns zero    
   
        loadFactor = -loadFactor;  // Mark hashCode computation in progress    
        Entry[] tab = table;    
        for (int i = 0; i < tab.length; i++)    
            for (Entry e = tab[i]; e != null; e = e.next)    
                h += e.key.hashCode() ^ e.value.hashCode();    
        loadFactor = -loadFactor;  // Mark hashCode computation complete    
   
        return h;    
    }    
   
    // java.io.Serializable的写入函数    
    // 将Hashtable的“总的容量,实际容量,所有的Entry”都写入到输出流中    
    private synchronized void writeObject(java.io.ObjectOutputStream s)    
        throws IOException    
    {    
        // Write out the length, threshold, loadfactor    
        s.defaultWriteObject();    
   
        // Write out length, count of elements and then the key/value objects    
        s.writeInt(table.length);    
        s.writeInt(count);    
        for (int index = table.length-1; index >= 0; index--) {    
            Entry entry = table[index];    
   
            while (entry != null) {    
            s.writeObject(entry.key);    
            s.writeObject(entry.value);    
            entry = entry.next;    
            }    
        }    
    }    
   
    // java.io.Serializable的读取函数:根据写入方式读出    
    // 将Hashtable的“总的容量,实际容量,所有的Entry”依次读出    
    private void readObject(java.io.ObjectInputStream s)    
         throws IOException, ClassNotFoundException    
    {    
        // Read in the length, threshold, and loadfactor    
        s.defaultReadObject();    
   
        // Read the original length of the array and number of elements    
        int origlength = s.readInt();    
        int elements = s.readInt();    
   
        // Compute new size with a bit of room 5% to grow but    
        // no larger than the original size.  Make the length    
        // odd if it's large enough, this helps distribute the entries.    
        // Guard against the length ending up zero, that's not valid.    
        int length = (int)(elements * loadFactor) + (elements / 20) + 3;    
        if (length > elements && (length & 1) == 0)    
            length--;    
        if (origlength > 0 && length > origlength)    
            length = origlength;    
   
        Entry[] table = new Entry[length];    
        count = 0;    
   
        // Read the number of elements and then all the key/value objects    
        for (; elements > 0; elements--) {    
            K key = (K)s.readObject();    
            V value = (V)s.readObject();    
                // synch could be eliminated for performance    
                reconstitutionPut(table, key, value);    
        }    
        this.table = table;    
    }    
   
    private void reconstitutionPut(Entry[] tab, K key, V value)    
        throws StreamCorruptedException    
    {    
        if (value == null) {    
            throw new java.io.StreamCorruptedException();    
        }    
        // Makes sure the key is not already in the hashtable.    
        // This should not happen in deserialized version.    
        int hash = key.hashCode();    
        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)) {    
                throw new java.io.StreamCorruptedException();    
            }    
        }    
        // Creates the new entry.    
        Entry<K,V> e = tab[index];    
        tab[index] = new Entry<K,V>(hash, key, value, e);    
        count++;    
    }    
   
    // Hashtable的Entry节点,它本质上是一个单向链表。    
    // 也因此,我们才能推断出Hashtable是由拉链法实现的散列表    
    private static class Entry<K,V> implements Map.Entry<K,V> {    
        // 哈希值    
        int hash;    
        K key;    
        V value;    
        // 指向的下一个Entry,即链表的下一个节点    
        Entry<K,V> next;    
   
        // 构造函数    
        protected Entry(int hash, K key, V value, Entry<K,V> next) {    
            this.hash = hash;    
            this.key = key;    
            this.value = value;    
            this.next = next;    
        }    
   
        protected Object clone() {    
            return new Entry<K,V>(hash, key, value,    
                  (next==null ? null : (Entry<K,V>) next.clone()));    
        }    
   
        public K getKey() {    
            return key;    
        }    
   
        public V getValue() {    
            return value;    
        }    
   
        // 设置value。若value是null,则抛出异常。    
        public V setValue(V value) {    
            if (value == null)    
                throw new NullPointerException();    
   
            V oldValue = this.value;    
            this.value = value;    
            return oldValue;    
        }    
   
        // 覆盖equals()方法,判断两个Entry是否相等。    
        // 若两个Entry的key和value都相等,则认为它们相等。    
        public boolean equals(Object o) {    
            if (!(o instanceof Map.Entry))    
                return false;    
            Map.Entry e = (Map.Entry)o;    
   
            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&    
               (value==null ? e.getValue()==null : value.equals(e.getValue()));    
        }    
   
        public int hashCode() {    
            return hash ^ (value==null ? 0 : value.hashCode());    
        }    
   
        public String toString() {    
            return key.toString()+"="+value.toString();    
        }    
    }    
   
    private static final int KEYS = 0;    
    private static final int VALUES = 1;    
    private static final int ENTRIES = 2;    
   
    // Enumerator的作用是提供了“通过elements()遍历Hashtable的接口” 和 “通过entrySet()遍历Hashtable的接口”。    
    private class Enumerator<T> implements Enumeration<T>, Iterator<T> {    
        // 指向Hashtable的table    
        Entry[] table = Hashtable.this.table;    
        // Hashtable的总的大小    
        int index = table.length;    
        Entry<K,V> entry = null;    
        Entry<K,V> lastReturned = null;    
        int type;    
   
        // Enumerator是 “迭代器(Iterator)” 还是 “枚举类(Enumeration)”的标志    
        // iterator为true,表示它是迭代器;否则,是枚举类。    
        boolean iterator;    
   
        // 在将Enumerator当作迭代器使用时会用到,用来实现fail-fast机制。    
        protected int expectedModCount = modCount;    
   
        Enumerator(int type, boolean iterator) {    
            this.type = type;    
            this.iterator = iterator;    
        }    
   
        // 从遍历table的数组的末尾向前查找,直到找到不为null的Entry。    
        public boolean hasMoreElements() {    
            Entry<K,V> e = entry;    
            int i = index;    
            Entry[] t = table;    
            /* Use locals for faster loop iteration */   
            while (e == null && i > 0) {    
                e = t[--i];    
            }    
            entry = e;    
            index = i;    
            return e != null;    
        }    
   
        // 获取下一个元素    
        // 注意:从hasMoreElements() 和nextElement() 可以看出“Hashtable的elements()遍历方式”    
        // 首先,从后向前的遍历table数组。table数组的每个节点都是一个单向链表(Entry)。    
        // 然后,依次向后遍历单向链表Entry。    
        public T nextElement() {    
            Entry<K,V> et = entry;    
            int i = index;    
            Entry[] t = table;    
            /* Use locals for faster loop iteration */   
            while (et == null && i > 0) {    
                et = t[--i];    
            }    
            entry = et;    
            index = i;    
            if (et != null) {    
                Entry<K,V> e = lastReturned = entry;    
                entry = e.next;    
                return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);    
            }    
            throw new NoSuchElementException("Hashtable Enumerator");    
        }    
   
        // 迭代器Iterator的判断是否存在下一个元素    
        // 实际上,它是调用的hasMoreElements()    
        public boolean hasNext() {    
            return hasMoreElements();    
        }    
   
        // 迭代器获取下一个元素    
        // 实际上,它是调用的nextElement()    
        public T next() {    
            if (modCount != expectedModCount)    
                throw new ConcurrentModificationException();    
            return nextElement();    
        }    
   
        // 迭代器的remove()接口。    
        // 首先,它在table数组中找出要删除元素所在的Entry,    
        // 然后,删除单向链表Entry中的元素。    
        public void remove() {    
            if (!iterator)    
                throw new UnsupportedOperationException();    
            if (lastReturned == null)    
                throw new IllegalStateException("Hashtable Enumerator");    
            if (modCount != expectedModCount)    
                throw new ConcurrentModificationException();    
   
            synchronized(Hashtable.this) {    
                Entry[] tab = Hashtable.this.table;    
                int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;    
   
                for (Entry<K,V> e = tab[index], prev = null; e != null;    
                     prev = e, e = e.next) {    
                    if (e == lastReturned) {    
                        modCount++;    
                        expectedModCount++;    
                        if (prev == null)    
                            tab[index] = e.next;    
                        else   
                            prev.next = e.next;    
                        count--;    
                        lastReturned = null;    
                        return;    
                    }    
                }    
                throw new ConcurrentModificationException();    
            }    
        }    
    }    
   
   
    private static Enumeration emptyEnumerator = new EmptyEnumerator();    
    private static Iterator emptyIterator = new EmptyIterator();    
   
    // 空枚举类    
    // 当Hashtable的实际大小为0;此时,又要通过Enumeration遍历Hashtable时,返回的是“空枚举类”的对象。    
    private static class EmptyEnumerator implements Enumeration<Object> {    
   
        EmptyEnumerator() {    
        }    
   
        // 空枚举类的hasMoreElements() 始终返回false    
        public boolean hasMoreElements() {    
            return false;    
        }    
   
        // 空枚举类的nextElement() 抛出异常    
        public Object nextElement() {    
            throw new NoSuchElementException("Hashtable Enumerator");    
        }    
    }    
   
   
    // 空迭代器    
    // 当Hashtable的实际大小为0;此时,又要通过迭代器遍历Hashtable时,返回的是“空迭代器”的对象。    
    private static class EmptyIterator implements Iterator<Object> {    
   
        EmptyIterator() {    
        }    
   
        public boolean hasNext() {    
            return false;    
        }    
   
        public Object next() {    
            throw new NoSuchElementException("Hashtable Iterator");    
        }    
   
        public void remove() {    
            throw new IllegalStateException("Hashtable Iterator");    
        }    
   
    }    
}   

是最基本的集合接口

继承的接口:Iterable

子接口:List、Set、Queue等

遍历Collection中的每一个元素

它支持一个Iterator()方法,该方法返回一个迭代子,该迭代子可逐一访问Collection中每一个元素

Iterator it = collection.iterator(); // 获得一个迭代子
    while(it.hasNext())  
    {
        Object obj = it.next(); // 得到下一个元素
    }

方法:

retainAll(Collection<?extends E>c);  //保留,交运算
addAll(Collection<?extends E>c);       //添加,并运算
removeAll(Collection<?extends E>c);     //移除,减运算

LinkedList是基于双向循环链表实现的,除了可以当作链表来操作外,它还可以当作栈、队列和双端队列来使用。

非线程安全,单线程下使用

LinkedList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了Cloneable接口,能被克隆。

  • 是一个类
  • 实现的接口:List、Collection、Iterable、Serializable、Cloneable、Deque,Queue
  • 子类:没有子类

添加元素方法:

boolean add(E e) 添加到链表末尾

void add(int index, E e) 添加到指定位置

boolean addAll(int index, Collection<? extends E> c)

boolean addAll(Collection<? extends E> c)

package java.util;    
   
public class LinkedList<E>    
    extends AbstractSequentialList<E>    
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable    
{    
    // 链表的表头,表头不包含任何数据。Entry是个链表类数据结构。    
    private transient Entry<E> header = new Entry<E>(null, null, null);    
   
    // LinkedList中元素个数    
    private transient int size = 0;    
   
    // 默认构造函数:创建一个空的链表    
    public LinkedList() {    
        header.next = header.previous = header;    
    }    
   
    // 包含“集合”的构造函数:创建一个包含“集合”的LinkedList    
    public LinkedList(Collection<? extends E> c) {    
        this();    
        addAll(c);    
    }    
   
    // 获取LinkedList的第一个元素    
    public E getFirst() {    
        if (size==0)    
            throw new NoSuchElementException();    
   
        // 链表的表头header中不包含数据。    
        // 这里返回header所指下一个节点所包含的数据。    
        return header.next.element;    
    }    
   
    // 获取LinkedList的最后一个元素    
    public E getLast()  {    
        if (size==0)    
            throw new NoSuchElementException();    
   
        // 由于LinkedList是双向链表;而表头header不包含数据。    
        // 因而,这里返回表头header的前一个节点所包含的数据。    
        return header.previous.element;    
    }    
   
    // 删除LinkedList的第一个元素    
    public E removeFirst() {    
        return remove(header.next);    
    }    
   
    // 删除LinkedList的最后一个元素    
    public E removeLast() {    
        return remove(header.previous);    
    }    
   
    // 将元素添加到LinkedList的起始位置    
    public void addFirst(E e) {    
        addBefore(e, header.next);    
    }    
   
    // 将元素添加到LinkedList的结束位置    
    public void addLast(E e) {    
        addBefore(e, header);    
    }    
   
    // 判断LinkedList是否包含元素(o)    
    public boolean contains(Object o) {    
        return indexOf(o) != -1;    
    }    
   
    // 返回LinkedList的大小    
    public int size() {    
        return size;    
    }    
   
    // 将元素(E)添加到LinkedList中    
    public boolean add(E e) {    
        // 将节点(节点数据是e)添加到表头(header)之前。    
        // 即,将节点添加到双向链表的末端。    
        addBefore(e, header);    
        return true;    
    }    
   
    // 从LinkedList中删除元素(o)    
    // 从链表开始查找,如存在元素(o)则删除该元素并返回true;    
    // 否则,返回false。    
    public boolean remove(Object o) {    
        if (o==null) {    
            // 若o为null的删除情况    
            for (Entry<E> e = header.next; e != header; e = e.next) {    
                if (e.element==null) {    
                    remove(e);    
                    return true;    
                }    
            }    
        } else {    
            // 若o不为null的删除情况    
            for (Entry<E> e = header.next; e != header; e = e.next) {    
                if (o.equals(e.element)) {    
                    remove(e);    
                    return true;    
                }    
            }    
        }    
        return false;    
    }    
   
    // 将“集合(c)”添加到LinkedList中。    
    // 实际上,是从双向链表的末尾开始,将“集合(c)”添加到双向链表中。    
    public boolean addAll(Collection<? extends E> c) {    
        return addAll(size, c);    
    }    
   
    // 从双向链表的index开始,将“集合(c)”添加到双向链表中。    
    public boolean addAll(int index, Collection<? extends E> c) {    
        if (index < 0 || index > size)    
            throw new IndexOutOfBoundsException("Index: "+index+    
                                                ", Size: "+size);    
        Object[] a = c.toArray();    
        // 获取集合的长度    
        int numNew = a.length;    
        if (numNew==0)    
            return false;    
        modCount++;    
   
        // 设置“当前要插入节点的后一个节点”    
        Entry<E> successor = (index==size ? header : entry(index));    
        // 设置“当前要插入节点的前一个节点”    
        Entry<E> predecessor = successor.previous;    
        // 将集合(c)全部插入双向链表中    
        for (int i=0; i<numNew; i++) {    
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);    
            predecessor.next = e;    
            predecessor = e;    
        }    
        successor.previous = predecessor;    
   
        // 调整LinkedList的实际大小    
        size += numNew;    
        return true;    
    }    
   
    // 清空双向链表    
    public void clear() {    
        Entry<E> e = header.next;    
        // 从表头开始,逐个向后遍历;对遍历到的节点执行一下操作:    
        // (01) 设置前一个节点为null     
        // (02) 设置当前节点的内容为null     
        // (03) 设置后一个节点为“新的当前节点”    
        while (e != header) {    
            Entry<E> next = e.next;    
            e.next = e.previous = null;    
            e.element = null;    
            e = next;    
        }    
        header.next = header.previous = header;    
        // 设置大小为0    
        size = 0;    
        modCount++;    
    }    
   
    // 返回LinkedList指定位置的元素    
    public E get(int index) {    
        return entry(index).element;    
    }    
   
    // 设置index位置对应的节点的值为element    
    public E set(int index, E element) {    
        Entry<E> e = entry(index);    
        E oldVal = e.element;    
        e.element = element;    
        return oldVal;    
    }    
     
    // 在index前添加节点,且节点的值为element    
    public void add(int index, E element) {    
        addBefore(element, (index==size ? header : entry(index)));    
    }    
   
    // 删除index位置的节点    
    public E remove(int index) {    
        return remove(entry(index));    
    }    
   
    // 获取双向链表中指定位置的节点    
    private Entry<E> entry(int index) {    
        if (index < 0 || index >= size)    
            throw new IndexOutOfBoundsException("Index: "+index+    
                                                ", Size: "+size);    
        Entry<E> e = header;    
        // 获取index处的节点。    
        // 若index < 双向链表长度的1/2,则从前先后查找;    
        // 否则,从后向前查找。    
        if (index < (size >> 1)) {    
            for (int i = 0; i <= index; i++)    
                e = e.next;    
        } else {    
            for (int i = size; i > index; i--)    
                e = e.previous;    
        }    
        return e;    
    }    
   
    // 从前向后查找,返回“值为对象(o)的节点对应的索引”    
    // 不存在就返回-1    
    public int indexOf(Object o) {    
        int index = 0;    
        if (o==null) {    
            for (Entry e = header.next; e != header; e = e.next) {    
                if (e.element==null)    
                    return index;    
                index++;    
            }    
        } else {    
            for (Entry e = header.next; e != header; e = e.next) {    
                if (o.equals(e.element))    
                    return index;    
                index++;    
            }    
        }    
        return -1;    
    }    
   
    // 从后向前查找,返回“值为对象(o)的节点对应的索引”    
    // 不存在就返回-1    
    public int lastIndexOf(Object o) {    
        int index = size;    
        if (o==null) {    
            for (Entry e = header.previous; e != header; e = e.previous) {    
                index--;    
                if (e.element==null)    
                    return index;    
            }    
        } else {    
            for (Entry e = header.previous; e != header; e = e.previous) {    
                index--;    
                if (o.equals(e.element))    
                    return index;    
            }    
        }    
        return -1;    
    }    
   
    // 返回第一个节点    
    // 若LinkedList的大小为0,则返回null    
    public E peek() {    
        if (size==0)    
            return null;    
        return getFirst();    
    }    
   
    // 返回第一个节点    
    // 若LinkedList的大小为0,则抛出异常    
    public E element() {    
        return getFirst();    
    }    
   
    // 删除并返回第一个节点    
    // 若LinkedList的大小为0,则返回null    
    public E poll() {    
        if (size==0)    
            return null;    
        return removeFirst();    
    }    
   
    // 将e添加双向链表末尾    
    public boolean offer(E e) {    
        return add(e);    
    }    
   
    // 将e添加双向链表开头    
    public boolean offerFirst(E e) {    
        addFirst(e);    
        return true;    
    }    
   
    // 将e添加双向链表末尾    
    public boolean offerLast(E e) {    
        addLast(e);    
        return true;    
    }    
   
    // 返回第一个节点    
    // 若LinkedList的大小为0,则返回null    
    public E peekFirst() {    
        if (size==0)    
            return null;    
        return getFirst();    
    }    
   
    // 返回最后一个节点    
    // 若LinkedList的大小为0,则返回null    
    public E peekLast() {    
        if (size==0)    
            return null;    
        return getLast();    
    }    
   
    // 删除并返回第一个节点    
    // 若LinkedList的大小为0,则返回null    
    public E pollFirst() {    
        if (size==0)    
            return null;    
        return removeFirst();    
    }    
   
    // 删除并返回最后一个节点    
    // 若LinkedList的大小为0,则返回null    
    public E pollLast() {    
        if (size==0)    
            return null;    
        return removeLast();    
    }    
   
    // 将e插入到双向链表开头    
    public void push(E e) {    
        addFirst(e);    
    }    
   
    // 删除并返回第一个节点    
    public E pop() {    
        return removeFirst();    
    }    
   
    // 从LinkedList开始向后查找,删除第一个值为元素(o)的节点    
    // 从链表开始查找,如存在节点的值为元素(o)的节点,则删除该节点    
    public boolean removeFirstOccurrence(Object o) {    
        return remove(o);    
    }    
   
    // 从LinkedList末尾向前查找,删除第一个值为元素(o)的节点    
    // 从链表开始查找,如存在节点的值为元素(o)的节点,则删除该节点    
    public boolean removeLastOccurrence(Object o) {    
        if (o==null) {    
            for (Entry<E> e = header.previous; e != header; e = e.previous) {    
                if (e.element==null) {    
                    remove(e);    
                    return true;    
                }    
            }    
        } else {    
            for (Entry<E> e = header.previous; e != header; e = e.previous) {    
                if (o.equals(e.element)) {    
                    remove(e);    
                    return true;    
                }    
            }    
        }    
        return false;    
    }    
   
    // 返回“index到末尾的全部节点”对应的ListIterator对象(List迭代器)    
    public ListIterator<E> listIterator(int index) {    
        return new ListItr(index);    
    }    
   
    // List迭代器    
    private class ListItr implements ListIterator<E> {    
        // 上一次返回的节点    
        private Entry<E> lastReturned = header;    
        // 下一个节点    
        private Entry<E> next;    
        // 下一个节点对应的索引值    
        private int nextIndex;    
        // 期望的改变计数。用来实现fail-fast机制。    
        private int expectedModCount = modCount;    
   
        // 构造函数。    
        // 从index位置开始进行迭代    
        ListItr(int index) {    
            // index的有效性处理    
            if (index < 0 || index > size)    
                throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);    
            // 若 “index 小于 ‘双向链表长度的一半’”,则从第一个元素开始往后查找;    
            // 否则,从最后一个元素往前查找。    
            if (index < (size >> 1)) {    
                next = header.next;    
                for (nextIndex=0; nextIndex<index; nextIndex++)    
                    next = next.next;    
            } else {    
                next = header;    
                for (nextIndex=size; nextIndex>index; nextIndex--)    
                    next = next.previous;    
            }    
        }    
   
        // 是否存在下一个元素    
        public boolean hasNext() {    
            // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。    
            return nextIndex != size;    
        }    
   
        // 获取下一个元素    
        public E next() {    
            checkForComodification();    
            if (nextIndex == size)    
                throw new NoSuchElementException();    
   
            lastReturned = next;    
            // next指向链表的下一个元素    
            next = next.next;    
            nextIndex++;    
            return lastReturned.element;    
        }    
   
        // 是否存在上一个元素    
        public boolean hasPrevious() {    
            // 通过元素索引是否等于0,来判断是否达到开头。    
            return nextIndex != 0;    
        }    
   
        // 获取上一个元素    
        public E previous() {    
            if (nextIndex == 0)    
            throw new NoSuchElementException();    
   
            // next指向链表的上一个元素    
            lastReturned = next = next.previous;    
            nextIndex--;    
            checkForComodification();    
            return lastReturned.element;    
        }    
   
        // 获取下一个元素的索引    
        public int nextIndex() {    
            return nextIndex;    
        }    
   
        // 获取上一个元素的索引    
        public int previousIndex() {    
            return nextIndex-1;    
        }    
   
        // 删除当前元素。    
        // 删除双向链表中的当前节点    
        public void remove() {    
            checkForComodification();    
            Entry<E> lastNext = lastReturned.next;    
            try {    
                LinkedList.this.remove(lastReturned);    
            } catch (NoSuchElementException e) {    
                throw new IllegalStateException();    
            }    
            if (next==lastReturned)    
                next = lastNext;    
            else   
                nextIndex--;    
            lastReturned = header;    
            expectedModCount++;    
        }    
   
        // 设置当前节点为e    
        public void set(E e) {    
            if (lastReturned == header)    
                throw new IllegalStateException();    
            checkForComodification();    
            lastReturned.element = e;    
        }    
   
        // 将e添加到当前节点的前面    
        public void add(E e) {    
            checkForComodification();    
            lastReturned = header;    
            addBefore(e, next);    
            nextIndex++;    
            expectedModCount++;    
        }    
   
        // 判断 “modCount和expectedModCount是否相等”,依次来实现fail-fast机制。    
        final void checkForComodification() {    
            if (modCount != expectedModCount)    
            throw new ConcurrentModificationException();    
        }    
    }    
   
    // 双向链表的节点所对应的数据结构。    
    // 包含3部分:上一节点,下一节点,当前节点值。    
    private static class Entry<E> {    
        // 当前节点所包含的值    
        E element;    
        // 下一个节点    
        Entry<E> next;    
        // 上一个节点    
        Entry<E> previous;    
   
        /**   
         * 链表节点的构造函数。   
         * 参数说明:   
         *   element  —— 节点所包含的数据   
         *   next      —— 下一个节点   
         *   previous —— 上一个节点   
         */   
        Entry(E element, Entry<E> next, Entry<E> previous) {    
            this.element = element;    
            this.next = next;    
            this.previous = previous;    
        }    
    }    
   
    // 将节点(节点数据是e)添加到entry节点之前。    
    private Entry<E> addBefore(E e, Entry<E> entry) {    
        // 新建节点newEntry,将newEntry插入到节点e之前;并且设置newEntry的数据是e    
        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);    
        newEntry.previous.next = newEntry;    
        newEntry.next.previous = newEntry;    
        // 修改LinkedList大小    
        size++;    
        // 修改LinkedList的修改统计数:用来实现fail-fast机制。    
        modCount++;    
        return newEntry;    
    }    
   
    // 将节点从链表中删除    
    private E remove(Entry<E> e) {    
        if (e == header)    
            throw new NoSuchElementException();    
   
        E result = e.element;    
        e.previous.next = e.next;    
        e.next.previous = e.previous;    
        e.next = e.previous = null;    
        e.element = null;    
        size--;    
        modCount++;    
        return result;    
    }    
   
    // 反向迭代器    
    public Iterator<E> descendingIterator() {    
        return new DescendingIterator();    
    }    
   
    // 反向迭代器实现类。    
    private class DescendingIterator implements Iterator {    
        final ListItr itr = new ListItr(size());    
        // 反向迭代器是否下一个元素。    
        // 实际上是判断双向链表的当前节点是否达到开头    
        public boolean hasNext() {    
            return itr.hasPrevious();    
        }    
        // 反向迭代器获取下一个元素。    
        // 实际上是获取双向链表的前一个节点    
        public E next() {    
            return itr.previous();    
        }    
        // 删除当前节点    
        public void remove() {    
            itr.remove();    
        }    
    }    
   
   
    // 返回LinkedList的Object[]数组    
    public Object[] toArray() {    
    // 新建Object[]数组    
    Object[] result = new Object[size];    
        int i = 0;    
        // 将链表中所有节点的数据都添加到Object[]数组中    
        for (Entry<E> e = header.next; e != header; e = e.next)    
            result[i++] = e.element;    
    return result;    
    }    
   
    // 返回LinkedList的模板数组。所谓模板数组,即可以将T设为任意的数据类型    
    public <T> T[] toArray(T[] a) {    
        // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)    
        // 则新建一个T[]数组,T[]的大小为LinkedList大小,并将该T[]赋值给a。    
        if (a.length < size)    
            a = (T[])java.lang.reflect.Array.newInstance(    
                                a.getClass().getComponentType(), size);    
        // 将链表中所有节点的数据都添加到数组a中    
        int i = 0;    
        Object[] result = a;    
        for (Entry<E> e = header.next; e != header; e = e.next)    
            result[i++] = e.element;    
   
        if (a.length > size)    
            a[size] = null;    
   
        return a;    
    }    
   
   
    // 克隆函数。返回LinkedList的克隆对象。    
    public Object clone() {    
        LinkedList<E> clone = null;    
        // 克隆一个LinkedList克隆对象    
        try {    
            clone = (LinkedList<E>) super.clone();    
        } catch (CloneNotSupportedException e) {    
            throw new InternalError();    
        }    
   
        // 新建LinkedList表头节点    
        clone.header = new Entry<E>(null, null, null);    
        clone.header.next = clone.header.previous = clone.header;    
        clone.size = 0;    
        clone.modCount = 0;    
   
        // 将链表中所有节点的数据都添加到克隆对象中    
        for (Entry<E> e = header.next; e != header; e = e.next)    
            clone.add(e.element);    
   
        return clone;    
    }    
   
    // java.io.Serializable的写入函数    
    // 将LinkedList的“容量,所有的元素值”都写入到输出流中    
    private void writeObject(java.io.ObjectOutputStream s)    
        throws java.io.IOException {    
        // Write out any hidden serialization magic    
        s.defaultWriteObject();    
   
        // 写入“容量”    
        s.writeInt(size);    
   
        // 将链表中所有节点的数据都写入到输出流中    
        for (Entry e = header.next; e != header; e = e.next)    
            s.writeObject(e.element);    
    }    
   
    // java.io.Serializable的读取函数:根据写入方式反向读出    
    // 先将LinkedList的“容量”读出,然后将“所有的元素值”读出    
    private void readObject(java.io.ObjectInputStream s)    
        throws java.io.IOException, ClassNotFoundException {    
        // Read in any hidden serialization magic    
        s.defaultReadObject();    
   
        // 从输入流中读取“容量”    
        int size = s.readInt();    
   
        // 新建链表表头节点    
        header = new Entry<E>(null, null, null);    
        header.next = header.previous = header;    
   
        // 从输入流中将“所有的元素值”并逐个添加到链表中    
        for (int i=0; i<size; i++)    
            addBefore((E)s.readObject(), header);    
    }    
}