文档章节

Java容器类(List、Map、Set)

o
 osc_x4h57ch8
发布于 2018/04/26 11:18
字数 2411
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

java容器类的基本类型包括List、Set和Map。它们可以自动调节自身的尺寸,因此和数组不同,在编程时可以将任意数量的对象放置到容器中,并且不需要担心容器应该设置为多大。本文源码的JDK版本为"1.8.0_131"

一、List

有两种类型的list:ArrayList和LinkedList。它们之间区别如下:

  1、ArrayList是基于数组实现的,LinkedList是基于链表实现的。

  2、对于随机访问get和set,ArrayList有速度优势,LinkedList需要遍历访问。

  3、对于新增和删除操作add和remove,LinkedList有优势,因为ArrayList有可能要大量移动数据。

 具体来说,ArrayList的主要实现源码为:

1 private static final int DEFAULT_CAPACITY = 10; //Default initial capacity
2 transient Object[] elementData; //The array buffer into which the elements of the ArrayList are stored.
3 private int size; //The size of the ArrayList (the number of elements it contains).
//如果ArrayList初始化时不指定大小,那么它的默认大小为10

主要实现方法有:

 1 //Returns the number of elements in this list.
 2 public int size() {
 3         return size;
 4     }
 5 
 6 public boolean isEmpty() {
 7         return size == 0;
 8     }
 9 
10 //get 根据数组下标直接访问
11  public E get(int index) {
12         rangeCheck(index);
13         return elementData(index);
14     }
15 E elementData(int index) {
16         return (E) elementData[index];
17     }
18 
19 //set 根据数组下表直接访问并修改
20 public E set(int index, E element) {
21         rangeCheck(index);
22 
23         E oldValue = elementData(index);
24         elementData[index] = element;
25         return oldValue;
26     }
27 
28 //add 会先检查需不需要扩容,若需要,先扩容,在插入到数组最后一位
29  public boolean add(E e) {
30         ensureCapacityInternal(size + 1);  // Increments modCount!!
31         elementData[size++] = e;
32         return true;
33     }
34 //ensureCapacityInternal这个函数最后会传到grow函数里面去
35 //显然,在ArrayList中,每次扩容的幅度是原来大小的一半
36 private void grow(int minCapacity) {
37         // overflow-conscious code
38         int oldCapacity = elementData.length;
39         int newCapacity = oldCapacity + (oldCapacity >> 1);
40         if (newCapacity - minCapacity < 0)
41             newCapacity = minCapacity;
42         if (newCapacity - MAX_ARRAY_SIZE > 0)
43             newCapacity = hugeCapacity(minCapacity);
44         // minCapacity is usually close to size, so this is a win:
45         elementData = Arrays.copyOf(elementData, newCapacity);
46     }
47 
48 //remove的操作
49 //如果ArrayList想要移除指定位置的数据,则需要将这个数据之后的所有数据往前移一位,在删除掉最后一个数据
50 public E remove(int index) {
51         rangeCheck(index);
52 
53         modCount++;
54         E oldValue = elementData(index);
55 
56         int numMoved = size - index - 1;
57         if (numMoved > 0)
58             System.arraycopy(elementData, index+1, elementData, index,
59                              numMoved);
60         elementData[--size] = null; // clear to let GC do its work
61 
62         return oldValue;
63     }

LinkedList的主要实现源码为:

 1  transient int size = 0;
 2 
 3     /**
 4      * Pointer to first node.
 5      * Invariant: (first == null && last == null) ||
 6      *            (first.prev == null && first.item != null)
 7      */
 8     transient Node<E> first;
 9 
10     /**
11      * Pointer to last node.
12      * Invariant: (first == null && last == null) ||
13      *            (last.next == null && last.item != null)
14      */
15     transient Node<E> last;
16 
17     // Constructs an empty list.
18     public LinkedList() {
19     }
21
22      /* Constructs a list containing the elements of the specified
23      * collection, in the order they are returned by the collection's
24      * iterator.28      */
29     public LinkedList(Collection<? extends E> c) {
30         this();
31         addAll(c);
32     }

其中LinkedList中的每个结点的数据结构为:

 1 private static class Node<E> {
 2 E item;
 3 Node<E> next;
 4 Node<E> prev;
 5 
 6 Node(Node<E> prev, E element, Node<E> next) {
 7   this.item = element;
 8   this.next = next;
 9   this.prev = prev;
10 }
11 }

 

主要实现方法有:

 1 //判断是否包含某个数据,需要从头到位的遍历,效率不如基于数组的ArrayList
 2 public boolean contains(Object o) {
 3         return indexOf(o) != -1;
 4     }
 5 public int indexOf(Object o) {
 6         int index = 0;
 7         if (o == null) {
 8             for (Node<E> x = first; x != null; x = x.next) {
 9                 if (x.item == null)
10                     return index;
11                 index++;
12             }
13         } else {
14             for (Node<E> x = first; x != null; x = x.next) {
15                 if (o.equals(x.item))
16                     return index;
17                 index++;
18             }
19         }
20         return -1;
21     }
22 
23 //若要在LinkedList中add一个数据,则只需在链表末尾添加即可,不用考虑扩容操作,因此效率可能会较高
24 public boolean add(E e) {
25         linkLast(e);
26         return true;
27     }
28 void linkLast(E e) {
29         final Node<E> l = last;
30         final Node<E> newNode = new Node<>(l, e, null);
31         last = newNode;
32         if (l == null)
33             first = newNode;
34         else
35             l.next = newNode;
36         size++;
37         modCount++;
38     }

