Java数据结构--List、Set和Map

一、概述

?数组

????????数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

链表

????????链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，为O(N);链表的特点是：寻址困难，插入和删除容易。

哈希表

????????既满足了数据的查找方便，也不占用太多的内容空间，使用十分方便

Android中常用的数据结构包括List、Set和Map这三大类的集合；

其中List和Set属于Collection，List可以存放重复的数据，Set不可以，Map是key-value键值对。

集合的关系类图：

二、List

特点：

????????元素有序，且可重复

扩容：

• 初始容量10，负载因子0.5，扩容增量0.5倍
• 新容量 = 原容量 + 原容量 * 0.5。如 ArrayList的容量为10，一次扩容后是容量为15

实现：

ArrayList

特点：

• ?????内部基于数组实现
• 支持动态扩容，超出容量自动扩容
• 根据索引随机访问快，随机插入和删除慢
• 线程不安全

?初始化和赋值：

//方式一：
  ArrayList<String> list = new ArrayList<String>();
  String str1 = String("test1");
  String str2 = String("test2");
  list.add(str1);
  list.add(str2);

//方式二：
  ArrayList<String> list = new ArrayList<String>() {{
      add("test1");
      add("test2");
  }};
    

3.遍历：

        //for循环方式
        for (String str : list) {

        }

        //迭代器方式
        Iterator<String> iter = list.iterator();
        while (iter.hasNext()) {
            String next = iter.next();
        }

4.常见问题：在遍历的过程中删除Item元素

? ? ? ?如果采用for循环的方式去删除元素，会出现删除的元素并没有完全被删除，或者出现ConcurrentModificationException异常

? ? ? ? 解决方案：使用遍历器iterator进行遍历删除

Linked List

特点：

• 以双向链表实现，链表无容量限制，一个元素中保存了上一个元素和下一个元素的的索引
• 允许元素为null
• 线程不安全
• 元素随机的增删快，只需要调整节点指向即可；随机查找可能会慢，从链头开始寻找，找下一个的引用

使用场景：

????????可用作堆栈（stack）、队列（queue）或双向队列（deque）

Vector

特点：

• 底层由数组实现，主要实现和ArrayList差不多
• 内部使用了synchronized关键字，实现了线程安全访问但性能有些降低，
• 线程安全，性能低

CopyOnWriteArrayList

特点：

• 写时复制
• 线程安全
• 适合于读多，写少的场景
• 写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array
• 比Vector性能高
• 实现了List接口，使用方式与ArrayList类似

三、Set

特点：

????元素无序，且不可重复

扩容：

????初始容量16，负载因子0.75，扩容增量1倍

实现：

HashSet

特点：

• 不保持插入顺序
• 没有重复对象
• 通过Map实现的，只用到了键，没有用到值。因为Map是通过键值对的形式存在的 ，键不能重复而值可以重复
• 按照哈希算法来存取集合中的对象
• 非线程安全

使用场景：

????????用HashSet对List中相同的元素进行去重

    private static <T> List<T> removeSame(List<T> list) {
        Set<T> set = new HashSet<>();
        set.addAll(list);
        List<T> listSingle = new ArrayList<>();
        for (T s : set) {
            listSingle.add(s);
        }
        return listSingle;
    }

TreeSet

特点：

• 是一个包含有序的且没有重复元素的集合
• 作用是提供有序的Set集合，自然排序或者根据提供的Comparator进行排序
• TreeSet是基于TreeMap实现的

四、Map

特点：

• 无序，键值对，键不能重复，值可以重复
• 键重复则覆盖，没有继承Collection接口

扩容：

????????初始容量16，负载因子0.75，扩容增量1倍

遍历：

• 先获取所有键的Set集合，再遍历（通过键获取值）
• 取出保存所有Entry的Set,再遍历此Set即可

实现：

HashMap

• 线程不安全，最常用，速度快
• 内部采用数组来存放数据
• 可以接受为null的键值(key)和值(value)

?HashTable

• 线程安全，使用synchronized来保证线程安全，性能差
• 不可以接受为null的键值(key)和值(value)

ConcurrentHashMap

• 线程安全，比HashTable性能高、扩展性好，Java 5出来的，用来替代HashTable的
• 内部采用数组+链表+红黑树实现

TreeMap

• 内部采用红黑树实现，用于保证key值的顺序，添加或获取元素时性能较HashMap慢
• key值按一定的顺序排序

LinkedHashMap

• 继承HashMap
• LinkedHashMap是有序的，且默认为插入顺序

五、总结

List：有序、可重复。

Set：无序、不可重复的集合。重复元素会覆盖掉。

Map：存储的是键值对，键不能重复，值可以重复。