多用多学之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的特性来实现排重。确实简单而且有效。

以上就是小编为大家带来的多用多学之java中的set,list,map详解全部内容了，希望大家多多支持~