LinkedList中无论是get()方法还是set()方法,都是基于遍历的,因此效率较低:

 1 public E get(int index) {
 2         checkElementIndex(index);
 3         return node(index).item;
 4     }
 5 
 6 public E set(int index, E element) {
 7         checkElementIndex(index);
 8         Node<E> x = node(index);
 9         E oldVal = x.item;
10         x.item = element;
11         return oldVal;
12     }
13 
14 Node<E> node(int index) {
15         // assert isElementIndex(index);
16 
17         if (index < (size >> 1)) {
18             Node<E> x = first;
19             for (int i = 0; i < index; i++)
20                 x = x.next;
21             return x;
22         } else {
23             Node<E> x = last;
24             for (int i = size - 1; i > index; i--)
25                 x = x.prev;
26             return x;
27         }
28     }

总结,当进行添加删除操作时,由于不需要扩容和整体移动的操作,因此LinkedList效率比ArrayList高。而在进行查询和修改操作时,由于数组可以直接利用下标进行定位,因此ArrayList效率比LinkedList高。

二、Map

Map可以将一个对象映射到另一个对象上。注意,Map本身只是一个抽象的接口,因此不能直接实例化一个Map对象。hashmap本身是一个用拉链法实现的哈希表,这个表的结构如下图所示:

 

HashMap的主要实现代码为:

 1 //哈希表中的存储数组
 2 transient Node<K,V>[] table;
 3 
 4 //哈希表中的存储节点 
 5  static class Node<K,V> implements Map.Entry<K,V> {
 6         final int hash;
 7         final K key;
 8         V value;
 9         Node<K,V> next;
10 
11         Node(int hash, K key, V value, Node<K,V> next) {
12             this.hash = hash;
13             this.key = key;
14             this.value = value;
15             this.next = next;
16         }
17 
18         public final K getKey()        { return key; }
19         public final V getValue()      { return value; }
20         public final String toString() { return key + "=" + value; }
21 
22         public final int hashCode() {
23             return Objects.hashCode(key) ^ Objects.hashCode(value);
24         }
25 
26         public final V setValue(V newValue) {
27             V oldValue = value;
28             value = newValue;
29             return oldValue;
30         }
31 
32         public final boolean equals(Object o) {
33             if (o == this)
34                 return true;
35             if (o instanceof Map.Entry) {
36                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
37                 if (Objects.equals(key, e.getKey()) &&
38                     Objects.equals(value, e.getValue()))
39                     return true;
40             }
41             return false;
42         }
43     }

HashMap的主要实现的方法有:

 1 //HashMap中get()方法的过程就是先根据key的hash值寻找数据存储在数组的哪个位置,一个一个遍历直至找到数据或者返回null
 2 public V get(Object key) {
 3         Node<K,V> e;
 4         return (e = getNode(hash(key), key)) == null ? null : e.value;
 5     }
 6 
 7  final Node<K,V> getNode(int hash, Object key) {
 8         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 9         if ((tab = table) != null && (n = tab.length) > 0 &&
10             (first = tab[(n - 1) & hash]) != null) {
11             if (first.hash == hash && // always check first node
12                 ((k = first.key) == key || (key != null && key.equals(k))))
13                 return first;
14             if ((e = first.next) != null) {
15                 if (first instanceof TreeNode)
16                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
17                 do {
18                     if (e.hash == hash &&
19                         ((k = e.key) == key || (key != null && key.equals(k))))
20                         return e;
21                 } while ((e = e.next) != null);
22             }
23         }
24         return null;
25     }
26 
27 //remove的过程
28 public V remove(Object key) {
29         Node<K,V> e;
30         return (e = removeNode(hash(key), key, null, false, true)) == null ?
31             null : e.value;
32     }
33 
34  final Node<K,V> removeNode(int hash, Object key, Object value,
35                                boolean matchValue, boolean movable) {
36         Node<K,V>[] tab; Node<K,V> p; int n, index;
37         if ((tab = table) != null && (n = tab.length) > 0 &&
38             (p = tab[index = (n - 1) & hash]) != null) {
39             Node<K,V> node = null, e; K k; V v;
40             if (p.hash == hash &&
41                 ((k = p.key) == key || (key != null && key.equals(k))))
42                 node = p;
43             else if ((e = p.next) != null) {
44                 if (p instanceof TreeNode)
45                     node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
46                 else {
47                     do {
48                         if (e.hash == hash &&
49                             ((k = e.key) == key ||
50                              (key != null && key.equals(k)))) {
51                             node = e;
52                             break;
53                         }
54                         p = e;
55                     } while ((e = e.next) != null);
56                 }
57             }
58             if (node != null && (!matchValue || (v = node.value) == value ||
59                                  (value != null && value.equals(v)))) {
60                 if (node instanceof TreeNode)
61                     ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
62                 else if (node == p)
63                     tab[index] = node.next;
64                 else
65                     p.next = node.next;
66                 ++modCount;
67                 --size;
68                 afterNodeRemoval(node);
69                 return node;
70             }
71         }
72         return null;
73     }

