集合

2017/01/07 Java

常见数据结构

名称 特点
先进后出
队列 先进先出
数组 查询快,增删慢
链表 查询慢,增删快

数据结构之数组和链表

数据结构之数组和链表

数据结构之栈和队列

数据结构之栈和队列

集合

集合类的关系

集合类的关系

集合类的特点

集合只用于存储对象,集合长度是可变的,集合可以存储不同类型的对象。

集合和数组的区别

  • 长度区别
    • 数组固定
    • 集合可变
  • 内容区别
    • 数组可以是基本类型,也可以是引用类型
    • 集合只能是引用类型
  • 元素内容
    • 数组只能存储同一种类型
    • 集合可以存储不同类型(其实集合一般存储的也是同一种类型)

Collection

List

有序的 collection(也称为序列)。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引(在列表中的位置)访问元素,并搜索列表中的元素。
与 set 不同,列表通常允许重复的元素。

  • ArrayList
    • 底层数据结构是数组,查询快,增删慢
    • 线程不安全,效率高
  • Vector
    • 底层数据结构是数组,查询快,增删慢
    • 线程安全,效率低
  • LinkedList
    • 底层数据结构是链表,查询慢,增删快
    • 线程不安全,效率高

Set

一个不包含重复元素的 collection。
特点:无序,唯一

  • HashSet
    • 不保证 set 的迭代顺序,特别是它不保证该顺序恒久不变。
  • LinkedHashSet
    • 元素有序唯一
      • 由链表保证元素有序
      • 由哈希表保证元素唯一
  • TreeSet
    • 使用元素的自然顺序对元素进行排序,或者根据创建 set 时提供的 Comparator 进行排序,具体取决于使用的构造方法。

HashSet如何保证元素唯一性

  • 底层数据结构是哈希表(元素是链表的数组)
  • 哈希表依赖于哈希值存储,添加功能底层依赖两个方法:
    • int hashCode()
    • boolean equals(Object obj)

HashSet存储元素保证唯一性的代码及图解

LinkedHashSet

  • 底层数据结构是链表和哈希表
    • 由链表保证元素有序
    • 由哈希表保证元素唯一

TreeSet如何保证元素的排序和唯一性

底层数据结构是红黑树(红黑树是一种自平衡的二叉树)

如何保证元素排序的呢?

  • 自然排序(元素具备比较性)
    • 让元素所属的类实现Comparable接口
  • 比较器排序(集合具备比较性)
    • 让集合构造方法接收Comparator的实现类对象

如何保证元素唯一性的呢?

根据比较的返回值是否是0来决定

TreeSet存储元素自然排序和唯一的图解

Map

  • 将键映射到值的对象
  • 一个映射不能包含重复的键
  • 每个键最多只能映射到一个值

HashMap

键是哈希表结构,可以保证键的唯一性

LinkedHashMap

接口的哈希表和链接列表实现,具有可预知的迭代顺序。

TreeMap

键是红黑树结构,可以保证键的排序和唯一性

HashMap和Hashtable的区别

  • Hashtable线程安全,效率低。不允许null键和null值
  • HashMap线程不安全,效率高。允许null键和null值

Collection和Map比较

Map接口和Collection接口的不同

  • Map是双列的,Collection是单列的
  • Map的键唯一,Collection的子体系Set是唯一的
  • Map集合的数据结构值针对键有效,跟值无关;Collection集合的数据结构是针对元素有效

List,Set,Map等接口是否都继承子Map接口

List,Set不是继承自Map接口,它们继承自Collection接口
Map接口本身就是一个顶层接口

Contains方法与equals()、hashcode()、compareTo()

List依赖存储对象的equals()方法

if (o == null) {
    for (int i = 0; i < size; i++)
	if (elementData[i]==null)
	    return i;
} else {
    for (int i = 0; i < size; i++)
	if (o.equals(elementData[i]))//判断equals
	    return i;
}
return -1;

HashMap和HashSet依赖存储对象的equals()方法和hashcode()方法

int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
     e != null;
     e = e.next) {
    Object k;
    if (e.hash == hash &&//首先比较hash
        ((k = e.key) == key || (key != null && key.equals(k))))//然后判断equals
        return e;
}
return null;

TreeMap和TreeSet依赖compareTo方法

// Offload comparator-based version for sake of performance
if (comparator != null)
    return getEntryUsingComparator(key);
if (key == null)
    throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
    int cmp = k.compareTo(p.key);
    if (cmp < 0)
        p = p.left;
    else if (cmp > 0)
        p = p.right;
    else
        return p;
}
return null;

迭代器

为什么定义为了一个接口而不是实现类

迭代器使用图解和原理图解

ConcurrentModificationException(并发修改异常)

出现的现象

当方法检测到对象的并发修改,但不允许这种修改时,抛出此异常。 (迭代器遍历集合,集合修改集合元素)

原因

迭代器是依赖于集合而存在的,在判断成功后,集合的中新添加了元素,而迭代器却不知道,所以就报错了,这个错叫并发修改异常。
其实这个问题描述的是:迭代器遍历元素的时候,通过集合是不能修改元素的。

解决方案

  • 迭代器遍历,迭代器修改(ListIterator)
    • 元素添加在刚才迭代的位置
  • 集合遍历,集合修改(size()和get())
    • 元素添加在集合的末尾
List list = new ArrayList();
// 添加元素
list.add("hello");
list.add("world");
list.add("java");

// 迭代器遍历
Iterator it = list.iterator();
while (it.hasNext()) {
	String s = (String) it.next();
	if ("world".equals(s)) {
		list.add("javaee");//ConcurrentModificationException
	}
}

// 方式1:迭代器迭代元素,迭代器修改元素
// 而Iterator迭代器却没有添加功能,所以我们使用其子接口ListIterator
ListIterator lit = list.listIterator();
while (lit.hasNext()) {
	String s = (String) lit.next();
	if ("world".equals(s)) {
		lit.add("javaee");//ListIterator特有方法
	}
}

// 方式2:集合遍历元素,集合修改元素(普通for)
for (int x = 0; x < list.size(); x++) {
	String s = (String) list.get(x);
	if ("world".equals(s)) {
		list.add("javaee");
	}
}

Collections

Collection和Collections的区别

  • Collection 是单列集合的顶层接口,有两个子接口List和Set
  • Collections 是针对集合进行操作的工具类,可以对集合进行排序和查找等

排序

Collections排序需要Comparator或者排序对象实现了Comparable接口

获取线程安全的集合

一般不会使用Vector等集合,使用Collections工具类的synchronizedList()、synchronizedMap()等方法即可获得县城安全的List、Map等集合

JDK1.5有提供线程安全的集合

java.util.concurrent包下的介绍可以知道有哪些并发集合

  • ConcurrentHashMap
  • CopyOnWriteArrayList
  • CopyOnWriteArraySet

以上概念总结于传智播客Java基础课程

Search

    Post Directory