专栏首页KEN DO EVERTHING「 深入浅出 」集合Map

「 深入浅出 」集合Map

前面已经介绍完了Collection接口下的集合实现类,今天我们来介绍Map接口下的几个重要的集合实现类HashMap,Hashtable,LinkedHashMap,TreeMap。

HashMap

(最常用,随机访问速度快,无序,可存一个Null key,多个Null value,非同步)

HashMap是最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值,具有很快的访问速度,遍历时,取得数据的顺序是完全随机的。因为键对象不可以重复,所以HashMap最多只允许一条记录的键为Null,允许多条记录的值为Null,是非同步的

Hashtable

(HashMap线程安全版,效率低,key和value都不能为null,同步)

Hashtable与HashMap类似,是HashMap的线程安全版,它支持线程同步,即任一时刻只有一个线程能写Hashtable,因此也导致了Hashtale在写入时会比较慢,它继承自Dictionary类,不同的是它不允许记录的键或者值为null,同时效率较低。

LinkedHashMap

(有序,遍历性能好,可存一个Null key,多个Null值,非同步)

LinkedHashMap是由散列表+循环双向链表实现的。LinkedHashMap需要维护元素的插入顺序,因此性能略低于HashMap的性能;但是因为它以链表来维护内部顺序,所以在迭代访问Map里的全部元素时有较好的性能。迭代输出LinkedHashMap的元素时,将会按照添加key-value对的顺序输出,有HashMap的全部特性。

TreeMap

(有序,可自定义排序,key不能为空,非同步)

TreeMap 是一个有序的key-value集合,它是通过红黑树实现的,每个key-value对即作为红黑树的一个节点。能够把它保存的记录根据键排序,默认是按键值的升序排序(自然顺序),也可以指定排序的比较器,不允许key值为空,非同步的。

HashMap的实现

下面具体说说hashMap的实现原理(基于jdk1.7)

HashMap的构造函数
//内部数组的默认初始容量,作为hashmap的初始容量
//2的4次方,2的n次方的作用是减少hash冲突
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//默认的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认负载因子,当容器使用率达到这个75%的时候就扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//当数组表还没扩容的时候,一个共享的空表对象
static final Entry<?,?>[] EMPTY_TABLE = {};

//内部数组表,用来装entry,大小只能是2的n次方。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

// 默认构造函数。
HashMap()

// 指定“容量大小”的构造函数
HashMap(int capacity)

// 指定“容量大小”和“加载因子”的构造函数
HashMap(int capacity, float loadFactor)

// 包含“子Map”的构造函数
HashMap(Map<? extends K, ? extends V> map)

HashMap有以上4种构造方法,其中HashMap(int capacity)和HashMap(int capacity, float loadFactor)可以指定容量或加载因子。

容量即是HashMap所能存储的"最大"容量(注意:最大加了双引号,因为hashMap会做扩容) 加载因子是HashMap在其容量做扩容前可以达到多满的程度。当容量超出了加载因子与当前容量的乘积时,hashMap会进行扩容达到原来的2倍容量。

当使用默认构造函数HashMap()构建时,会使用默认的容量DEFAULT_INITIAL_CAPACITY = 1 << 4(即是16)和默认加载因子DEFAULT_LOAD_FACTOR = 0.75f

注意:使用HashMap时,尽量指定它的初始容量,因为扩容是按1倍扩展的,如果频繁的扩容会导致性能下降,内存的消耗。

底层存储Entry

上次文中错误是这一块内容,jdk7中低层存储是Entry,jdk8中低层存储是Node

HashMap是通过"拉链法"实现的哈希表。其底层存储结构是Entry数组,Entry实际上就是一个单向链表,哈希表的"key-value键值对"都是存储在Entry中的。

Entry是HashMap的内部类,如下

/**
* 内部类
* hashmap中每一个键值对都是存在Entry对象中,entry还存储了自己的hash值等信息
* Entry被储存在hashmap的内部数组中。
* @param <K> 键值名key
* @param <V> 键值value
*/
static class Entry<K,V> implements Map.Entry<K,V> {
        //键对象,final修饰,不可变
        final K key;
        //值对象
        V value;
        //下一个键值对Entry对象
        Entry<K,V> next;
        //键对象的哈希值
        int hash;

        //提供了一个有参构造方法
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
       ...
    }

Java中数据存储方式最底层的两种结构:数组和链表。

