public boolean hasNext() {
	return cursor != size();
}

public Object next() {
	try {
		// 调用实现类的get方法，获取指定坐标的元素
		Object next = get(cursor);
		// 检查迭代过程中，List是否有被修改过
		checkForComodification();
		// 游标++，记录最新一次next方法返回的元素坐标
		lastRet = cursor++;
		return next;
	} catch(IndexOutOfBoundsException e) {
		checkForComodification();
		throw new NoSuchElementException();
	}
}

final void checkForComodification() {
	// 检查基础ArrayList里的modCount是否被修改过
	if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	}
}

public void remove() {
	if (lastRet == -1)
		throw new IllegalStateException();

	try {
		// 调用实现类的remove方法
		AbstractList.this.remove(lastRet);
	if (lastRet < cursor)
		cursor--;
	lastRet = -1;

	int newModCount = modCount;
	if (newModCount - expectedModCount > 1)
		throw new ConcurrentModificationException();
	// 重置modCount值
	expectedModCount = newModCount;
	} catch(IndexOutOfBoundsException e) {
		throw new ConcurrentModificationException();
	}
}

public boolean hasPrevious() {
	return cursor != 0;
}

public Object previous() {
	try {
		Object previous = get(--cursor);
		checkForComodification();
		lastRet = cursor;
		return previous;
	} catch(IndexOutOfBoundsException e) {
		checkForComodification();
		throw new NoSuchElementException();
	}
}

public void set(Object o) {
	if (lastRet == -1)
		throw new IllegalStateException();

	try {
		// 通过lastRet值来更新元素
		AbstractList.this.set(lastRet, o);

	int newModCount = modCount;
	if (newModCount - expectedModCount > 1)
		throw new ConcurrentModificationException();
	// 记得要更新modCount值
	expectedModCount = newModCount;
	} catch(IndexOutOfBoundsException e) {
		throw new ConcurrentModificationException();
	}
}

public void add(Object o) {
	try {
		AbstractList.this.add(cursor++, o);
		lastRet = -1;

		int newModCount = modCount;
		if (newModCount - expectedModCount > 1)
		    throw new ConcurrentModificationException();
		expectedModCount = newModCount;
	    } catch(IndexOutOfBoundsException e) {
		throw new ConcurrentModificationException();
	    }
	}
}

	// 持有当前ArrayList集合对象的引用，即父集合的引用
	private AbstractList l;
	// fromIndex，ArrayList的开始位置
    private int offset;
	// 子集合的长度
    private int size;
	// 用于检查父集合是否被修改过
    private int expectedModCount;

	// 通过构造函数可以看出，SubList并没有新创建一个集合，而是持有对父集合的引用，内部通过坐标来实现
    SubList(AbstractList list, int fromIndex, int toIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        expectedModCount = l.modCount;
    }

private transient Object elementData[]; // 元素实际存储在这个数组中

public ArrayList() {
	this(10); // 默认数组容量值为10
}

public ArrayList(int initialCapacity) {
    super();    // AbstractList构造方法为空
    this.elementData = new Object[initialCapacity]; // 创建ArrayList对象的时候就会立即初始化一个数组
}

// 将集合以数组形式返回 这里会创建一个新的数组返回，不会直接将列表集合里的elementData数组返回。
public Object[] toArray() {
	Object[] result = new Object[size]; // 创建一个新的数组，容量为ArrayList的容量
	System.arraycopy(elementData, 0, result, 0, size);  // 使用System.arraycopy将当前列表复制到新的数组。
	return result;
}

public boolean add(Object o) {
	ensureCapacity(size + 1);  // 动态调整数组容量大小，确认容量空间够
	elementData[size++] = o; // 将新元素添加到数组末尾
	return true;
}

// ensureCapacity会自动扩容，所以只有调用了这个方法，一定会确保数组的容量是够用的
public void ensureCapacity(int minCapacity) {
	modCount++; // 记录对集合的每次操作，在迭代器中就根据这个遍历值来判断集合是否被修改过。
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object oldData[] = elementData;
	    int newCapacity = (oldCapacity * 3)/2 + 1;  // 如果集合容量不够了，就进行扩容
    	    if (newCapacity < minCapacity)
		newCapacity = minCapacity;  // 如果容量还是不够，就直接用指定的容量minCapacity
	    elementData = new Object[newCapacity];  // 创建一个使用新容量的新的数组
	    System.arraycopy(oldData, 0, elementData, 0, size); // 使用System.arraycopy将旧数组拷贝到新的数组
	}
    // 如果当前容量够，就直接结束返回
}

