一：集合有哪些
1、java.lang
1) Object 1
2) String 1
3) AbstractStringBuilder 1
4) StringBuffer 1
5) StringBuilder 1
6) Boolean 2
7) Byte 2
8) Double 2
9) Float 2
10) Integer 2
11) Long 2
12) Short 2
13) Thread 2
14) ThreadLocal 2
15) Enum 3
16) Throwable 3
17) Error 3
18) Exception 3
19) Class 4
20) ClassLoader 4
21) Compiler 4
22) System 4
23) Package 4
24) Void 4
2、java.util
1) AbstractList 1
2) AbstractMap 1
3) AbstractSet 1
4) ArrayList 1
5) LinkedList 1
6) HashMap 1
7) Hashtable 1
8) HashSet 1
9) LinkedHashMap 1
10) LinkedHashSet 1
11) TreeMap 1
12) TreeSet 1
13) Vector 2
14) Queue 2
15) Stack 2
16) SortedMap 2
17) SortedSet 2
18) Collections 3
19) Arrays 3
20) Comparator 3
21) Iterator 3
22) Base64 4
23) Date 4
24) EventListener 4
25) Random 4
26) SubList 4
27) Timer 4
28) UUID 4
29) WeakHashMap 4二、hashmap
链表：增删快，查询慢，时间复杂度是O（n）
数组：查询快，增删慢，时间复杂度是O（1）
Hashmap=链表+数组+红黑树（在链表超过8，数组长度超过64，变树，链表小于6变回）
hashmap的查找时间复杂度是O（1）
put操作的流程：
第一步：key.hashcode()，时间复杂度O(1)。
第二步：找到桶以后，判断桶里是否有元素，如果没有，直接new一个entey节点插入到数组中。时间复杂度O(1)。
第三步：如果桶里有元素，并且元素个数小于6，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入都链表尾部。时间复杂度O(1)+O(n)=O(n)。
第四步：如果桶里有元素，并且元素个数大于6，则调用equals方法，比较是否存在相同名字的key，不存在则new一个entry插入都链表尾部。时间复杂度O(1)+O(logn)=O(logn)。红黑树查询的时间复杂度是logn。
实际上每个元素都是装满链表的数组的存储格式
链表的每个node结构是：hash+map+next（指针），hash是通过hash碰撞出来的hashcode，map是键值对（k,v）
三、代码
// 默认容量16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认负载因子0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 链表节点转换红黑树节点的阈值, 9个节点转 static final int TREEIFY_THRESHOLD = 8; // 红黑树节点转换链表节点的阈值, 6个节点转 static final int UNTREEIFY_THRESHOLD = 6; // 转红黑树时, table的最小长度 static final int MIN_TREEIFY_CAPACITY = 64; // 链表节点, 继承自Entry static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; // ... ... } // 红黑树节点 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; // ... }
// 代码1 static final int hash(Object key) { // 计算key的hash值 int h; // 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 代码2 int n = tab.length; // 将(tab.length - 1) 与 hash值进行&运算 int index = (n - 1) & hash;
四：经典部分
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; // 1.对table进行校验：table不为空 && table长度大于0 && // table索引位置(使用table.length - 1和hash值进行位与运算)的节点不为空 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 2.检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 3.如果first不是目标节点，并且first的next节点不为空则继续遍历 if ((e = first.next) != null) { if (first instanceof TreeNode) // 4.如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { // 5.执行链表节点的查找，向下遍历链表, 直至找到节点的key和入参的key相等时,返回该节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } // 6.找不到符合的返回空 return null; }
/** * 从调用此方法的节点开始查找, 通过hash值和key找到对应的节点 * 此方法是红黑树节点的查找, 红黑树是特殊的自平衡二叉查找树 * 平衡二叉查找树的特点：左节点<根节点<右节点 */ final TreeNode<K,V> find(int h, Object k, Class<?> kc) { // 1.将p节点赋值为调用此方法的节点，即为红黑树根节点 TreeNode<K,V> p = this; // 2.从p节点开始向下遍历 do { int ph, dir; K pk; TreeNode<K,V> pl = p.left, pr = p.right, q; // 3.如果传入的hash值小于p节点的hash值，则往p节点的左边遍历 if ((ph = p.hash) > h) p = pl; else if (ph < h) // 4.如果传入的hash值大于p节点的hash值，则往p节点的右边遍历 p = pr; // 5.如果传入的hash值和key值等于p节点的hash值和key值,则p节点为目标节点,返回p节点 else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if (pl == null) // 6.p节点的左节点为空则将向右遍历 p = pr; else if (pr == null) // 7.p节点的右节点为空则向左遍历 p = pl; // 8.将p节点与k进行比较 else if ((kc != null || (kc = comparableClassFor(k)) != null) && // 8.1 kc不为空代表k实现了Comparable (dir = compareComparables(kc, k, pk)) != 0)// 8.2 k<pk则dir<0, k>pk则dir>0 // 8.3 k<pk则向左遍历(p赋值为p的左节点), 否则向右遍历 p = (dir < 0) ? pl : pr; // 9.代码走到此处, 代表key所属类没有实现Comparable, 直接指定向p的右边遍历 else if ((q = pr.find(h, k, kc)) != null) return q; // 10.代码走到此处代表“pr.find(h, k, kc)”为空, 因此直接向左遍历 else p = pl; } while (p != null); return null; }