数组的特点:连续空间,寻址迅速,但是在刪除或者添加元素的时候需要有较大幅度的移动,所以查询速度快,增刪较慢。 而链表正好相反,由于空间不连续,寻址困难,增刪元素只需修改指針,所以查询速度慢、增刪快。 有沒有一种数组结构來综合一下数组和链表,以便发挥它们各自的优势?答案是肯定的!就是:哈希表(HashMap)。 哈希表具有较快(常量级)的查询速度,及相对较快的增刪速度,所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”,我們可以理解为“链表的数组”,如下图:

从图中,我们可清楚地看出哈希表是由数组+链表组成的,一个长度为16的数组中,每個元素存储的是一个链表的头结点。 通过hash(key)方法判断出元素的存储位置,如果hash(key)值相等,则都存入该hash值所对应的链表中。

这个hash(key)方法是HashMap的一个方法,与Object类的hashCode()是有所区别的,hash(key)在hashCode()方法的基础做一些修改。

HashMap遍历

有3种遍历方式,map.keySet()、map.values()、Map.Entry,例子代码如下

public class Demo2 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<Integer, String>();
        map.put(1, "aaaa");
        map.put(2, "bbbb");
        map.put(3, "cccc");
        System.out.println(map);


        // 第一种方式: 使用keySet
        // 需要分别获取key和value,没有面向对象的思想
        // Set<K> keySet() 返回所有的key对象的Set集合
        Set<Integer> ks = map.keySet();
        Iterator<Integer> it = ks.iterator();
        while (it.hasNext()) {
            Integer key = it.next();
            String value = map.get(key);
            System.out.println("key=" + key + " value=" + value);
        }

        // 第二种方式:map.values()
        // 通过values 获取所有值,不能获取到key对象
        // Collection<V> values()
        Collection<String> vs = map.values();
        Iterator<String> it = vs.iterator();
        while (it.hasNext()) {
            String value = it.next();
            System.out.println(" value=" + value);
                }

        // 第三种方式: Map.Entry对象 推荐使用 重点
        // Set<Map.Entry<K,V>> entrySet()
        // 返回的Map.Entry对象的Set集合 Map.Entry包含了key和value对象
        Set<Map.Entry<Integer, String>> es = map.entrySet();

        Iterator<Map.Entry<Integer, String>> it = es.iterator();

        while (it.hasNext()) {

            // 返回的是封装了key和value对象的Map.Entry对象
            Map.Entry<Integer, String> en = it.next();

            // 获取Map.Entry对象中封装的key和value对象
            Integer key = en.getKey();
            String value = en.getValue();

            System.out.println("key=" + key + " value=" + value);
          }
    }
}

性能分析及适用场景

  • HashMap与Hashtable实现机制几乎一样,但是HashMap比Hashtable性能更好些。
  • LinkedHashMap比HashMap慢一点,因为它需要维护一个双向链表。
  • TreeMap比HashMap与Hashtable慢(尤其在插入、删除key-value时更慢),因为TreeMap底层采用红黑树来管理键值对。

适用场景:

  • 一般的应用场景,尽可能多考虑使用HashMap,因为其为快速查询设计的。
  • 如需特定的排序时,考虑使用TreeMap。
  • 如仅仅需要插入的顺序时,考虑使用LinkedHashMap。

集合篇系列上讲完了,Queue就不讲了,实在是很少用到,请自行学习哈~

本文分享自微信公众号 - java从心(javaFollowHeart)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「 深入浅出 」集合Map

    (最常用,随机访问速度快,无序,可存一个Null key,多个Null value,非同步)

    KEN DO EVERTHING
  • 一组漫画完美总结互联网人生

    1991年,万维网(World Wide Web)向公众开放,标志着互联网的诞生。如今人类的生活被互联网极大地改变,以至于没有网络的生活几乎是难以想象的...

    KEN DO EVERTHING
  • 「 从0到1学习微服务SpringCloud 」13 断路器Hystrix

    在微服务架构中,很多情况下,各个服务之间是相互依赖,一个服务可能会调用了好几个其他服务,假设其中有一个服务故障,便会产生级联故障,最终导致整个系统崩溃无法使用(...

    KEN DO EVERTHING
  • java中HashMap详解

    当程序试图将多个 key-value 放入 HashMap 中时,以如下代码片段为例:

    用户5640963
  • Java HashMap那点事

    HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

    Java后端工程师
  • 大牛带你深入解读HashMap

    HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

    慕容千语
  • Java中HashMap详解

    HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

    哲洛不闹
  • HashSet/HashMap详解

    HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

    似水的流年
  • HashMap解析

    linxinzhe
  • 算法踩坑小记

    反之,结果为最大值或者接近无穷大的数,甚至溢出有效范围,那就可能出现"梯度爆炸"的问题.

    cpuimage

扫码关注云+社区

领取腾讯云代金券