java集合放在java.util包下面

1.ArrayList（数据是放在一个 顺序地址 的内存块）

ArrayList的数据结构是数组

2.LinkedList

LinkedList的数据结构是链表结构（每个节点储存了前一个和后一个节点的地址，每个节点是分散在内存中）

3.HashMap

HashMap是数据结构是由数组和链表组成

数组结构是

/**     * The table, initialized on first use, and resized as     * necessary. When allocated, length is always a power of two.     * (We also tolerate length zero in some operations to allow     * bootstrapping mechanics that are currently not needed.)     */    transient Node
     
      [] table;
     

当put操作时

/**     * Implements Map.put and related methods     *     * @param hash hash for key     * @param key the key     * @param value the value to put     * @param onlyIfAbsent if true, don't change existing value     * @param evict if false, the table is in creation mode.     * @return previous value, or null if none     */    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node
      
       [] tab; Node
       
         p; int n, i;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        else {            Node
        
          e; K k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                e = ((TreeNode
         
          )p).putTreeVal(this, tab, hash, key, value);            else {                for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;        if (++size > threshold)            resize();        afterNodeInsertion(evict);        return null;    }
         
        
       
      

（n-1）&hash(key)  算出数组的索引，如果这个索引没有node就new 一个node放到这个索引上面。

如果索引有node，首先从索引上这个节点对应的链表判断，是否条件满足，如果满足就把新的value替换掉这个node的value，如果不满足就new一个node放到这个链表上。

判断条件　　if (p.hash == hash &&

                ((k = p.key) == key || (key != null && key.equals(k))))

 

4.HashSet

HashSet其实是通过HashMap去实现的

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

 

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

 

4.TreeMap

TreeMap的数据结构理解就难点，它是由红黑平衡树组成的。

他可以跟key排序。

 

。。。。。。