关联博文
认真研究JDK1.7下HashMap的循环链表和数据丢失问题
【1】概念介绍
Map用于保存具有映射关系的数据，因此Map集合里保存着两组值，一组值用于保存Map里的key，另外一组值用于保存Map里的value。key和value都可以是任何引用类型的数据。Map的Key值为set，不允许重复，即同一个Map对象的任何两个key通过equals方法比较结果总是返回false。关于Map，我们要从代码复用的角度去理解
java是先实现了Map，然后通过包装了一个所有value都为null的Map就实现了Set集合。
Map的这些实现类和子接口中key集的存储形式和Set集合完全相同(即key不能重复)。Map的这些实现类和子接口中value集的存储形式和List非常类似(即value可以重复、根据索引来查找)
常用String类作为Map的“键”。key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value。Map接口继承树如下图所示：常见的有HashMap、TreeMap
Map的key、value和记录(Entry)如下图所示：
【2】HashMap
HashMap是 Map 接口使用频率最高的实现类。允许使用null键和null值(只允许一个null键)，与HashSet一样，不保证映射的顺序。
HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等。
HashMap 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true。HashMap的继承结果如下图所示：
【3】LinkedHashMap
同与LinkedHashSet是有序的类似，LinkedHashMap使用双向链表来维护key-value对的次序，该链表负责维护Map的迭代顺序，与key-value对的插入顺序一致(注意和TreeMap对所有的key-value进行排序进行区分)。
LinkedHashMap 是 HashMap 的子类，相对于HashMap，LinkedHashMap可以记录插入key-value的顺序，但是并不能再对其进行自定义排序。
LinkedHashMap类继承结构如下所示：
【4】TreeMap
① 结构
正如Set接口派生出SortedSet子接口，SortedSet接口有一个TreeSet实现类一样。Map接口也派生出一个SortedMap子接口，SortedMap接口也有一个TreeMap实现类 。
TreeMap就是一个红黑树数据结构，每个key-value对即作为红黑树的一个节点。TreeMap存储key-value对(节点)时，需要根据key对节点进行排序。TreeMap可以保证所有的key-value对处于有序状态。
同样，TreeMap也有两种排序方式: 自然排序、定制排序。
② TreeMap的 Key 的排序
自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException。
定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对 TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现 Comparable 接口。
// 创建默认排序的TreeMap TreeMap<String, String> map = new TreeMap<String, String>(); // 创建自定义排序的TreeMap TreeMap<String, String> map = new TreeMap<String, String>(new Comparator<String>() { @Override public int compare(String o1, String o2) { return o2.compareTo(o1); } });
TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0。
③ 排序规则
3.1 两个字符串 s1, s2比较
- 如果s1和s2是父子串关系，则 子串 < 父串
- 如果非为父子串关系， 则从第一个非相同字符来比较。
例子 s1 = "ab", s2 = "ac" 这种情况算法规则是从第二个字符开始比较， 由于'b' < 'c' 所以 "ab" < "ac"
3.2 字符间的比较，是按照字符的字节码（ascii）来比较
3.3 compareTo 实现机制：对于字符串来说，字典排序规则；对于数字来说，直接按照大小排序。
若使用自定义类作为TreeMap的key，所属类需要重写equals()和hashCode()方法，且equals()方法返回true时，compareTo()方法应返回0(equasls方法和compareTo方法保持一致)。
相对于LinkedHashMap只是维护插入key-value的顺序，TreeMap同时允许自然排序和定制排序！
④ 如果想实现value排序呢
没有办法在treeMap自身上实现，只能将map的value拿出来进行排序。实例如下：
HashMap onlyMap=new HashMap<>(); //...put data ArrayList<Map.Entry<String, Object>> arrayList = new ArrayList<>(onlyMap.entrySet()); Collections.sort(arrayList, new Comparator<Map.Entry<String, Object>>() { @Override public int compare(Map.Entry<String, Object> o1, Map.Entry<String, Object> o2) { return o2.getValue().toString().compareTo(o1.getValue().toString()); } });
【5】Hashtable
Hashtable是个古老的 Map 实现类，线程安全。与HashMap不同，Hashtable 不允许使用 null 作为 key 和 value。与HashMap一样，Hashtable 也不能保证其中 Key-Value 对的顺序。
Hashtable判断两个key相等、两个value相等的标准，与hashMap一致。Hashtable继承自Dictionary类并实现了Map接口，而HashMap是Java1.2引进的Map interface的一个实现。
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable {
HashTable是通过给整张散列表加锁的方式来保证线程安全,这种方式保证了线程安全，但是并发执行效率低下。建议采用ConcurrentHashMap。
【6】Properties
Properties 类是 Hashtable 的子类，该对象用于处理属性文件,也是线程安全的。
Properties对象在处理属性文件时特别方便(windows平台上的.ini文件)，Properties类可以把Map对象和属性文件关联起来，从而可以把Map对象中的key-value对写入到属性文件中，也可以把属性文件中的"属性名-属性值"加载到Map对象中
由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型。
存取数据时，建议使用setProperty(String key,String value)方法和getProperty(String key)方法。
实例代码如下：
Properties pros = new Properties(); pros.load(new FileInputStream("jdbc.properties")); String user = pros.getProperty("user"); System.out.println(user);
【7】WeakHashMap
WeakHashMap与HashMap的用法基本相似。区别在于，HashMap的key保留了对实际对象的"强引用"，这意味着只要该HashMap对象不被销毁，该HashMap所引用的对象就不会被垃圾回收。
但WeakHashMap的key只保留了对实际对象的弱引用，这意味着如果WeakHashMap对象的key所引用的对象没有被其他强引用变量所引用，则这些key所引用的对象可能被垃圾回收，当垃圾回收了该key所对应的实际对象之后，WeakHashMap也可能自动删除这些key所对应的key-value对。
【8】IdentityHashMap
IdentityHashMap的实现机制与HashMap基本相似，在IdentityHashMap中，当且仅当两个key严格相等(key1 == key2) 时，IdentityHashMap才认为两个key相等。
import java.util.*; public class IdentityHashMapTest { public static void main(String[] args) { IdentityHashMap ihm = new IdentityHashMap(); //下面两行代码将会向IdentityHashMap对象中添加两个key-value对 ihm.put(new String("语文") , 89); ihm.put(new String("语文") , 78); //下面两行代码只会向IdentityHashMap对象中添加一个key-value对 ihm.put("java" , 93); ihm.put("java" , 98); System.out.println(ihm); } }
在ScheduledAnnotationBeanPostProcessor中就使用了IdentityHashMap来维护每个bean的计划任务。
private final Map<Object, Set<ScheduledTask>> scheduledTasks = new IdentityHashMap<>(16);
【9】EnumMap
EnumMap是一个与枚举类一起使用的Map实现，EnumMap中的所有key都必须是单个枚举类的枚举值。
创建EnumMap时必须显式或隐式指定它对应的枚举类。EnumMap根据key的自然顺序(即枚举值在枚举类中的定义顺序)。
import java.util.*; enum Season { SPRING,SUMMER,FALL,WINTER } public class EnumMapTest { public static void main(String[] args) { //创建一个EnumMap对象，该EnumMap的所有key //必须是Season枚举类的枚举值 EnumMap enumMap = new EnumMap(Season.class); enumMap.put(Season.SUMMER , "夏日炎炎"); enumMap.put(Season.SPRING , "春暖花开"); System.out.println(enumMap); } }
与创建普通Map有所区别的是，创建EnumMap是必须指定一个枚举类，从而将该EnumMap和指定枚举类关联起来。
【10】ConcurrentHashMap
虽然不能保持排序（如TreeMap 、LinkedHashMap），但是在并发场景为了线程安全可以常常看到这个ConcurrentHashMap。其key和value均不可以为null
其使用Segment(分段锁机制)的思想来保持线程并发安全。与HashTable不同的是，HashTable只能由一个线程操作， ConcurrentHashMap可以让一个线程操作第一个Segment，另一个线程操作另一个Segment。
从JDK1.8开始, ConcurrentHashMap数据结构与1.8中的HashMap保持一致,均为数组+链表+红黑树，是通过乐观锁+Synchroni zed来保证线程安全的。
当多线程并发向同一个散列桶添加元素时。若散列桶为空,此时触发乐观锁机制,线程会获取到桶中的版本号，在添加节点之前，判断线程中获取的版本号与桶中实际存在的版本号是否一致,若一致,则添加成功，若不一致，则让线程自旋。
若散列桶不为空，此时使用Synchronized来保证线程安全，先访问到的线程会给桶中的头节点加锁，从而保证线程安全。
10】 在多线程环境中使用HashMap有什么问题？调用put()方法什么时候会进入无限循环？
HashMap本身没有什么问题，有没有问题取决于你是如何使用它的。
比如，你在一个线程里初始化了一个HashMap然后在多个其他线程里对其进行读取，这肯定没有任何问题。
当有多于一个线程对HashMap进行修改操作的时候才会真正产生问题，比如增加、删除、更新键值对的时候。
因为put()操作可以造成重新分配存储大小（re-sizeing）的动作，因此有可能造成无限循环的发生，所以这时需要使用Hashtable或者ConcurrentHashMap(更好)。