// 将新元素添加到指定位置
public void add(int index, Object 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++;
}

// 删除指定位置的元素
public Object remove(int index) {
	RangeCheck(index);

	modCount++; // 只要有对集合操作，modCount都会增加
	Object 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 最后一格元素置为null，方便垃圾收集器回收

	return oldValue;
}

// 清空列表集合
public void clear() {
	modCount++; // 清空操作也会记录

	// Let gc do its work
	for (int i = 0; i < size; i++)
	    elementData[i] = null; // 这里是通过遍历方式，将数组里的所有元素都置为null。

	size = 0;
}

public Object get(int index) {
	RangeCheck(index);

	return elementData[index];
}

public void remove(ArrayList<String> list) {

	for(int i = list.size() - 1; i > 0; i++) {
		if("StringA".equals(list.get(i))) {
			list.remove(i);
		}
	}

}

public void remove(ArrayList<String> list) {

	Iterator iterator = list.iterator();
	while(iterator.hasNext()) {
		if("StringA".equals(iterator.next())) {
			iterator.remove();
		}
	}

}

// 链表节点，链表的组成部分
private static class Entry {
	Object element; // 节点值
	Entry next; // 下一个节点
	Entry previous; // 上一个节点

	Entry(Object element, Entry next, Entry previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
}

private transient Entry header = new Entry(null, null, null); // 初始会创建一个空的Entry节点，链表节点都是用Entry来表示的。记住该版本的链表只有header，当next指针指向header的时候，表示链表尾。
private transient int size = 0;	// 链表长度

public LinkedList() {
    header.next = header.previous = header; // 初始化的时候会构建一个空的循环链表
}

public boolean add(Object o) {
	// header
	// header<->entryA
	addBefore(o, header);
    return true;
}

private Entry addBefore(Object o, Entry e) {
	// 这不是头插法吗？	
	// header<->newEntry
	// header<->entryA
	Entry newEntry = new Entry(o, e, e.previous);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
}

public boolean remove(Object o) {
	if (o==null) {
		for (Entry e = header.next; e != header; e = e.next) {
			if (e.element==null) {
				remove(e);
				return true;
			}
		}
	} else {
		// 从header.next第一个节点开始遍历，通过equals方法比较元素是否相等
		for (Entry e = header.next; e != header; e = e.next) {
			if (o.equals(e.element)) {
				// 找到了，删除Entry节点
				remove(e);
				return true;
			}
		}
	}
	return false;
}

// 移除当前节点  
// head <--> Entry A <--> Entry B <--> Entry C <--> head(the one)         
private void remove(Entry e) {
	if (e == header)
	    throw new NoSuchElementException();

	e.previous.next = e.next;   // 将当前元素的上一个元素的next指针指向当前元素的next对象
	e.next.previous = e.previous;   // 将当前元素的下一个元素的previous指针指向当前元素的previous对象
	size--;
	modCount++;

    // 这样操作完之后，当前元素的next指针还会指向next对象，previous指针还会指针previous对象。这里只改变了上一个和下一个元素的指针指向。并不会改变自己的。所以1.2中即使remove元素，元素对象还是不会被回收。
	// 2018/10/17 jdk1.5优化了这个现象，将e.next = e.previous = null 以及 e.element = null
}

// 根据坐标获取元素
public Object get(int index) {
        return entry(index).element;
}


private Entry entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry e = header;
    if (index < size/2) { // 一次折半查找，从前半部分或者后半部分开始查找
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

// 数组
private transient Entry table[]; 

// 单向链表
private static class Entry implements Map.Entry {
	int hash;
	Object key;
	Object value;
	Entry next;

	Entry(int hash, Object key, Object value, Entry next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}
}

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

private int threshold; // 根据capacity和loadFactor计算出来的，用于扩容HashMap用的

private float loadFactor;

private transient int modCount = 0; // 记录Map的修改次数，迭代的时候可以用来判断集合是否被修改

public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0)
	    throw new IllegalArgumentException("Illegal Initial Capacity: "+
                                               initialCapacity);
	if (loadFactor <= 0)
		throw new IllegalArgumentException("Illegal Load factor: "+
											loadFactor);
	if (initialCapacity==0)
		initialCapacity = 1;

