欢迎访问昆山宝鼎软件有限公司网站! 设为首页 | 网站地图 | XML | RSS订阅 | 宝鼎邮箱 | 后台管理


新闻资讯

MENU

软件开发知识

Map各人族的那 图纸加密 点事儿(1) :Map

点击: 次  来源:昆山软开发 时间:2018-09-04

原文出处: SylvanasSun’s Blog

Map


Map是一种用于快速查找的数据布局,它以键值对的形式存储数据,每一个键都是独一的,且对应着一个值,假如想要查找Map中的数据,只需要传入一个键,Map会对键举办匹配并返回键所对应的值,可以说Map其实就是一个存放键值对的荟萃。Map被各类编程语言遍及利用,只不外在名称上大概会有些夹杂,像Python中叫做字典(Dictionary),也有些语言称其为关联数组(Associative Array),但其实它们都是一样的,都是一个存放键值对的荟萃。至于Java中常常用到的HashMap也是Map的一种,它被称为散列表,关于散列表的细节我会在本文中表明HashMap的源码时提及。

Java还提供了一种与Map密切相关的数据布局:Set,它是数学意义上的荟萃,特性如下:

  • 无序性:一个荟萃中,每个元素的职位都是沟通的,元素之间也都是无序的。不外Java中也提供了有序的Set,这点倒是没有完全遵循。
  • 互异性:一个荟萃中,任何两个元素都是不沟通的。
  • 确定性:给定一个荟萃以及其任一元素,该元素属于可能不属于该荟萃是必需可以确定的。
  • 很明明,Map中的key就很切合这些特性,Set的实现其实就是在内部利用Map。譬喻,HashSet就界说了一个范例为HashMap的成员变量,向HashSet添加元素a,等同于向它内部的HashMap添加了一个key为a,value为一个Object工具的键值对,这个Object工具是HashSet的一个常量,它是一个虚拟值,没有什么实际寄义,源码如下:

    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    小插曲事后,让我们接着说Map,它是JDK的一个顶级接口,提供了三种荟萃视图(Collection Views):包括所有key的荟萃、包括所有value的荟萃以及包括所有键值对的荟萃,Map中的元素顺序与它所返回的荟萃视图中的元素的迭代顺序相关,也就是说,Map自己是不担保有序性的,虽然也有破例,好比TreeMap就对有序性做出了担保,这主要因为它是基于红黑树实现的。

    所谓的荟萃视图就是由荟萃自己提供的一种会见数据的方法,同时对视图的任何修改也会影响到荟萃。比如Map.keySet()返回了它包括的key的荟萃,假如你挪用了Map.remove(key)那么keySet.contains(key)也将返回false,再好比说Arrays.asList(T)可以把一个数组封装成一个List,昆山软件开发,这样你就可以通过List的API来会见和操纵这些数据,如下列示例代码:

    String[] strings = {"a", "b", "c"};
    List<String> list = Arrays.asList(strings);
    System.out.println(list.get(0)); // "a"
    strings[0] = "d";
    System.out.println(list.get(0)); // "d"
    list.set(0, "e");
    System.out.println(strings[0]); // "e"

    是不是感受很神奇,其实Arrays.asList()只是将传入的数组与Arrays中的一个内部类ArrayList(留意,它与java.util包下的ArrayList不是同一个)做了一个”绑定“,在挪用get()时会直接按照下标返回数组中的元素,而挪用set()时也会直接修改数组中对应下标的元素。相对付直接复制来说,荟萃视图的利益是内存操作率更高,假设你有一个数组,又很想利用List的API来操纵它,那么你不消new一个ArrayList以拷贝数组中的元素,只需要一点特另外内存(通过Arrays.ArrayList对数组举办封装),原始数据依然是在数组中的,并不会复制成多份。

    Map接口类型了Map数据布局的通用API(也含有几个用于简化操纵的default要领,default是JDK8的新特性,它是接口中声明的要领的默认实现,即非抽象要领)而且还在内部界说了Entry接口(键值对的实体类),在JDK中提供的所有Map数据布局都实现了Map接口,下面为Map接口的源码(代码中的注释太长了,根基都是些实现的类型,为了篇幅我就只管省略了)。

    package java.util;
    import java.util.function.BiConsumer;
    import java.util.function.BiFunction;
    import java.util.function.Function;
    import java.io.Serializable;
    public interface Map<K,V> {
    
    	// 查询操纵
        /**
         * 返回这个Map中所包括的键值对的数量,假如大于Integer.MAX_VALUE,
         * 则应该返回Integer.MAX_VALUE。
         */
        int size();
        /**
         * Map是否为空。
         */
        boolean isEmpty();
        /**
     	 * Map中是否包括key,假如是返回true,不然false。
         */
        boolean containsKey(Object key);
        /**
         * Map中是否包括value,假如是返回true,不然false。
         */
        boolean containsValue(Object value);
        /**
         * 按照key查找value,假如Map不包括该key,则返回null。
         */
        V get(Object key);
        // 修改操纵
        /**
         * 添加一对键值对,假如Map中已含有这个key,那么新value将包围掉旧value,
         * 并返回旧value,假如Map中之前没有这个key,那么返回null。
         */
        V put(K key, V value);
        /**
         * 删除指定key并返回之前的value,假如Map中没有该key,则返回null。
         */
        V remove(Object key);
        // 批量操纵
        /**
         * 将指定Map中的所有键值对批量添加到当前Map。
         */
        void putAll(Map<? extends K, ? extends V> m);
        /**
         * 删除Map中所有的键值对。
         */
        void clear();
        // 荟萃视图
        /**
         * 返回包括Map中所有key的Set,对该视图的所有修改操纵会对Map发生同样的影响,反之亦然。
         */
        Set<K> keySet();
        /**
         * 返回包括Map中所有value的荟萃,昆山软件开发,对该视图的所有修改操纵会对Map发生同样的影响,反之亦然。
         */
        Collection<V> values();
        /**
         * 返回包括Map中所有键值对的Set,对该视图的所有修改操纵会对Map发生同样的影响,昆山软件开发,反之亦然。
         */
        Set<Map.Entry<K, V>> entrySet();
        /**
         * Entry代表一对键值对,类型了一些根基函数以及几个已实现的类函数(各类较量器)。
         */
        interface Entry<K,V> {
    
            K getKey();
            V getValue();
            V setValue(V value);
            boolean equals(Object o);
            int hashCode();
            public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
                return (Comparator<Map.Entry<K, V>> & Serializable)
                    (c1, c2) -> c1.getKey().compareTo(c2.getKey());
            }
            public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
                return (Comparator<Map.Entry<K, V>> & Serializable)
                    (c1, c2) -> c1.getValue().compareTo(c2.getValue());
            }
            public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
                Objects.requireNonNull(cmp);
                return (Comparator<Map.Entry<K, V>> & Serializable)
                    (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
            }
            public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
                Objects.requireNonNull(cmp);
                return (Comparator<Map.Entry<K, V>> & Serializable)
                    (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
            }
        }
        // 较量和hashing
        /**
         * 将指定的工具与此Map举办较量是否相等。
         */
        boolean equals(Object o);
        /**
         * 返回此Map的hash code。
         */
        int hashCode();
        // 默认要领(非抽象要领)
        /**
         * 按照key查找value,假如该key不存在或便是null则返回defaultValue。
         */
        default V getOrDefault(Object key, V defaultValue) {
            V v;
            return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue;
        }
        /**
         * 遍历Map并对每个键值对执行指定的操纵(action)。
         * BiConsumer是一个函数接口(具有一个抽象要领的接口,用于支持Lambda),
         * 它代表了一个接管两个输入参数的操纵,且不返回任何功效。
         * 至于它奇怪的名字,按照Java中的其他函数接口的定名类型,Bi应该是Binary的缩写,意思是二元的。
         */
        default void forEach(BiConsumer<? super K, ? super V> action) {
            Objects.requireNonNull(action);
            for (Map.Entry<K, V> entry : entrySet()) {
                K k;
                V v;
                try {
                    k = entry.getKey();
                    v = entry.getValue();
                } catch(IllegalStateException ise) {
                    // this usually means the entry is no longer in the map.
                    throw new ConcurrentModificationException(ise);
                }
                action.accept(k, v);
            }
        }
        /** 
         * 遍历Map,然后挪用传入的函数function生成新value对旧value举办替换。
         * BiFunction同样是一个函数接口,它接管两个输入参数而且返回一个功效。
         */
        default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
            Objects.requireNonNull(function);
            for (Map.Entry<K, V> entry : entrySet()) {
                K k;
                V v;
                try {
                    k = entry.getKey();
                    v = entry.getValue();
                } catch(IllegalStateException ise) {
                    // this usually means the entry is no longer in the map.
                    throw new ConcurrentModificationException(ise);
                }
                // ise thrown from function is not a cme.
                v = function.apply(k, v);
                try {
                    entry.setValue(v);
                } catch(IllegalStateException ise) {
                    // this usually means the entry is no longer in the map.
                    throw new ConcurrentModificationException(ise);
                }
            }
        }
        /**
         * 假如指定的key不存在可能关联的value为null,则添加键值对。
         */
        default V putIfAbsent(K key, V value) {
            V v = get(key);
            if (v == null) {
                v = put(key, value);
            }
            return v;
        }
        /**
         * 当指定key关联的value与传入的参数value相等时删除该key。
         */
        default boolean remove(Object key, Object value) {
            Object curValue = get(key);
            if (!Objects.equals(curValue, value) ||
                (curValue == null && !containsKey(key))) {
                return false;
            }
            remove(key);
            return true;
        }
        /**
         * 当指定key关联的value与oldValue相等时,利用newValue举办替换。
         */
        default boolean replace(K key, V oldValue, V newValue) {
            Object curValue = get(key);
            if (!Objects.equals(curValue, oldValue) ||
                (curValue == null && !containsKey(key))) {
                return false;
            }
            put(key, newValue);
            return true;
        }
        /**
         * 当指定key关联到某个value时举办替换。
         */
        default V replace(K key, V value) {
            V curValue;
            if (((curValue = get(key)) != null) || containsKey(key)) {
                curValue = put(key, value);
            }
            return curValue;
        }
        /**
         * 当指定key没有关联到一个value可能value为null时,挪用mappingFunction生成值并添加键值对到Map。
         * Function是一个函数接口,它接管一个输入参数并返回一个功效,假如mappingFunction返回的功效
         * 也为null,那么将不会挪用put。
         */
        default V computeIfAbsent(K key,
                Function<? super K, ? extends V> mappingFunction) {
            Objects.requireNonNull(mappingFunction);
            V v;
            if ((v = get(key)) == null) {
                V newValue;
                if ((newValue = mappingFunction.apply(key)) != null) {
                    put(key, newValue);
                    return newValue;
                }
            }
            return v;
        }
        /**
         * 当指定key关联到一个value而且不为null时,挪用remappingFunction生成newValue,
         * 假如newValue不为null,那么举办替换,不然删除该key。
         */
        default V computeIfPresent(K key,
                BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
            Objects.requireNonNull(remappingFunction);
            V oldValue;
            if ((oldValue = get(key)) != null) {
                V newValue = remappingFunction.apply(key, oldValue);
                if (newValue != null) {
                    put(key, newValue);
                    return newValue;
                } else {
                    remove(key);
                    return null;
                }
            } else {
                return null;
            }
        }
        /**
         * remappingFunction按照key与其相关联的value生成newValue,
         * 当newValue便是null时删除该key,不然添加可能替换旧的映射。
         */
        default V compute(K key,
                BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
            Objects.requireNonNull(remappingFunction);
            V oldValue = get(key);
            V newValue = remappingFunction.apply(key, oldValue);
            if (newValue == null) {
                // delete mapping
                if (oldValue != null || containsKey(key)) {
                    // something to remove
                    remove(key);
                    return null;
                } else {
                    // nothing to do. Leave things as they were.
                    return null;
                }
            } else {
                // add or replace old mapping
                put(key, newValue);
                return newValue;
            }
        }
        /**
         * 当指定key没有关联到一个value可能value为null,将它与传入的参数value
         * 举办关联。不然,挪用remappingFunction生成newValue并举办替换。
         * 假如,newValue便是null,那么删除该key。
         */
        default V merge(K key, V value,
                BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
            Objects.requireNonNull(remappingFunction);
            Objects.requireNonNull(value);
            V oldValue = get(key);
            V newValue = (oldValue == null) ? value :
                       remappingFunction.apply(oldValue, value);
            if(newValue == null) {
                remove(key);
            } else {
                put(key, newValue);
            }
            return newValue;
        }
    }

    需要留意一点,这些default要领都长短线程安详的,任何担保线程安详的扩展类都必需重写这些要领,譬喻ConcurrentHashMap。