多用多学之Java中的Set,List,Map详解_java

很长时间以来一直代码中用的比较多的数据列表主要是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的特性来实现排重。确实简单而且有效。

以上就是小编为大家带来的多用多学之Java中的Set,List,Map详解全部内容了,希望大家多多支持~

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索java
, map
, list
set
java list map set、java中list set map、list set map区别、list map set的区别、list map set,以便于您获取更多的相关知识。

时间: 2016-06-28
Tags: list, java, Map, set

多用多学之Java中的Set,List,Map详解_java的相关文章

关于java中构造函数的一些知识详解_java

java的构造函数是一个非常重要的作用,首先java里的构造函数是可以重载的,而且因为也是可以继承在父类的构造函数,所以在子类里,首先必然是调用父类的构造函数.可以看下面的两个例子来对比: public class Test { public static void main(String args[]) { B b = new B(100); } } class A { public A() { System.out.println("A without any parameter"

java中set接口使用方法详解_java

java中的set接口有如下的特点: 不允许出现重复元素: 集合中的元素位置无顺序: 有且只有一个值为null的元素. 因为java中的set接口模仿了数学上的set抽象,所以,对应的数学上set的特性为: 互异性:一个集合中,任何两个元素都认为是不相同的,即每个元素只能出现一次.无序性:一个集合中,每个元素的地位都是相同的,元素之间是无序的.集合上可以定义序关系,定义了序关系后,元素之间就可以按照序关系排序.但就集合本身的特性而言,元素之间没有必然的序.空集的性质:空集是一切集合的子集    

Java中对象序列化与反序列化详解_java

本文实例讲述了Java中对象序列化与反序列化.分享给大家供大家参考.具体如下: 一.简介 对象序列化(Serializable)是指将对象转换为字节序列的过程,而反序列化则是根据字节序列恢复对象的过程. 序列化一般用于以下场景: 1.永久性保存对象,保存对象的字节序列到本地文件中: 2.通过序列化对象在网络中传递对象: 3.通过序列化在进程间传递对象. 对象所属的类必须实现Serializable或是Externalizable接口才能被序列化.对实现了Serializable接口的类,其序列化

java中queue接口的使用详解_java

Queue接口与List.Set同一级别,都是继承了Collection接口.LinkedList实现了Queue接口.Queue接口窄化了对LinkedList的方法的访问权限(即在方法中的参数类型如果是Queue时,就完全只能访问Queue接口所定义的方法 了,而不能直接访问 LinkedList的非Queue的方法),以使得只有恰当的方法才可以使用.BlockingQueue 继承了Queue接口.  队列是一种数据结构.它有两个基本操作:在队列尾部加人一个元素,和从队列头部移除一个元素就

Java中的迭代和递归详解_java

前言 最近在看书的时候看到这一内容,感觉还是蛮有收获的.迭代使用的是循环(for,while,do...wile)或者迭代器,当循环条件不满足时退出.而递归,一般是函数递归,可以是自身调用自身,也可以是非直接调用,即方法A调用方法B,而方法B反过来调用方法A,递归退出的条件为if,else语句,当条件符合基的时候退出. 上面是迭代和递归的语法特性,他们在Java中有什么不同呢?下面通过这篇文章来详细了解了解. 一.递归 提到迭代,不得不提一个数学表达式: n!=n*(n-1)*(n-2)*...

Java 中的字符串常量池详解_java

Java中的字符串常量池 Java中字符串对象创建有两种形式,一种为字面量形式,如String str = "droid";,另一种就是使用new这种标准的构造对象的方法,如String str = new String("droid");,这两种方式我们在代码编写时都经常使用,尤其是字面量的方式.然而这两种实现其实存在着一些性能和内存占用的差别.这一切都是源于JVM为了减少字符串对象的重复创建,其维护了一个特殊的内存,这段内存被成为字符串常量池或者字符串字面量池.

java中List集合及其遍历详解_java

1. 首先List<E>集合继承与Collection<E>,是一个接口.    ①  Collection (集合框架是JDK1.2版本出现的)    ②   list:是有序的,元素可以重复,以为该集合体系有索引.      经常用到的是实现该接口的ArrayList和LinkedList类    ③   Arraylist:  底层的数据结构使用的是数组结构,   特点: 查询速度很快,但是增删稍慢.线程不同步          LinkedList: 底层使用的是链表数据结

Java中对XML的解析详解_java

先简单说下前三种方式: DOM方式:个人理解类似.net的XmlDocument,解析的时候效率不高,占用内存,不适合大XML的解析: SAX方式:基于事件的解析,当解析到xml的某个部分的时候,会触发特定事件,可以在自定义的解析类中定义当事件触发时要做得事情:个人感觉一种很另类的方式,不知道.Net体系下是否有没有类似的方式? StAX方式:个人理解类似.net的XmlReader方式,效率高,占用内存少,适用大XML的解析: 不过SAX方式之前也用过,本文主要介绍JAXB,这里只贴下主要代码

浅谈java中静态方法的重写问题详解_java

首先来看看以下程序将会打印出什么: 复制代码 代码如下: class Dog {    public static void bark() {        System.out.print("woof ");    }} class Basenji extends Dog {    public static void bark() { }} public class Bark {    public static void main(String args[]) {