数据结构之Map基础入门与详解

流烟默

12035人浏览 · 2016-11-18 11:08:32

流烟默 · 2016-11-18 11:08:32 发布

关联博文
数据结构之Map基础入门与详解
 认真学习Java集合之HashMap的实现原理
 认真研究HashMap的读取和存放操作步骤
 认真研究HashMap的初始化和扩容机制
 认真研究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);
   }
}