public interface ListIterator<E> extends Iterator<E> {
	//Iterator中的方法
    boolean hasNext();
    E next();
	void remove();
	//适用于自然有序的集合的方法
    boolean hasPrevious();//反向遍历
    E previous();//反向遍历
    int nextIndex();
    int previousIndex();
    void set(E e);
    void add(E e);
}

public static void main(String[] args) {
	List<String> a = new LinkedList<>();
	a.add("Amy");
	a.add("Carl");
	a.add("Ercia");
	List<String> b = new LinkedList<String>();
	b.add("Bob");
	b.add("Doug");
	b.add("Frances");
	b.add("Gloia");
	//Merge the word from b to a
	//listIterator和iterator是指向两个元素之间的，而不是某一个元素
	ListIterator<String> aIterator = a.listIterator();
	//bIterator是Iterator，因此无add方法
	Iterator<String> bIterator = b.iterator();
	while(bIterator.hasNext()){
		if(aIterator.hasNext()){
			aIterator.next();
		}
		//添加元素是在指针所指的中间添加元素
		aIterator.add(bIterator.next());
	}
	System.out.println(a);
	bIterator = b.iterator();
	while(bIterator.hasNext()){
		bIterator.next();
		if(bIterator.hasNext()){
			bIterator.next();
			//删除指针左边的元素
			bIterator.remove();
		}
	}
	System.out.println(b);
	//这里是List的方法，删除a中所有b的元素
	a.removeAll(b);
	System.out.println(a);
}

ListIterator<String> iterator = c.listIterator();
String oldValue = iterator.next();
iterator.set(newValue);

Collection<String> a = new LinkedList<String>();
a.add("A");
a.add("B");
Iterator<String> it1 = a.iterator();
Iterator<String> it2 = a.iterator();
it1.next();
it1.remove();
it2.next();

static class Entry<K, V> implements Map.Entry<K, V> {
	// Entry继承了Map接口中的静态子类Entry；Entry<K,V>是槽中的元素，
	// 用作链表来解决散列冲突
	final K key;// 键
	V value;// 值
	Entry<K, V> next;// 用来实现链表结构， 同一链表中的key的hash是相同的
	int hash;
	protected Entry(int hash, K key, V value, Entry<K, V> next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}
}

public class HashMap<K,V>{
	static final int DEFAULT_INITIAL_CAPACITY = 16 ; // 默认初始容量是16。 （ 必须是2的次方）
	static final int MAXIMUM_CAPACITY = 1 << 30 ; // 即2的30次方
	static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认装载因子
	Entry[] table; // Entry表
	int size; // Entry[]实际存储的Entry个数
	int threshold; // reash的阈值， =capacity * loadfactor
	final float loadFactor;   //装填因子
}

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    //对于空值table[0]中查找
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    //二次hash，得到hash值
    int hash = (key == null) ? 0 : hash(key);
    //计算出在哪个桶indexFor(hash, table.length)
    //遍历桶内元素
    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;
}

public V put(K key, V value) {
	//判断是否空
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    //二次hash得到hash值
    int hash = hash(key);
    //得到该hash的桶号码
    int i = indexFor(hash, table.length);
    //寻找过程，确保唯一
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //如果存在，要覆盖
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //添加Entry
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
    	//容量扩大两倍
        resize(2 * table.length);
        //二次hash
        hash = (null != key) ? hash(key) : 0;
        //找到槽位
        bucketIndex = indexFor(hash, table.length);
    }
    //添加
    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    //头插
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Set<K> keySet();  //键集
Collection<V> values(); //值集合
Set<Map.Entry<K, V>> entrySet(); //键值集

