HashMap与HashTable
平时用的最多的就是HashMap了，先给出定义：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {}
由定义可以知道HashMap是键值对的集合，可克隆，可序列化；
HashTable定定义如下：
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {}
由定义知道HashTable也是键值对的集合，可克隆，可序列化；
HasMap和HashTable的区别如下：
- HashMap不是线程安全的；HashTable是线程安全的，其部分方法用synChronized修饰。
- HashMap可以接受null值，即key或者value都可为null；而HashTable不可以。
- 我们从定义可到看到HashMap继承AbstractMap，而HashTable继承Dictionary。
HasMap和HashTable的相似之处如下：
- 二者都是无序的，即不会记录插入顺序。
- 底层实现的数据结构类似。数组+链表的数据结构。首先对key进行哈希，根据哈希值计算数组下标；而不同的key可能产生相同的哈希值，因此同一个数组下标下的键值对采用链表的结构进行存储。
- HashTable除了可以用Iterator，还可以用Enumeration，HashMap不可以用Enumeration。
HashMap和HashTable的几种遍历方式如下
package cn.ihep.collection;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import org.junit.Test;
public class TestHashMapHashTable {
@Test
public void test1() {
Map<String, String> map = new HashMap<String, String>();
map.put("1", "Tom");
map.put("a", "aaa");
map.put("student", "xiaowang");
map.put("2", "shao");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + entry.getValue());
}
System.out.println("*******************");
for (String key : map.keySet()) {
System.out.println(key + map.get(key));
}
System.out.println("*******************");
Iterator<Map.Entry<String, String>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
Entry<String, String> entry = iter.next();
System.out.println(entry.getKey() + entry.getValue());
}
System.out.println("------------------------");
Hashtable<String, String> map2 = new Hashtable<>();
map2.put("2", "Jerry");
map2.put("student", "xiaowang");
map2.put("usr", "tom");
map2.put("10", "wang");
Iterator<Map.Entry<String, String>> iterator = map2.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, String> entry = iterator.next();
System.out.println(entry.getKey() + entry.getValue());
}
System.out.println("*******************");
//获取key的枚举值集合，然后还能借助key得到value值
Enumeration<String> enums = map2.keys();
while (enums.hasMoreElements()) {
String key = enums.nextElement();
System.out.println(key + map2.get(key));
}
System.out.println("*************");
Iterator<String> iterator2 = map2.keySet().iterator();
while (iterator2.hasNext()) {
String key = iterator2.next();
System.out.println(key + map2.get(key));
}
System.out.println("*************");
//map2.elements()仅仅得到value值集合
Enumeration<String> enums2 = map2.elements();
while (enums2.hasMoreElements()) {
System.out.println(enums2.nextElement());
}
}
}
WeakHashMap和HashMap对比
WeakHashMap中key采用“弱引用”方式，只要WeakHashMap中的key不再被外部引用，它就有可能被GC回收。而HashMap中的key采用“强引用”方式，当HashMap中的key没有被外部引用时，只有这个key从HashMap中删除后，才能被GC回收。
TreeMap
首先给出TreeMap的定义：
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}
这里顺便给出NavigableMap接口的定义：
public interface NavigableMap<K,V> extends SortedMap<K,V> {}
由定义我们得知TreeMap是键值对的集合，可克隆，可序列化，同时还能具备一些导航方法，由NavigableMap接口继承了SortedMap知道，TreeMap中的元素是有序的。
的确，TreeMap底层实现是红黑树，根据key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）。
为了更好的介绍TreeMap，我们先复习一下几个树的概念：
二叉查找树
是一个二叉树，每个节点都含有一个comparable的键（以及对应的值），每个节点的键都大于左子树中任意节点的键，而小于右子树中任意节点的键。
平衡二叉树
任意节点的左右子树高度差的绝对值不超过1，这样的树叫平衡二叉树。
定义TreeMap(红黑树)
红黑树是一种近似平衡的二叉查找树，任何一个节点的左右子树高度差不会超过二者中较低那个的一倍。具体来说，红黑树是满足下面条件的二叉查找树：
- 每个节点要么是红色，要么是黑色
- 根节点必须是黑色
- 红色节点不能连续（即红色节点的孩子和父亲不能都是红色）
- 对于每个节点，从该节点到null（树尾端）的任何路径，都含有相同个数的黑色节点
当TreeMap进行插入或者删除时，往往会破坏上面的3或4，需要重新调整查找树使其满足红黑树的条件。这个调整包括颜色调整和结构调整。
对于二叉查找树的调整，首先说几个预备知识：
-
左旋
左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。如图，
左旋
TreeMap中左旋代码如下：
/** From CLR */
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
-
右旋
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
右旋
TreeMap中右旋代码如下：
/** From CLR */
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
TreeMap参考博客
LinkedHashMap
首先给出其定义：
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>{}
由此可以LinkedHashMap是HashMap的一个子类，也实现了Map接口。光从名字上我们就能猜测数LinkedHashMap底层实现应该是链表。
的确，LinkedHashMap使用双向链表维护键值对顺序，迭代顺序和键值对插入顺序保持一致（这点和HashMap、HashTable都不一样哈），LinkedHashMap需要维护键值对的插入顺序，所以性能略低于HashMap。
LinkedHashMap的内部存储结构
entry是下面这样的，相比HashMap，多了两个属性，一个before，一个after。next和after有时候会指向同一个entry，有时候next指向null，而after指向entry。
LinkedHashMap
linkedHashMap和HashMap在存储操作上是一样的，但是LinkedHashMap多的东西是会记住在此之前插入的元素，这些元素不一定是在一个桶中，画个图。
LInkedHashMap
也就是说，对于linkedHashMap的基本操作还是和HashMap一样，在其上面加了两个属性，也就是为了记录前一个插入的元素和记录后一个插入的元素。注意一点，会有一个header的实体，目的是为了记录第一个插入的元素是谁，在遍历的时候能够找到第一个元素。
IdentityHashMap和HashMap区别
IdentityHashMap使用==（对比的引用）来判断key是否相等，HashMap使用equals来判断key是否相等。因此IdentityHashMap可以存放相同的key值。（只要引用不同就行了嘛）
比如：
package cn.ihep.collection;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.Map;
import org.junit.Test;
public class TestIdentityHashMap {
@Test
public void test() {
System.out.println("======================");
IdentityHashMap<String, String> ih = new IdentityHashMap<>();
ih.put("a", "tom");
ih.put(new String("a"), "Jim");
ih.put("a", "Jerry");
System.out.println(ih.size());
Iterator<Map.Entry<String, String>> it = ih.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, String> entry = it.next();
System.out.println(entry.getKey() + entry.getValue());
}
}
}
//输出结果：
======================
2
aJerry
aJim
ConcurrentHashMap
底层采用分段的数组+链表实现，线程安全.
Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
引入了一个“分段锁”的概念，具体可以理解为把一个大的Map拆分成N个小的HashTable，根据key.hashCode()来决定把key放到哪个HashTable中。在ConcurrentHashMap中，就是把Map分成了N个Segment，put和get的时候，都是现根据key.hashCode()算出放到哪个Segment中.通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
网友评论