专栏首页mini188多用多学之Java中的Set,List,Map

多用多学之Java中的Set,List,Map

        很长时间以来一直代码中用的比较多的数据列表主要是List,而且都是ArrayList,感觉有这个玩意就够了。ArrayList是用于实现动态数组的包装工具类,这样写代码的时候就可以拉进拉出,迭代遍历,蛮方便的。

        也不知道从什么时候开始慢慢的代码中就经常会出现HashMap和HashSet之类的工具类。应该说HashMap比较多一些,而且还是面试经典题,平时也会多看看。开始用的时候简单理解就是个键值对应表,使用键来找数据比较方便。随后深入了解后发现这玩意还有点小奥秘,特别是新版本的JDK对HashMap的改成树后,代码都有点小复杂咯。

        Set开始用的较少,只是无意中在一个代码中发现一个TreeSet,发现这个类可以自带排序,感觉蛮有点意思,才慢慢的发现这也是个好工具啊。

        代码写的多了就感觉到基础的重要性,所以在此写一篇小文简单的整理一下对集合的一些知识。

好了,简单的整理一下:

  • List:即是列表,支持数组、链表的功能,一般都是线性的
  • Map:即是映射表,存储的是键与值的对应关系
  • Set:即是集合的意思,主要是用于排重数据及排序

先来看看List

List是用于存放线性数据的一种容器,比如:用于数组的ArrayList和用于链表的LinkedList。

ArrayList

这是一个数组列表,不过提供了自动扩容的功能,实现List接口,外部操作都是通过接口申明的方法访问,这样即安全又方便。

ArrayList的关键就是自动扩容,在对象初始化时可以设定初始容量,也可以按默认的容量。如果对数组大小没有特别明确可以不指定初始大小,如果明确的话可以指定一个大小,这样减少动态扩容时产生的卡顿。说到这就要说一下扩容是怎么实现的了,看下面的代码:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

grow是在ArrayList在添加元素或者一些容易检查时会触发的一个方法。主要过程:

1、得到数组的长度,并对其进行右移,这样就相当于oldCapacity/2,得到新的长度

2、如果这个长度小于最小容量那么直接就用最小容易

3、如果大于了最大容易则取一个最大值,这里会调用一个hugeCapacity方法,主要是比较minCapacity与MAX_ARRAY_SIZE的,如果minCapacity大于MAX_ARRAY_SIZE则取Integer.MAX_VALUE,否则就取MAX_ARRAY_SIZE,有意思的是MAX_ARRAY_SIZE取的是Integer.MAX_VALUE - 8;并不知道这样做的意义是什么

4、最后就是调用一个复制方法将现有数复制到一个新的数组中。

因为有这个复制过程,如果数组比较大,那么老是触发扩容当然就会出现卡顿的情况。所以如果一开始就知道最大值而且很容易增长到这个值,那么开始初始化时就指定大小会有一定的作用。

LinkedList

这是针对链表的工具类,链表的优秀是添加删除啥的比较快,但是查找会慢一些。

至于代码好像也没什么特别的,就是一串指针链接起来,当然Java中就使用对象来代替,建立一个Node的对象,Node本身指向了前一个Node和后一个Node,这就是链表的结构:

 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
 
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

然后用两个Node指向头和尾就完成了,下面的代码:

 /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
 
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

看一个add操作:

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

过往就是:

1、获取到最后的Node并放在l中

2、创建一个新的Node,将数据取到这个Node中,创建过程会将新Node的prev指向l,这样就接上了链

3、然后将last指向这个新Node

4、然判断l是否null,如果是null说明是空链表,新node就是第一个元素,这样first也要指向newNode

5、如果不为空则将l的next指向newNode

6、累加计数器

删除操作也是这种Node的前后Node指向移动操作。

再来看看Map

Map是键与值做一个映射表的应用,主要的实现类:HashMap,HashTable,TreeMap

HashMap和HashTable

使用hash算法进行键值映射的就是HashMap啦,HashTable是带有同步的线程安全的类,它们两主要的区别就是这个。原理也类似,都是通过桶+链来组合实现。桶是用来存Key的,而由于Hash碰撞的原因值需要用一个链表来存储。

  • 的意义在于高效,通过Hash计算可以一步定位
  • 链表的意义在于存取重复hash的数据

具体的原理以前写过一篇《学习笔记:Hashtable和HashMap》

只不过看JDK1.8的HashMap换了存储结构,采用红黑树的结构,这样可能是解决链表查找效率问题吧?具体没有细研究。

TreeMap