Set s = Collections.synchronizedSet(new HashSet(...));

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
 {
    // 使用 NavigableMap 的 key 来保存 Set 集合的元素
    private transient NavigableMap<E,Object> m;
    // 使用一个 PRESENT 作为 Map 集合的所有 value。
    private static final Object PRESENT = new Object();
    // 包访问权限的构造器，以指定的 NavigableMap 对象创建 Set 集合
    TreeSet(NavigableMap<E,Object> m)
    {
        this.m = m;
    }
    public TreeSet()                                      // ①
    {
        // 以自然排序方式创建一个新的 TreeMap，
        // 根据该 TreeSet 创建一个 TreeSet，
        // 使用该 TreeMap 的 key 来保存 Set 集合的元素
        this(new TreeMap<E,Object>());
    }
    public TreeSet(Comparator<? super E> comparator)     // ②
    {
        // 以定制排序方式创建一个新的 TreeMap，
        // 根据该 TreeSet 创建一个 TreeSet，
        // 使用该 TreeMap 的 key 来保存 Set 集合的元素
        this(new TreeMap<E,Object>(comparator));
    }
    public TreeSet(Collection<? extends E> c)
    {
        // 调用①号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
        this();
        // 向 TreeSet 中添加 Collection 集合 c 里的所有元素
        addAll(c);
    }
    public TreeSet(SortedSet<E> s)
    {
        // 调用②号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
        this(s.comparator());
        // 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素
        addAll(s);
    }
    //TreeSet 的其他方法都只是直接调用 TreeMap 的方法来提供实现
    ...
    public boolean addAll(Collection<? extends E> c)
    {
        if (m.size() == 0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap)
        {
            // 把 c 集合强制转换为 SortedSet 集合
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            // 把 m 集合强制转换为 TreeMap 集合
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<? super E> cc = (Comparator<? super E>) set.comparator();
            Comparator<? super E> mc = map.comparator();
            // 如果 cc 和 mc 两个 Comparator 相等
            if (cc == mc || (cc != null && cc.equals(mc)))
            {
                // 把 Collection 中所有元素添加成 TreeMap 集合的 key
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        // 直接调用父类的 addAll() 方法来实现
        return super.addAll(c);
    }
    ...
 }

public interface SortedSet<E> extends Set<E> {
    Comparator<? super E> comparator();
    /**
     * Returns a view of the portion of this set whose elements range
     * from <tt>fromElement</tt>, inclusive, to <tt>toElement</tt>,
     * exclusive.  (If <tt>fromElement</tt> and <tt>toElement</tt> are
     * equal, the returned set is empty.)
     */
    SortedSet<E> subSet(E fromElement, E toElement);
    /**
     * Returns a view of the portion of this set whose elements are
     * strictly less than <tt>toElement</tt>.
     */
    SortedSet<E> headSet(E toElement);
    /**
     * Returns a view of the portion of this set whose elements are
     * greater than or equal to <tt>fromElement</tt>.
     */
    SortedSet<E> tailSet(E fromElement);
    /**
     * Returns the first (lowest) element currently in this set.
     */
    E first();
    /**
     * Returns the last (highest) element currently in this set.
     */
    E last();
}

public interface NavigableSet<E> extends SortedSet<E> {
	//不包括等于
    /**
     * Returns the greatest element in this set strictly less than the
     * given element, or {@code null} if there is no such element.
     */
    E lower(E e);
    /**
     * Returns the least element in this set strictly greater than the
     * given element, or {@code null} if there is no such element.
     */
    E higher(E e);
    //包括等于
    /**
     * Returns the greatest element in this set less than or equal to
     * the given element, or {@code null} if there is no such element.
     */
    E floor(E e);
    /**
     * Returns the least element in this set greater than or equal to
     * the given element, or {@code null} if there is no such element.
     */
    E ceiling(E e);
    /**
     * Retrieves and removes the first (lowest) element,
     * or returns {@code null} if this set is empty.
     */
    E pollFirst();
    /**
     * Retrieves and removes the last (highest) element,
     * or returns {@code null} if this set is empty.
     */
    E pollLast();
    /**
     * Returns an iterator over the elements in this set, in ascending order.
     */
    Iterator<E> iterator();
    /**
     * Returns a reverse order view of the elements contained in this set.
     */
    NavigableSet<E> descendingSet();
    /**
     * Returns an iterator over the elements in this set, in descending order.
     * Equivalent in effect to {@code descendingSet().iterator()}.
     */
    Iterator<E> descendingIterator();
    /**
     * Returns a view of the portion of this set whose elements range from
     * {@code fromElement} to {@code toElement}.  If {@code fromElement} and
     * {@code toElement} are equal, the returned set is empty unless {@code
     * fromInclusive} and {@code toInclusive} are both true.
     */
    NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);
    /**
     * Returns a view of the portion of this set whose elements are less than
     * (or equal to, if {@code inclusive} is true) {@code toElement}.
     */
    NavigableSet<E> headSet(E toElement, boolean inclusive);
    /**
     * Returns a view of the portion of this set whose elements are greater
     * than (or equal to, if {@code inclusive} is true) {@code fromElement}.
     */
    NavigableSet<E> tailSet(E fromElement, boolean inclusive);
}

public static void main(String[] args) {
	Queue<Integer>  prq = new PriorityQueue();
	Random r = new Random();
	System.out.println("--------------add----------------");
	for(int i = 0; i < 5; i++){
		int addNum = r.nextInt(100);
		prq.add(addNum);
		System.out.println("add num" + addNum);
		//通过打印的队列可以看出来，队列内部不一定有序，但是最小元素一定在队头
		//添加的变化过程就是将新元素放在最后，然后调整堆
		System.out.println("prq" + prq);
	}
	System.out.println("----------------remove-----------------------");
	for(int i = 0; i < 5; i++){
		int x = prq.peek();
		System.out.println("remove num" + x);
		prq.remove();
		//通过打印的队列可以看出来，队列内部不一定有序，但是最小元素一定在队头
		//删除的变化过程就是将最后一个元素，放在堆顶，然后在进行调整
		System.out.println("prq" + prq);
	}
}

public static void main(String[] args) throws Exception {
	String a = new String("a");
	String b = new String("b");
	Map weakmap = new WeakHashMap();
	Map map = new HashMap();
	map.put(a, "aaa");
	map.put(b, "bbb");
	weakmap.put(a, "aaa");
	weakmap.put(b, "bbb");
	map.remove(a);
	a = null;
	b = null;
	System.gc();
	Iterator i = map.entrySet().iterator();
	while (i.hasNext()) {
		Map.Entry en = (Map.Entry) i.next();
		System.out.println("map:" + en.getKey() + ":" + en.getValue());
	}
	Iterator j = weakmap.entrySet().iterator();
	while (j.hasNext()) {
		Map.Entry en = (Map.Entry) j.next();
		System.out.println("weakmap:" + en.getKey() + ":" + en.getValue());
	}
}

List<WeakHashMap<byte[][], byte[][]>> maps = new ArrayList<WeakHashMap<byte[][], byte[][]>>();
for (int i = 0; i < 1000; i++) {
	WeakHashMap<byte[][], byte[][]> d = new WeakHashMap<byte[][], byte[][]>();
	d.put(new byte[1000][1000], new byte[1000][1000]);
	maps.add(d);
	System.gc();
	System.err.println(i);
//	for (int j = 0; j < i; j++) {
//		System.err.println(j + " size" + maps.get(j).size());
//	}
}

private static class Entry<K,V> extends WeakReference<K>
implements Map.Entry<K,V> Entry(K key, V value, ReferenceQueue<K> queue,int hash, Entry<K,V> next) {
	super(key, queue);
	this.value = value;
	this.hash = hash;
	this.next = next;
}

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
{
    /**
     * The head of the doubly linked list.
     */
    private transient Entry<K,V> header;
    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     */
    private final boolean accessOrder;
    /**
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
     * with the specified initial capacity and load factor.
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        //初始化不记录访问顺序
        accessOrder = false;
    }
    /**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    /**
     * Called by superclass constructors and pseudoconstructors (clone,
     * readObject) before any entries are inserted into the map.  Initializes
     * the chain.
     */
    @Override
    void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }
}
private static class Entry<K,V> extends HashMap.Entry<K,V> {
    //双向循环链表
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }
    /**
     * Removes this entry from the linked list.
     */
    private void remove() {
        before.after = after;
        after.before = before;
    }
    /**
     * Inserts this entry before the specified existing entry in the list.
     */
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }
    //put方法会调用该方法
    /**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        //按照访问顺序记录
        if (lm.accessOrder) {
            lm.modCount++;
            //删除该节点
            remove();
            //由于被访问过，变为最新节点，放在head前面
            addBefore(lm.header);
        }
    }
    void recordRemoval(HashMap<K,V> m) {
        remove();
    }
}

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //添加了删除队头的操作
    addEntry(hash, key, value, i);
    return null;
}
//#####################重写方法#####################
void addEntry(int hash, K key, V value, int bucketIndex) {
    super.addEntry(hash, key, value, bucketIndex);
    //最老的在队头
    // Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    }
}
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //按照访问顺序记录
    if (lm.accessOrder) {
        lm.modCount++;
        //删除该节点
        remove();
        //由于被访问过，变为最新节点，放在head前面
        addBefore(lm.header);
    }
}
//在一个节点前面添加节点
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
}
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //按照访问顺序记录
    if (lm.accessOrder) {
        lm.modCount++;
        //删除该节点
        remove();
        //由于被访问过，变为最新节点，放在head前面
        addBefore(lm.header);
    }
}

private enum Color {
	RED(255, 0, 0), GREEN(0, 255, 0), BLUE(0, 0, 255);
	private int r;
	private int g;
	private int b;
	Color(int r, int g, int b) {
		this.r = r;
		this.g = g;
		this.b = b;
	}
}
public static void drawLine(Set<Color> colors) {
	System.out.println("Requested Colors to draw lines : " + colors);
	for (Color c : colors) {
		System.out.println("drawing line in color : " + c);
	}
}
public static void main(String[] args) {
	// this will draw line in yellow color
	EnumSet<Color> yellow = EnumSet.of(Color.RED, Color.GREEN);
	drawLine(yellow);
	// RED + GREEN + BLUE = WHITE
	EnumSet<Color> white = EnumSet.of(Color.RED, Color.GREEN, Color.BLUE);
	drawLine(white);
	// RED + BLUE = PINK
	EnumSet<Color> pink = EnumSet.of(Color.RED, Color.BLUE);
	drawLine(pink);
}