Java 中 Hashtable 、HashMap 、TreeMap 有什么不同？
- HashTable 最早期的 Java 类库提供的一个 Hash表实现，本身是同步的，不支持 null 键和值，对同步有导致性能开销，很少被推荐使用。
- HashMap 是应该更加广泛的哈希表实现，行为上与 hashtable 一致，主要区别是 Hashmap 不是同步的，支持null 建和值。 HashMap 进行 put 或者 get 操作，可以达到常熟时间的性能，所以绝大多数场景都使用 HashMap。
- TreeMap 则是基于红黑树提供的顺序访问的。与HashMap不同，它的get put remove之类的操作都是 O(log(N))的时间复杂度，具体顺序可以通过的 Comparator 或者根据键的自然顺序来判断。
Map 整体结构
Hashtable 是扩展了 Dictonary 类，类结构上与 HashMap 之类不同，HashMap 继承的是 abstractMap
HashMap 等其他 Map 都是扩展了 AbstractMap ,里面包含了通用方法抽象。
HashMap 的性能表现非常依赖哈希表的有效性。
equals 和 hashcode 基本约定
- equals 相等，hashcode 一定要相等。
- 重写了 hashcode也要重写 eqquals
- hashCode 需要保持一致性，状态改变，返回的 hash 值也需要保持一致。
- equals 的对称，反射，传递等特性。
LinkedHashMap
LinkedHashMap 通常提供的是遍历顺序符合插入顺序，它的实现通过键值对维护一个双向链表，通过特定的构造函数，可以创建反映顺序的实例，通过put get computed等操作作为访问。
public V get(Object key) { Node e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value;} hashMap：public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}
LinkedHashMap 的使用示例：
import java.util.LinkedHashMap;import java.util.Map;public class LinkedHashMapSample { public static void main(String[] args) { LinkedHashMap accessOrderedMap = new LinkedHashMap(16, 0.75F, true) { protected boolean removeEldesEntry(Map.Entry eldes) { // 实现自定义删除策略，否则行为就和普遍Map没有区别 return size() > 3; } }; accessOrderedMap.put("Project1", "Valhalla"); accessOrderedMap.put("Project2", "Panama"); accessOrderedMap.put("Project3", "Loom"); accessOrderedMap.forEach((k, v) -> { System.out.println(k + ":" + v); }); // 模拟访问 accessOrderedMap.get("Project2"); accessOrderedMap.get("Project2"); accessOrderedMap.get("Project3"); System.out.println("Iterate over should be not afected:"); accessOrderedMap.forEach((k, v) -> { System.out.println(k + ":" + v); }); // 触发删除 accessOrderedMap.put("Project4", "Mission Control"); System.out.println("Oldes entry should be removed:"); accessOrderedMap.forEach((k, v) -> {// 遍历顺序不变 System.out.println(k + ":" + v); }); }}
LinkedHashMap 是怎么保证有序的？
LinkedHashMap 只定义了两个属性：
/** * The head of the doubly linked list. * 双向链表的头节点 */private transient Entry header;/** * The iteration ordering method for this linked hash map: true * for access-order, false for insertion-order. * true表示最近最少使用次序，false表示插入顺序 */private final boolean accessOrder;
结构如下：
image
image
构造函数：
// 构造方法1，构造一个指定初始容量和负载因子的、按照插入顺序的LinkedListpublic LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false;}// 构造方法2，构造一个指定初始容量的LinkedHashMap，取得键值对的顺序是插入顺序public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false;}// 构造方法3，用默认的初始化容量和负载因子创建一个LinkedHashMap，取得键值对的顺序是插入顺序public LinkedHashMap() { super(); accessOrder = false;}// 构造方法4，通过传入的map创建一个LinkedHashMap，容量为默认容量(16)和(map.zise()/DEFAULT_LOAD_FACTORY)+1的较大者，装载因子为默认值public LinkedHashMap(Map extends K, ? extends V> m) { super(m); accessOrder = false;}// 构造方法5，根据指定容量、装载因子和键值对保持顺序创建一个LinkedHashMappublic LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder;}
从构造方法中可以看出，默认采用插入顺序来维持取出键值对的次序，所有改造方法都是通过父类的构造方法来创建对象。 主要顺序调整，靠 put 方法中afterNodeAccess实现:
LinkedHashMap 中 afterNodeAccess 实现：
void afterNodeAccess(Node e) { // move node to last LinkedHashMap.Entry last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry p = (LinkedHashMap.Entry)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } }
- 从table的角度看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
- 从header的角度看，新的entry需要插入到双向链表的尾部。
总得来看，再说明一遍，LinkedHashMap的实现就是HashMap+LinkedList的实现方式，以HashMap维护数据结构，以双向链表LinkedList的方式维护数据插入顺序。
TreeMap
TreeMap 整体顺序是由键的顺序关键决定，通过 Comparator 或者 Comparable 顺序来决定。
public V put(K key, V value) { Entry t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry parent; // split comparator and comparable paths Comparator super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable super K> k = (Comparable super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }
TreeMap 是如何保证顺序的？
主要是使用：
Comparator super K> cpr = comparator;
方式进行比较，然后插入，保证顺序。
HashMap
- HashMap内部实现基本点分析。
- 容量(capcity)和负载系数(load factor)。
- 树化 。
HashMap 内部的结构
HashMap 是数组+链表/红黑树的实现。数组被分为一个个桶(bucket)，通过对 哈希值的键值进行数组的寻址，如果哈希值相同，然后以链表形式存储。
image
HashMap 构造函数
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; this.threshold = tableSizeFor(initialCapacity); }
为什么HashMap要树化呢？
本质上这是个安全问题。 因为在元素放置过程中，如果一个对象哈希冲突，都被放置到同一个桶里，则会形成一个链表，我们知道链表查询是线性的，会严重影响存取的性能。而在现实世界，构造哈希冲突的数据并不是非常复杂的事情，恶意代码就可以利用这些数据大量与服务器端交互，导致服务器端CPU大量占用，这就构成了哈希碰撞拒绝服务攻击，国内一线互联网公司就发生过类似攻击事件。
欢迎关注公众号:程序员开发者社区