Hashtable、HashMap、TreeMap的区别及相关知识扩展
区别：
-
Hashtable:
是早期java类库提供的哈希表实现，本身是同步的，不支持null键和值，由于同步导致的性能开销，已经很少被推荐使用；
-
HashMap:
HashMap是应用更加广泛的哈希表实现，行为上与Hashtable一致，主要区别在于HashMap不是同步的，支持null键和值；散列正常情况下，对HashMap进行put或者get操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选；
-
TreeMap：
TreeMap是基于红黑树的一种提供数序访问的Map，和HashMap不同，他的get、put、remove之类都是log（N）的时间复杂度，具体顺序是可以指定的，由conparator来决定，或者根据键的自然访问顺序；
Map整体结构：
- 大部分使用Map的场景通常就是放入、访问或者删除，HashMap在这种情况下基本是最好的选择；HashMap的性能表现非常依赖哈希码的有效性；
- hashCode和equals的基本约定：
- equals相等，hashCode一定要相等；
- 重写了hashCode也要重写equals
- hashCode需要保持一致性，状态改变，返回的哈希码仍然要一致；
LinkedHashMap和TreeMap：
二者都能保证某种顺序，但还是有所不同的；
LinkedhashMap：
提供的是遍历顺序符合插入顺序，他的实现是通过为条目维护一个双向链表，通过特定的构造函数，可以创建反映访问顺序的实例；
如果是插入顺序模式，对已经存在map中的key再进行put操作不会影响其在链表中的位置；
如果是访问顺序模式，则遍历时最先访问的是最少被访问的元素，这点可以非常方便的用来实现LRU； put、get、putAll（参数Map中的所有元素都算访问）等都算作访问；containsKey和containsValue等函数则不算访问；
重写 removeEldestEntry(Map.Entry) 方法来实施删除策略，传入的Entry是最早插入的（插入顺序）或者是最少访问的（访问顺序），如果该函数返回true，则会在put或者putAll时删除最早或者最少访问的元素，返回false则不会删除，用来实现LRU非常方便；
因为需要维护链表，所以其效率比HashMap略低，但在遍历时因为有链表的存在所以无需访问整个map（与Map容量无关），而HashMap在遍历时需要访问整个Map，所以其访问效率受Map容量影响，所以如果没有必要，不要将HashMap的容量设置的过大；
TreeMap：
对于TreeMap，他的整体顺序是由键的顺序关系决定的，通过Comparator或者Comparable来决定；类似于hashCode和equals的约定，compareTo的返回值需要与equals一致，否则就会出现模棱两可的情况；下面是TreeMap的put函数中的部分片段（JDK8U201），从代码中可以看出，如果key的compare方法返回0（使用Comparator时是一样的），则会被当成同一个对象，不管equals是否返回true；
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
HashMap部分源码阅读：
-
HashMap使用懒加载，构造函数仅仅是设置一些初始值而已，看如下代码：
public HashMap(int initialCapacity, float loadFactor) { //忽略一系列参数检查后： this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } -
值得注意的是threshold的赋值，按照理解threshold应该是capacity × factor，但是此处是直接将tableSizeFor函数的返回值直接给了threshold，而tableSizeFor函数只是将15等非2的幂数值调整为16等2的幂数值，如果参数capacity就是2的幂数值，相当于直接将capacity赋值给了threshold，而没有考虑factor？？？其实因为talbe没有初始化，put操作会触发resize方法，该方法中会重新计算容量和门限，逻辑没有问题；下面贴出tableSizeFor函数内容：
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; } -
put函数中仅有一句putVal的调用，注意：putVal调用时第一个参数哈希值是调用了hash函数，并不是key本身的哈希值：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } -
hash函数，将key的hashCode有移16位然后与位移前的自身进行异或，为什么要这么做？因为有些数据计算出的哈希值差异主要在高位，而HashMap的寻址是忽略容量以上高位的，这么做可以有效避免哈希碰撞；
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } -
putVal函数最后两个参数：
-
最后两个boolean参数，第一个在注释中可以清楚的看见它的含义：如果是true，则当元素已存在时，不改变value值；第二个参数则是直接传给了一个叫afterNodeInsertion的函数，去看函数定义时，明确说明，是给LinkedHashMap添加逻辑使用的，除了这个函数还有两个函数也是同样的功能，代码如下：
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }
-
-
putVal部分代码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> 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 { ... if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); ... } ... if (++size > threshold) resize(); }- resize()方法在tab为null或者容量不满足要求时扩容；
- 新插入的元素位置由 (n - 1) & hash 决定；
- 当容量达到一定的门限值时会发生树化；
-
putVal完整代码逻辑及代码：
代码逻辑：
- 如果table == null 或者table.length == 0，resize方法负责初始化它；
- 如果（n-1） & hash == null，则直接使用key和value新建一个node并存放至tab[（n-1） & hash];
- 如果（n-1） & hash != null：
-
查找需要修改的节点：
- 如果talbe[n-1） & hash]这个Node对象（下面我们称头节点）的哈希码（Node对象存储了构造函数传入的hash，也是hash函数计算的hash值）与hash（参数）相同，并且头节点的key == 参数key 或者 key equals 参数key，则修改节点e就是头节点；
- 如果第一步不成立，则检查头节点是否是TreeNode的实例，如果不是，进入第三步，否则e由头节点.putTreeVal()函数决定，该函数根据hash进行二叉树的搜索及当hash一致但key不同时候一系列操作；
- 遍历链表，直到找出key或者到链表尾部，如果遍历完链表还找不到Node，则在链表尾部插入一个新建的Node，该node存放需要插入的key和value信息，并且如果链表的长度大于等于TREEIFY_THRESHOLD - 1，调用treeifyBin(tab, hash);进行树化。e等于新建的Node；
-
修改节点：
- 如果查询到的需要修改的节点为null，则什么也不做（e为null只在putTreeVal函数中才会返回，因为已经为e赋值，无需更多操作所以返回null），否则修改val（要看onlyIfAbsent参数）、调用afterNodeAccess(e)并return oldValue；
- 虽然putTreeVal函数没有onlyIfAbsent参数，但是它仅在新建节点时候赋值并返回null，所以不违反onlyIfAbsent参数的约定；
-
- 插入完成后：++modCount；++size；如果size > threshold,调用resize方法；
- 调用afterNodeInsertion(evict)方法；
- return null（因为代码如果进入第三条，则会有自己的return，不进入第三条相当于是新建，所有没有oldValue）；
完整代码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> 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<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) e = ((TreeNode<K,V>)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; } -
resize：
- resize触发条件：size > threshold或者table==null 或者table.length ==0;
- resize逻辑：
- 如果size已经超过MAXIMUM_CAPACITY（1 << 30），那么直接提高门限为Integer.MAX_VALUE，不进行扩容；
- 正常情况，容量、门限扩大一倍；
- map未初始化，但设定过threshold，那么将容量设置为门限，重新计算门限，如果容量和门限都小于如果size已经超过MAXIMUM_CAPACITY（门限可能大于容量，当负载因子大于1时），则门限为容量×负载因子，否则门限为Integer.MAX_VALUE；
- map未初始化，没有设定过threshold，使用默认大小及门限：容量16，负载因子：0.75；
- 如果原table中存在引用，则将引用迁移至新的table中并将oldTable中的引用置null；
- 迁移时只需要使用hash & oldCapacity即可确定元素新的位置；
- 拿到oldTable首元素后马上将oldTable首元素引用置空，降低并发resize导致出现问题的概率，但仍然是不可避免的，将链表分成位置不变的一个链表和位置为原位置+oldCapacity的一个链表后，再将首元素分辨放入table中；
- 迁移不再导致卡死，因为迁移时同一个桶内的元素位置不在颠倒，所以不会再产生循环链表导致卡死的问题了，但是仍然是不是线程安全的，并发的resize会导致元素丢失等问题；
整体源码：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } -
树化：
-
树化触发：
binCount >= TREEIFY_THRESHOLD - 1；TREEIFY_THRESHOLD = 8；虽然binCount >= 7时会触发，但是binCount在树化触发的分支上是比实际元素个数小2的；所以触发的条件是链表长度 > 8，即长度达到9的时候会触发树化，这跟TREEIFY_THRESHOLD变量名字面意思保持一致；
-
treeifyBin逻辑：
-
如果
tab.length < MIN_TREEIFY_CAPACITY MIN_TREEIFY_CAPACITY = 64只会简单的扩容，不会树化；当容量大于阈值时，才会树化；
-
-
为什么要树化：
hash相同的数据会被放置在同一个桶里，他们是以链表的形式存放的，查找、添加、删除都是n的复杂度（添加需要查询是否存在），现实世界中，构造hash相同的数据并不是十分困难的事情，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端 CPU 大量占用，这就构成了哈希碰撞拒绝服务攻击；
-
解决hash冲突有哪些办法：
解决哈希冲突的常用方法有：
-
开放定址法
基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
-
再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。 -
链地址法（即HashMap选择的方式）
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
-
建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