	this.loadFactor = loadFactor;
	table = new Entry[initialCapacity];     // 初始化的时候会创建默认一个Entry数组（JDK1.8版是在put操作初始化的）
	threshold = (int)(initialCapacity * loadFactor);    // 计算出Map扩容值，当Map的元素值超过这个阈值时，Map就会进行扩容
}

// 总结下put的逻辑：
// key null和非null的处理逻辑不同
// key null，添加到tab数组第一个位置
// key 非null，先获取key的hash值，计算得出hash对于数组tab的下标值index，取出tab[index]的链表
// 通过hash和equals方法遍历链表值是否与key相等，如果相等则直接替换，并返回旧值。
public Object put(Object key, Object value) {
	// Makes sure the key is not already in the HashMap.
	Entry tab[] = table;
    int hash = 0;
    int index = 0;

    if (key != null) {
        hash = key.hashCode(); // 取得key的hashCode值，注意hashCode值有可能相同
        index = (hash & 0x7FFFFFFF) % tab.length;   // 计算key的数组下标
        for (Entry e = tab[index] ; e != null ; e = e.next) {   // 遍历Entry链表，这里从tab数组中取出的元素是一个链表结构。
            if ((e.hash == hash) && key.equals(e.key)) {    // 如果key已存在，则value覆盖，并返回old的值
                Object old = e.value;
                e.value = value;
                return old;
            }
        } // 这里for循环的结果是：1）得出结论，key在这个Entry链表中不存在，可以直接插入；2）Entry为null。
    } else {
		// key允许为null
		// 默认数组第一个位置放key为null的元素
        for (Entry e = tab[0] ; e != null ; e = e.next) {
            if (e.key == null) { // key为null的比对是直接用==，所以理论上tab[0]有且只要一个链表节点
                Object old = e.value;
                e.value = value;
                return old;
            }
        }
    }

	// 只有当map的size值发生变化，modCount值才会变化
	modCount++; // key不存在map中，为新的key，则modCount++，表示Map要增加了

	// 如果集合当然容量超过阈值，则进行扩容
	if (count >= threshold) {
	    // Rehash the table if the threshold is exceeded
	    rehash();

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

	// Creates the new entry. 创建新的链表节点Entry
	Entry e = new Entry(hash, key, value, tab[index]); // 创建新的Entry，插入到Entry链表头
	// 这里并发执行会有问题，两个线程同时执行，其中一个线程的数据会丢失
	tab[index] = e; // new Entry方法，会将现有Entry链表添加到新Entry的后面。
	count++;
	return null;
}

// 对Map进行扩容，扩容到更大的数组，需要重新计算下标
private void rehash() {
	int oldCapacity = table.length;
	Entry oldMap[] = table;

	int newCapacity = oldCapacity * 2 + 1;
	Entry newMap[] = new Entry[newCapacity];

	modCount++;
	threshold = (int)(newCapacity * loadFactor);
	// 并发rehash问题的引入，这里创建完新集合就直接赋值给全局table了。
	// 多线程同时rehash
	table = newMap;

	// 取出每一个元素，重新计算下标，插入新数组。
	for (int i = oldCapacity; i-- > 0;) { // 倒序遍历Entry数组
	    for (Entry old = oldMap[i] ; old != null ; ) {  // 顺序遍历Entry链表
			Entry e = old;
			old = old.next;

			int index = (e.hash & 0x7FFFFFFF) % newCapacity;    // 重新计算新的数组下标
			// 以下两行代码在并发扩容的时候会出现死循环，JDK1.8之后改为尾插入，可以避免死循环问题，但是在并发put的时候会出现数据覆盖问题。
			e.next = newMap[index]; // 将Entry添加到链表头，这样扩容完后，是不是就改变的元素的顺序，对的。
			newMap[index] = e;
	    }
	}
}

// 通过键获取值，通过hash获取key所在Entry数组下标，然后遍历该下标的Entry链表，返回值。注意：同一个下标的Entry链表，hash值可能是相同的
public Object get(Object key) {
	Entry tab[] = table;

    if (key != null) {
        int hash = key.hashCode();  // 获取键的hash值
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry e = tab[index]; e != null; e = e.next)
            if ((e.hash == hash) && key.equals(e.key))  //  遍历Entry链表，判断Entry的hash和键是否相等
                return e.value;
	} else {
        for (Entry e = tab[0]; e != null; e = e.next)
            if (e.key == null)
                return e.value;
    }

	return null;
}

