ArrayList,LinkedLIst,HashMap

一、概述

ArrayList:数组集合。与数组不同,数组一旦创建,长度固定,但是ArrayList的长度是动态的,不受限制,可以存储任意多的对象,但是只能存储对象。

     查询、修改、新增(新增的位置在尾部)快,删除、新增(新怎的位置在中间)慢。适用于查询、修改较多的场景。

LinkedList:双向链表集合。元素有序且可以重复。

     查询、修改(需要遍历集合),新增‘删除(只需要修改前后节点的链接)快,适用于新增、删除较多的场景。

HashMap:结合数组和链表的优势,期望做到增删改查都快速,时间复杂度接近于O(1)。当哈希算法较好时,Hash冲突较低。适用于增删改查所有场景。

二、分述

ArrayList

  • ArrayList底层实现是基于数组的,因此对指定下表的查找和修改比较快,但是删除和插入的操作比较慢。
  • 继承自AbstractList,实现了List接口。
  • 允许 null 的存在,同时还实现了 RandomAccess、Cloneable、Serializable 接口,所以ArrayList 是支持快速访问、复制、序列化的。
  • 构造ArrayList时尽量指定容量,减少扩容时带来的数组赋值操作,如果不知道大小可以赋值其默认容量。
  • 每次添加元素之前都会检查是否需要扩容,每次扩容都是增加到原有容量的一般。(扩容时创建一个新的数组,并将原来的数组元素迁移到新数组中)
  • ArrayList的所有方法第一没有进行同步,因此它不是线程安全的。

ArrayList,LinkedLIst,HashMap

贴一个简单的案例:

 1 import java.util.ArrayList;
 2 public class TestArrayList {
 3     public static void main(String[] args) {
 4         // Create a list to store cities
 5         ArrayList<String> cityList = new ArrayList<String>();
 6         
 7         // Add some cities in the list
 8         cityList.add("London");
 9         // cityList now contains [London]
10         
11         cityList.add("Denver");
12         // cityList now contains [London, Denver]
13         
14         cityList.add("Paris");
15         // cityList now contains [London, Denver, Paris]
16         
17         cityList.add("Miami");
18         // cityList now contains [London, Denver, Paris, Miami]
19         
20         cityList.add("Seoul");
21         // Contains [London, Denver, Paris, Miami, Seoul]
22         
23         cityList.add("Tokyo");
24         // Contains [London, Denver, Paris, Miami, Seoul, Tokyo]
25 
26         System.out.println("List size? " + cityList.size());  // 6
27         System.out.println("Is Miami in the list? " + cityList.contains("Miami"));  // true
28         System.out.println("The location of Denver in the list? " + cityList.indexOf("Denver")); // 1 返回索引,如果不在list中,返回-1
29         System.out.println("Is the list empty? " + cityList.isEmpty()); // Print false
30 
31         // Insert a new city at index 2
32         cityList.add(2, "Xian");
33         // Contains [London, Denver, Xian, Paris, Miami, Seoul, Tokyo]
34 
35         // Remove a city from the list
36         cityList.remove("Miami");
37         // Contains [London, Denver, Xian, Paris, Seoul, Tokyo]
38 
39         // Remove a city at index 1
40         cityList.remove(1);
41         // Contains [London, Xian, Paris, Seoul, Tokyo]
42 
43         // Display the contents in the list
44         System.out.println(cityList.toString());
45 
46         // Display the contents in the list in reverse order
47         for (int i = cityList.size() - 1; i >= 0; i--)
48             System.out.print(cityList.get(i) + " ");
49         System.out.println();
50 
51         // Create a list to store two circles
52         ArrayList<CircleFromSimpleGeometricObject> list = new ArrayList<CircleFromSimpleGeometricObject>();
53 
54         // Add two circles
55         list.add(new CircleFromSimpleGeometricObject(2));
56         list.add(new CircleFromSimpleGeometricObject(3));
57 
58         // Display the area of the first circle in the list
59         System.out.println("The area of the circle? " + list.get(0).getArea());
60     }
61 }

 

LinkedList

  • LinkedList是基于双向链表实现的,不论是增删改查方法还是队列和栈的实现,都可通过操作节点实现。
  • LinkedList无需提前指定容量,因为基于链表操作,集合的容量随着元素的加入自动增加(无序执行默认长度,也没有扩容需求)
  • LinkedList删除元素后集合占用的内存自动缩小,无需像ArrayList一样调用trinToSize()方法
  • LinkedList的所有方法没有进行同步,因此它也不是线程安全的,应该避免在多线程环境下使用。
  • LinkedList根据index查询时采取的是二分法,即index小于总长度一半时从链表头开始往后查找,大于总长度一半时从链表尾往前查找。如果是根据元素查找,则需要从头开始遍历

LinkedList中的属性:

1 //链表的节点个数
2 transient int size = 0;
3 //指向头节点的指针
4 transient Node<E> first;
5 //指向尾节点的指针
6 transient Node<E> last;

Node节点结构

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

HashMap

  • 哈希表是由数组和单向链表共同构成的一种结构,上图中一个数组元素链表存在多个元素,说明存在hash冲突,理想情况下每个数组元素之应包含一个元素
  • 扩容原因:HashMap默认的初始容量为16,默认的加载因子是0.75。而threshold是集合能够存储的键值对的阀值,默认是初始容量*加载因子,也就是16*0.75=12,当键值对要超过阀值时,意味着这时候的哈希表已处于饱和状态,再继续添加元素就会增加哈希冲突,从而使HashMap的性能下降。
  • 每次扩容都是增加原有容量的一倍。(扩容是创建一个新的数组,并将原来的数组元素迁移到新数组中,根据hash值重新分配)
  • hash值的计算方式(字符串是单独的计算方式,扰动函数就是把所有东西杂糅到一起,提高随机性)
 1 //生成hash码的函数
 2 final int hash(Object k) {
 3   int h = hashSeed;
 4   //key是String类型的就使用另外的哈希算法
 5   if (0 != h && k instanceof String) {
 6       return sun.misc.Hashing.stringHash32((String) k);
 7   }
 8   h ^= k.hashCode();
 9   //扰动函数
10   h ^= (h >>> 20) ^ (h >>> 12);
11   return h ^ (h >>> 7) ^ (h >>> 4);
12 }

而还有与HashMap相似但又很容易混淆的HashTable和ConcurrentHasgMap在我的另一篇博客中有介绍到。

三、总结

  概述中已经描述各个集合的适用场景,这里重点说一下HashMap。HashMap可以通过hash值快速定位到数组下标,执行新增、修改、删除操作。当hash算法较好(hash冲突较少)时,增删改查的时间复杂度都是O(1)。但是如果链表较长,则会增加增删改查的时间复杂度O(链表长度)。原则就是尽量减少hash冲突,并预先估算hashmap长度,减少扩容操作。

上一篇:jQuery获取并设置 CSS 类


下一篇:SpringEl表达式