最近在复习集合类的知识，尽可能将常见的集合类的底层代码都分析一遍。
1.理解HashMap
前面已经分析了ArrayList和LinkedList，两种数据结构实现的List存储有极端的差别：
线性表存储
数组存储区建是连续的，占用内存严重，空间复杂度大寻址容易，但是插入删除复杂（如果都是在数组末尾操作，复杂度会相对较小）链表存储
存储区间离散，占用内存比较宽松，空间复杂度小寻址困难，插入删除简单而哈希表结合了两种存储的特点，在HashMap中通过拉链表的方式（即链表的数组）实现
从上图中可以看到，哈希表结合数组和链表，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12=12,28=12,108=12,140=12。所以12、28、108以及140都存储在数组下标为12的位置。
而java8中则结合了链表、数组和红黑树，当链表中的个数超过8个时，会转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法
2.HashMap的底层实现
初始化 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //默认装载因子0.75f.。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（扩容操作） static final float DEFAULT_LOAD_FACTOR = 0.75f; //最大容量 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认的初始容量16. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容 int threshold; // 填充因子 final float loadFactor; } HashMap的构造方法 //初始化，设置默认加载因子 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 指定初始容量和填充因子的构造方法 public HashMap(int initialCapacity, float loadFactor) { // 指定的初始容量非负 if (initialCapacity < 0) throw new IllegalArgumentException(Illegal initial capacity: + initialCapacity); // 如果指定的初始容量大于最大容量,置为最大容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 填充比为正 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(Illegal load factor: + loadFactor); this.loadFactor = loadFactor; // 指定容量后，tableSizeFor方法计算出临界值，put数据的时候如果超出该值就会扩容，该值肯定也是2的倍数 // 指定的初始容量没有保存下来，只用来生成了一个临界值 this.threshold = tableSizeFor(initialCapacity); } //生成临界值 static final int tableSizeFor(int cap) { int n = cap - 1; // 向右做无符号位移 n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; // 三目运算符的嵌套 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } Map中的节点，同样是以内部类的方式存在（这里面所有的方法都是final修饰的，不可以被重写，可以重载） //链表节点 static class Node<K,V> implements Map.Entry<K,V> { //节点的hashcode是固定的 final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } //重写equals一般要重写hashCode方法 public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } //红黑树节点 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; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } /** * Returns root of tree containing this node. */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } 获取哈希值（hashMap中的hash值并不是直接取对象的哈希值，而是把key的hashcode做一些运算以得到最终的哈希值，最后的哈希值表示对象的链表位置） static final int hash(Object key) { int h; // h = key.hashCode() 为第一步 取hashCode值 // h ^ (h >>> 16) 为第二步 高位参与运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } Map中的put方法（put的时候根据 h & (length - 1) 定位到那个桶然后看是红黑树还是链表再putVal，如果是链表则讲解点放在数组后的第一个节点，原先该位置的节点往后移，如果是红黑树，放入节点之后还要进行自旋并染色，已达到红黑树要求） //放入键值对 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果tab为空或长度为0，则分配内存resize() if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // (n - 1) & hash找到put位置，如果为空,则直接put if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //如果不为空时，则将结点作为头节点 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) // 红黑树的put方法比较复杂，putVal之后还要遍历整个树，必要的时候修改值来保证红黑树的特点 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 链表 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // e为空，表示已到表尾也没有找到key值相同节点，则新建节点 p.next = newNode(hash, key, value, null); // 新增节点后如果节点个数到达阈值，则将链表转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 容许空key空value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 更新hash值和key值均相同的节点Value值 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; } Map的get方法（先获取key的hash值，并根据hash的值判断数组头节点是不是对应的值，不是在遍历链表或树的节点） public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } //根据hash和key获取value final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab;//Entry对象数组 Node<K,V> first,e; //在tab数组中经过散列的第一个位置 int n; K k; /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/ //也就是说在一条链上的hash值相同的 if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { /*检查第一个Node是不是要找的Node*/ if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同 return first; /*检查first后面的node*/ if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); /*遍历后面的链表，找到key值和hash值都相同的Node*/ do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }3.最后再区分一下几个常见的Map
(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它继承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，使用双链表和哈希表的形式实现，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
linkedHashMap的链表结构如下：
//以插入顺序遍历 Map<String,String> map=new LinkedHashMap<String,String>(); //以访问次序顺序遍历 Map<String,String> map=new LinkedHashMap<String,String>(16,0.75f,true);实现原理： 以插入顺序遍历：插入一个新的节点，该节点的前指针指向上一个节点，上一个节点的后指针指向新节点
以访问次序顺序遍历：在LinkedHashMap中调用map方法后，会将这次访问的元素移至链表尾部，不断访问可以形成访问顺序排序的链表。
(4) TreeMap：TreeMap实现SortedMap接口，是通过红黑树实现的map，映射根据其键的自然顺序进行排序 ，或者根据 创建映射时提供的 Comparator 进行排序 ，具体取决于使用的构造方法。TreeMap的基本操作containsKey、get、put、remove方法，它的时间复杂度是log（n）。默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
（5）ConcurentHashMap：ConcurentHashMap是线程安全的HashMap，而ConcurrentHashMap和Hashtable主要区别就是围绕着锁的粒度以及如何锁,可以简单理解成把一个大的HashTable分解成多个，形成了锁分离。（以前的HashTable是对整个map加锁）
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。
上述Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。
set就是基于map实现的，其中set放入的对象是放到key值得位置，因为map要求key值不能重复，因此set中要求元素不能重复