public Object remove(Object key) {
	Entry tab[] = table;

    if (key != null) {
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;

		// 所以这里就是一个链表基本删除操作
		// 单链表删除，要保存上一个元素
        for (Entry e = tab[index], prev = null; e != null;  // prev变量用来保存上一个Entry
                prev = e, e = e.next) {
            if ((e.hash == hash) && key.equals(e.key)) {
                modCount++; // 做删除操作，集合size有变，所以modCount++
                if (prev != null)   // 如果prev不为空，直接将prev的next指针指向要删除元素的next对象
                    prev.next = e.next;
                else    // 如果prev为null，说明e为链表头结点，则将链表头指向e的next对象
                    tab[index] = e.next;

                count--;
                Object oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
    } else {
        for (Entry e = tab[0], prev = null; e != null;  // key为null，默认保存在Entry数组的第一个位置
                prev = e, e = e.next) {
            if (e.key == null) {
                modCount++;
                if (prev != null)
                    prev.next = e.next;
                else
                    tab[0] = e.next;

                count--;
                Object oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
    }

	return null;
}

// 只有entry不为null，就说明还可以继续遍历；如果entry为null，就判断index是否>0，如果小于0就没有结束了；
// index>0,entry=null，就继续取出下一个数组的节点赋值给entry
public boolean hasNext() {
	// entry == null 有两种可能：1.还没开始遍历；2.遍历到链表末尾了；
	// index > 0 这里的index初始值是size的值，所以只有>0说明数组坐标还未越界
	while (entry==null && index>0)
		entry = table[--index];

	return entry != null;
}

public Object next() {
	// 使用迭代器方式遍历Map，外部不能修改集合，否者抛异常
	if (modCount != expectedModCount)
		throw new ConcurrentModificationException();

	// 如果entry为null，且index大于0，则取出下一个数组节点
	while (entry==null && index>0)
		entry = table[--index]; // 倒序

	if (entry != null) {
		// lastReturned 遍历保存上一个节点值
		// e 保存当前节点值
		Entry e = lastReturned = entry;
		// 取出下一个节点赋值给entry
		entry = e.next;
		// 根据迭代类型，判断返回的值。HashMap迭代器支持3种类型（构造器中要指明类型），1.返回entry的key；2.返回entry的value；3.直接将entry返回
		return type == KEYS ? e.key : (type == VALUES ? e.value : e);
	}

	// 这里异常的抛出条件是 entry == 0 && index == 0 说明没有节点可以再遍历了
	throw new NoSuchElementException();
}

public void remove() {
		// 说明上次没有调用next方法，或则next没有返回值，也直接抛出了异常
	    if (lastReturned == null)
			throw new IllegalStateException();
		// 说明在集合迭代过程中，外部有修改集合结构，比如新增或则删除
	    if (modCount != expectedModCount)
			throw new ConcurrentModificationException();

	    Entry[] tab = HashMap.this.table;
		// 取得要删除节点的数组index位置
	    int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;

	    for (Entry 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();
	}
}

public Set keySet() {
	if (keySet == null) {
		keySet = new AbstractSet() {
			public Iterator iterator() {
				return new HashIterator(KEYS);
			}
			public int size() {
				return count;
			}
			public boolean contains(Object o) {
				return containsKey(o);
			}
			public boolean remove(Object o) {
				return HashMap.this.remove(o) != null;
			}
			public void clear() {
				HashMap.this.clear();
			}
		};
	}
	return keySet;
}

// 判断值是否在Map中，要遍历整个Map
// 所以containsValue非常耗时
public boolean containsValue(Object value) {
	Entry tab[] = table;

	if (value==null) {
	    for (int i = tab.length ; i-- > 0 ;)
			for (Entry e = tab[i] ; e != null ; e = e.next)
				if (e.value==null)
					return true;
	} else {
		// 后续遍历
	    for (int i = tab.length ; i-- > 0 ;)    // 循环遍历Entry数组，每个Entry是一个链表结构
			for (Entry e = tab[i] ; e != null ; e = e.next) // 再循环判断Entry链表，判断值是否相等
				if (value.equals(e.value)) // 通过equals方法判断值是否相等
					return true;
	}

	return false;
}

// 判断键是否在集合中，通过hash获取key所在的Entry数组下标，然后判断该下标的Entry链表即可。
// contains逻辑与get一模一样
public boolean containsKey(Object key) {
	Entry tab[] = table;
        if (key != null) {
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;   // 获取key的Entry数组下标
            for (Entry e = tab[index]; e != null; e = e.next)   // 遍历Entry链表，判断键是否相等
                if (e.hash==hash && key.equals(e.key))
                    return true;
        } else {
            for (Entry e = tab[0]; e != null; e = e.next)
                if (e.key==null)
                    return true;
        }

	return false;
}

// 清空map
public void clear() {
	Entry tab[] = table;
	modCount++;
	for (int index = tab.length; --index >= 0; )    // 遍历Entry数组
	    tab[index] = null;  // 将Entry链表置为null
	count = 0;
}

// 红黑树节点
static class Entry implements Map.Entry {
	Object key; // 节点值
	Object value;
	Entry left = null; // 左孩子
	Entry right = null; // 右孩子
	Entry parent; // 父节点
	boolean color = BLACK; // 节点颜色
}

Entry(Object key, Object value, Entry parent) { 
	this.key = key;
	this.value = value;
	this.parent = parent;
}

private transient Entry root = null;

private Comparator comparator = null;   // 比较器，用于比较两个元素的大小来决定顺序位置

private transient Entry root = null;    // 红黑树，树根

public TreeMap(Comparator c) {
	this.comparator = c;
}

public Object put(Object key, Object value) {
	Entry t = root;

	if (t == null) {
	    incrementSize();
	    root = new Entry(key, value, null); // 如果树为空树，则创建第一个root节点
	    return null;
	}

	// 这里为什么while循环？因为要递归判断子节点
	// 左子树的值比右子树的小，左小右大
	while (true) {
		// 首先比较key值
	    int cmp = compare(key, t.key);
	    if (cmp == 0) {
		    return t.setValue(value);   // 如果key相同，直接替换value值
	    } else if (cmp < 0) {   // 如果小于，就放到左子树
            if (t.left != null) {
                t = t.left; // 如果左子树不为空，继续递归比较左子树
            } else {
                incrementSize();    // 如果是左子树的叶子节点，就新建一个节点
                t.left = new Entry(key, value, t);  // 将节点插入该位置
                fixAfterInsertion(t.left);  // 然后确保树平衡，尝试旋转树节点到平衡
                return null;
            }
	    } else { // cmp > 0 // 如果大于，就放到右子树
		    if (t.right != null) {
		        t = t.right; // 如果右子树不为空，继续递归比较右子树
		    } else {
                incrementSize();
                t.right = new Entry(key, value, t);
                fixAfterInsertion(t.right); // 确认树平衡
                return null;
            }
	    }
	}
}

private int compare(Object k1, Object k2) {
	return (comparator==null ? ((Comparable)k1).compareTo(k2)
				 : comparator.compare(k1, k2));
}

/** From CLR **/
private void fixAfterInsertion(Entry x) {
	x.color = RED;

	while (x != null && x != root && x.parent.color == RED) {
	    if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
		Entry y = rightOf(parentOf(parentOf(x)));
		if (colorOf(y) == RED) {
		    setColor(parentOf(x), BLACK);
		    setColor(y, BLACK);
		    setColor(parentOf(parentOf(x)), RED);
		    x = parentOf(parentOf(x));
		} else {
		    if (x == rightOf(parentOf(x))) {
			x = parentOf(x);
			rotateLeft(x);
		    }
		    setColor(parentOf(x), BLACK);
		    setColor(parentOf(parentOf(x)), RED);
		    if (parentOf(parentOf(x)) != null) 
			rotateRight(parentOf(parentOf(x)));
		}
	    } else {
		Entry y = leftOf(parentOf(parentOf(x)));
		if (colorOf(y) == RED) {
		    setColor(parentOf(x), BLACK);
		    setColor(y, BLACK);
		    setColor(parentOf(parentOf(x)), RED);
		    x = parentOf(parentOf(x));
		} else {
		    if (x == leftOf(parentOf(x))) {
			x = parentOf(x);
			rotateRight(x);
		    }
		    setColor(parentOf(x),  BLACK);
		    setColor(parentOf(parentOf(x)), RED);
		    if (parentOf(parentOf(x)) != null) 
			rotateLeft(parentOf(parentOf(x)));
		}
	    }
	}
	root.color = BLACK;
}

public Object get(Object key) {
	Entry p = getEntry(key);
	return (p==null ? null : p.value);
}

private Entry getEntry(Object key) {
	Entry p = root;
	while (p != null) {
	    int cmp = compare(key,p.key);   // 比较key的大小
	    if (cmp == 0)   // 这里使用二分查找，小于根节点，就从左子树迭代查找；大于根节点，从右子树查找；知道节点等于返回
		return p;
	    else if (cmp < 0)
		p = p.left;
	    else
		p = p.right;
	}
	return null;
}

public Object remove(Object key) {
	Entry p = getEntry(key);
	if (p == null)
	    return null;

	Object oldValue = p.value;
	deleteEntry(p);
	return oldValue;
}

private void deleteEntry(Entry p) {
        decrementSize();

	// If strictly internal, first swap position with successor.
	if (p.left != null && p.right != null) {
	    Entry s = successor(p);
	    swapPosition(s, p);
	} 

	// Start fixup at replacement node, if it exists.
	Entry replacement = (p.left != null ? p.left : p.right);

	if (replacement != null) {
	    // Link replacement to parent 
	    replacement.parent = p.parent;
	    if (p.parent == null)       
		root = replacement; 
	    else if (p == p.parent.left)  
		p.parent.left  = replacement;
	    else
		p.parent.right = replacement;

	    // Null out links so they are OK to use by fixAfterDeletion.
	    p.left = p.right = p.parent = null;
      
	    // Fix replacement
	    if (p.color == BLACK) 
		fixAfterDeletion(replacement);
	} else if (p.parent == null) { // return if we are the only node.
	    root = null;
	} else { //  No children. Use self as phantom replacement and unlink.
	    if (p.color == BLACK) 
		fixAfterDeletion(p);

	    if (p.parent != null) {
		if (p == p.parent.left) 
		    p.parent.left = null;
		else if (p == p.parent.right) 
		    p.parent.right = null;
		p.parent = null;
	    }
	}
}

public boolean containsKey(Object key) {
	return getEntry(key) != null;
}

private int compare(Object k1, Object k2) {
	return (comparator==null ? ((Comparable)k1).compareTo(k2)   // 如果没有指定比较器，就用元素自带的比较方法
				 : comparator.compare(k1, k2)); // 否则用比较器实现的比较方法
}

// 查找元素是否在集合中，这里要遍历树，使用前序遍历整颗树。
public boolean containsValue(Object value) {
    return (root==null ? false :
            (value==null ? valueSearchNull(root)
                    : valueSearchNonNull(root, value)));
}

private boolean valueSearchNonNull(Entry n, Object value) {
    // Check this node for the value
    if (value.equals(n.value))
        return true;

    // Check left and right subtrees for value
    return (n.left  != null && valueSearchNonNull(n.left, value)) ||    // 前序遍历树查找值
            (n.right != null && valueSearchNonNull(n.right, value));
}

// 返回集合中的第一个元素，采用前序遍历
public Object firstKey() {
        return key(firstEntry());
}

private Entry firstEntry() {
	Entry p = root;
	if (p != null)
	    while (p.left != null)  // 一直遍历左子树直到左叶子节点
		p = p.left;
	return p;
}

// 返回集合中的最后一个元素，采用后序遍历
public Object lastKey() {
    return key(lastEntry());
}

private Entry lastEntry() {
	Entry p = root;
	if (p != null)
	    while (p.right != null)  // 一直遍历右子树直到右叶子节点
		p = p.right;
	return p;
}

// 表示key是一个弱引用，在GC时会被回收
static private class WeakKey extends WeakReference {
		private int hash;	/* Hashcode of key, stored here since the key
					may be tossed by the GC */
}

// 内部使用HashMap
private Map hash;

// 垃圾回收队列，当weakkey要被回收时，会先加入到该队列。
private ReferenceQueue queue = new ReferenceQueue();

private transient HashMap map;  // 基于HashMap实现，内部其实只是用HashMap来保存元素

private static final Object PRESENT = new Object();   // 表示HashMap的value，因为Set不是键值对集合。

// 添加元素到Set中
public boolean add(Object o) {
	return map.put(o, PRESENT)==null;   // 用HashMap保存，key为元素值，value为固定值object
}

public boolean remove(Object o) {
	return map.remove(o)==PRESENT;  // 整个HashMap的value都是同一个对象PRESENT
}