看过TreeMap的代码后发现还是使用的树结构,红黑树。由于红黑树是有序的,所以自然带排序功能。当然也可通过comparator来指定比较方法来实现特定的排序。

因为采用了树结构存储那么添加和删除数据时会麻烦一些,看一下put的代码:

public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
            compare(key, key); // type (and possibly null) check
 
            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

1、先是检查根节点是否存在,不存在说明是第一条数据,直接作为树的根

2、判断是否存在比较器,如果存在则使用比较器进行查找数据的存放位置,如果比较器返回结果小于0取左,大于0取右,否则直接替换当前节点的值

3、如果不存在比较器则key直接与节点的key比较,比较和前面方法一样

4、接下来就是在找到的parent上创建一个子节点,并放入左或者右子节点中

5、fixAfterInsertion是对节点进行着色

6、累加器处理

在remove操作时也会有点麻烦,除了删除数据外,还要重新平衡一下红黑树。

另外,TreeMap实现了NavigableMap<K,V>接口,所以也提供了对数据集合的一些返回操作。

最后看看Set

Set主要是两类应用:HashSet和TreeSet。

HashSet

字面意思很明确,使用了Hash的集合。这种集合的特点就是使用Hash算法存数据,所以数据不重复,存取都相对较快。怎么做到的呢?

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

原来是存在一个map对象中,再看map是个啥?

private transient HashMap<E,Object> map;

是个HashMap,了解HashMap的就明白,这样的数据是不会重复的。因为存入时是鼗对象本身作为Key来存的,所以在HashMap中只会存在一份。

了解了这点其他的东西就非常明白了。

TreeSet

这个集合是用于对集合进行排序的,也就是除了带有排重的能力外,还可以自带排序功能。只不过看了TreeSet的代码发现,其就是在TreeMap的基础实现的。更准确的说应该是NavigableMap的派生类。默认不指定map情况下TreeSet是以TreeMap为基础的。

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

所以,这里可能更关注的是TreeSet是如何排重呢?看一下add的方法吧:

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

和HashSet有点类似,都是基于Map的特性来实现排重。确实简单而且有效。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据库SQL,NoSQL之小感悟

    遇到1000万数据表 最近遇到一个问题,就是单表数据过1000万的存储及查询问题。举个例子:1000万的数据存在一个表中,字段4-5个样子,日常 开发中难免要做...

    用户1105954
  • 学习笔记:发现一个IE版本判断的好方法

    web开发就不得不面对浏览器兼容性问题,特别是IE的兼容问题。在前端代码中经常要处理一些兼容格式,为了解决这个问题网上找了找识别浏览器版本的方法。 常规js方法...

    用户1105954
  • 测试一下StringBuffer和StringBuilder及字面常量拼接三种字符串的效率

    之前一篇里写过字符串常用类的三种方式《java中的字符串相关知识整理》,只不过这个只是分析并不知道他们之间会有多大的区别,或者所谓的StringBuffer能提...

    用户1105954
  • JDK1.8HashMap源码分析

    HashMap和Hashtable的主要区别是: 1. Hashtable是线程安全,而HashMap则非线程安全,Hashtable的实现方法里面大部分都添...

    小小明童鞋
  • 浅析几种线程安全模型

    多线程编程一直是老生常谈的问题,在Java中,随着JDK的逐渐发展,JDK提供给我们的并发模型也越来越多,本文摘取三例使用不同原理的模型,分析其大致原理。

    Java团长
  • 谈谈Java中常见的线程安全模型

    多线程编程一直是老生常谈的问题,在Java中,随着JDK的逐渐发展,JDK提供给我们的并发模型也越来越多,本文摘取三例使用不同原理的模型,分析其大致原理。

    黄泽杰
  • 【必看】技术&案例 | V**路由转发表原理与大型MPLS案例分析

    VPN路由转发表(VPN Routingand Forwarding table ),简称VRF,VRF主要是为了解决本地路由冲突问题。PE和CE之间的...

    网络技术联盟站
  • ConcurrentHashMap#Put

    其余分支我们后面可以细讲,现在简略讲下分支2,它使用cas无锁模式将元素添加到空桶,代码如下:

    java达人
  • ConcurrentHashMap详解

    参考: http://www.cnblogs.com/everSeeker/p/5601861.html http://blog.csdn.net/fj...

    提莫队长
  • Python学习笔记(第六章)

    函数是什么,随着学习的深入,编写的代码越来越复杂,所以要找到一个方法去吧,重复性的操作变得更加简单高效起来,把一些重复性的的代码块封装成BIF,方便反复调用,减...

    天钧

扫码关注云+社区

领取腾讯云代金券