HashMap的put()方法:

 1 //HashMap的put()方法不能插入重复的元素,若重复,则替换
 2 public V put(K key, V value) {
 3         return putVal(hash(key), key, value, false, true);
 4     }
 5 
 6 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 7                    boolean evict) {
 8         Node<K,V>[] tab; Node<K,V> p; int n, i;
 9         if ((tab = table) == null || (n = tab.length) == 0)
10             n = (tab = resize()).length;
11         if ((p = tab[i = (n - 1) & hash]) == null)
12             tab[i] = newNode(hash, key, value, null);
13         else {
14             Node<K,V> e; K k;
15             if (p.hash == hash &&
16                 ((k = p.key) == key || (key != null && key.equals(k))))
17                 e = p;
18             else if (p instanceof TreeNode)
19                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
20             else {
21                 for (int binCount = 0; ; ++binCount) {
22                     if ((e = p.next) == null) {
23                         p.next = newNode(hash, key, value, null);
24                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
25                             treeifyBin(tab, hash);
26                         break;
27                     }
28                     if (e.hash == hash &&
29                         ((k = e.key) == key || (key != null && key.equals(k))))
30                         break;
31                     p = e;
32                 }
33             }
34             if (e != null) { // existing mapping for key
35                 V oldValue = e.value;
36                 if (!onlyIfAbsent || oldValue == null)
37                     e.value = value;
38                 afterNodeAccess(e);
39                 return oldValue;
40             }
41         }
42         ++modCount;
43         if (++size > threshold)
44             resize();
45         afterNodeInsertion(evict);
46         return null;
47     }

三、Set

 Set类不保存重复的元素,如果你试图将相同对象的多个实例添加到Set中,那么它就会组织这种重复现象。注意,Set本身只是一个抽象的接口,因此不能直接实例化一个Set对象。另外,hashset对查找方面进行了优化操作。

HashSet的主要实现源码有:

//可以看到HashSet的底层是由HashMap实现的
1
private transient HashMap<E,Object> map; 2 3 public HashSet() { 4 map = new HashMap<>(); 5 } 6 7 public HashSet(int initialCapacity) { 8 map = new HashMap<>(initialCapacity); 9 }

HashSet的主要方法有:

 1 public Iterator<E> iterator() {
 2         return map.keySet().iterator();
 3     }
 4 
 5 public int size() {
 6         return map.size();
 7     }
 8 
 9 public boolean isEmpty() {
10         return map.isEmpty();
11     }
12 
13 public boolean contains(Object o) {
14         return map.containsKey(o);
15     }
16 
17  public boolean add(E e) {
18         return map.put(e, PRESENT)==null;
19     }
20 
21 /**
22 * Dummy value to associate with an Object in the backing Map
23 * private static final Object PRESENT = new Object();
24 */
24
25 25 public boolean remove(Object o) { 26 return map.remove(o)==PRESENT; 27 }

 由于HashSet的底层是基于HashMap的,所以它的查询效率很高。另外如果给add()方法传入的是已经存在的重复值,那么在底层给HashMap也是传入重复的键值对,那么就会将原来相同的键值对覆盖,在上层看来就和没有插入一样的。

下一篇: 第四章
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

es集群笔记

es 集群的默认配置是当集群中的某个节点磁盘达到使用率为 85% 的时候, 就不会在该节点进行创建副本, 当磁盘使用率达到 90% 的时候, 尝试将该节点的副本重分配到其他节点. 当磁盘使用率达到 ...

gaolongquan
10分钟前
4
0
VS Code编写Vue过程中出现空格不规范报错的问题

报错内容: 解决办法: 1.注释或删除这些代码 注释掉之后(重启vue服务),再进行编写的时候,空格不规范的情况下就不会再报错了。 2.如果没在webpack.dev.conf.js文件中找到注释代码就在webpack...

安然_oschina
13分钟前
9
0
域名防封_域名防红_微信域名防拦截

最近微信开始大封杀,不知道原因是什么,可能是因为违规网站太多了吧,很多网站都被错杀了,下面我们聊一下怎样才能避免域名被封杀呢。 在各种不同的域名当中,能够做出了更适合的选择,这些...

戚馨逸
17分钟前
13
0
数据结构(六)——循环链表

一、循序链表简介 1、循环链表的定义 循环链表的任意元素都有一个前驱和一个后继,所有数据元素在关系上构成逻辑上的环。 循环链表是一种特殊的单链表,尾结点的指针指向首结点的地址。 循环...

rainbowcode
20分钟前
13
0
六边形寻路格子绘制

using System.Collections;using System.Collections.Generic;using UnityEngine;public class AdventureIsland : MonoBehaviour{ static AdventureIsland instante; pu......

江湖令
21分钟前
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部