Java集合

发表 | 更新 | 分类 ， | 评论： | 热度：
本文字数： 5.4k | 阅读时长 ≈ 5 分钟

集合的简单笔记，首先了解Java的数组有一下几个特点：

  1. 只能存储同一种类型的元素。 除了Object类型的数组以外。
  2. 数组一旦初始化长度固定。
  3. 数组中元素与元素之间的内存地址是连续的。

因此很多方面数组是不够的，因此就需要集合。

集合体系

Collection单列集合

List

如果是实现了List接口的集合类具备的特点： 有序、 元素可重复

  • ArrayList ： ArrayList底层是维护了一个Object数组去实现的，特点：查询速度快，增删慢
  • LinkedList：底层是使用了链表数据结构实现的， 特点：查询速度慢，增删快
  • Vector： 底层也是使用一个Object数组去实现的，但是Vector线程安全，操作效率低

ArrayList的底层是使用了一个Object数组去实现的，往ArrayList存储数据的时候，数据实际上是存储到了Object数组中， 使用无参构造函数是，Object数组的初始化容量是10， 当容量不够使用时会自动自增原来的0.5倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

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);
}

Vector和ArrayList的区别：

相同点：
Vector和ArrayList的底层都是使用Object数组去实现的

不同点：

1. Vector是线程安全的，操作效率低，ArrayList是线程非安全的，操作效率高 
2. Vector是jdk1.0出现的，ArrayList是jdk1.2出现的

List接口下特有的方法：

  1. 增加
    add(int index, E element) 指定索引值添加元素
    addAll(int index, Collection c) 指定索引值把一个集合的元素添加到另外一个集合中
  2. 删除
    remove(int index) 制定索引值删除元素
  3. 修改
    set(int index, E element) 指定索引值修改元素
  4. 获取
    get(int index) 根据索引值获取元素
    indexOf(Object o) 查找指定元素第一次出现的索引值，如果不包含制定的元素则返回-1表示。
    lastIndexOf(Object o) 查找指定元素最后一次出现的索引值，如果不包含指定的元素则返回-1表示。
    subList(int fromIndex, int toIndex) 指定开始于结束的索引值截取集合中的元素，返回
  5. 迭代
    iterator() 获取集合中的迭代期，迭代期的作用就是用于抓取集合中的元素
    迭代器常用的方法
    • next() : 先获取当前游标指向的元素，然后游标向下移动一个单位）
    • hasNext() : 有没有元素可遍历
    • remove() ： 移出迭代器最后一次返回的元素
      listIterator()
      迭代特有的方法：
    • hasPrevious() : 问是否有上一个元素
    • previous() : 游标先向上移动一个单位，然后获取当前游标指向的元素
    • add(E e) : 把元素添加到当前游标指向的位置上
    • set(E e) ： 使用指定的元素代替迭代期最后一次返回的元素

List接口特有的方法都是操作索引值的。

迭代器在迭代的过程中要注意的事项：

  1. 迭代器在迭代的过程中不准使用集合对象改变集合的元素个数。 否则会报出：ConcurrentModificationException
  2. 在迭代过程中如果需要改变集合中的元素个数，只能使用迭代器的方法去改变。

LinkedList特有的方法：

  1. 方法介绍
    • addFirst(E e) 把元素添加到集合的首位置
    • addLast(E e) 把元素添加到集合的末尾处
    • getFirst() 获取集合的首位置元素
    • getLast() 获取集合的末尾元素
    • removeFirst() 删除集合的首元素
    • removeLast() 删除集合的末尾元素
  2. 数据结构
    1. 栈：先进后出
      push();
      pop();
    2. 队列：先进先出
      offer()
      poll()
  3. 返回逆序的迭代器对象
    descendingIterator()

Set

如果实现了Set接口的集合类具备的特点： 无序、元素不可重复

  • HashSet 底层是使用了哈西表支持的，特点：存取的速度快。
  • TreeSet 底层使用了红黑树(二叉树)数据结构实现的，特点：可以对元素进行排序存储

HashSet存储原理：

往HashSet存储元素的时候，首先HashSet会先调用元素的hashCode方法，得到元素的哈希码值，然后通过哈希码就额可以算出该元素在哈希表中的存储位置

情况1： 如果根据元素的哈希码值算出的位置目前没有任何匀速存储，那么该元素可以直接存储到哈希表中

情况2： 根据元素的哈希码算出的位置目前如果已经存在了其他元素，那么会调用该元素的equals方法与这个位置的元素再比较一次，如果
equals方法返回的是true，那么该元素则被视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素也可以运行被添加

TreeSet 要注意的事项：

  1. 如果往TreeSet添加元素的时候，如果元素本身具备自然顺序的特性，那么treeset就会按照元素自然顺序进行排序存储
  2. 如果往TreeSet添加元素的时候，如果元素本身不具备自然顺序的特性，那么元素所属的类就必须要实现Comparable接口，把元素的比较规则定义在compareTo方法中
  3. 在TreeSet中如果比较的方法返回的是0，该元素则被视为重复元素，不允许添加
  4. 在TreeSet添加元素的时候，如果元素本身不具备自然顺序的特性，而且元素所属的类没有实现Compareable接口，那么在创建TreeSet对象的时候就必须要传入一个比较器对象
  5. 如果元素已经实现了Comparable接口，当的创建TreeSet对象的时候又传入了比较器对象，那么比较规则优先使用比较器的

推荐使用：比较器
自然排序（实现comparable的compareTo的方法）
比较排序（Comparator的compare方法 ）

Map双列集合

Map 实现了Map接口的集合类具备的特点： 存储的数据都是以键值对的形式存在的，键(key)不能重复，值(value)可以重复

Hashtable

底层是哈希表数据结构，线程是同步的，不可以存入null键，null值。效率较低，被HashMap 替代。

HashMap

底层是哈希表数据结构，线程是不同步的，可以存入null键，null值。要保证键的唯一性，需要覆盖hashCode方法，和equals方法。

LinkedHashMap

该子类基于哈希表又融入了链表。可以Map集合进行增删提高效率。

TreeMap

底层是二叉树数据结构。可以对map集合中的键进行排序。需要使用Comparable或者Comparator 进行比较排序。return 0，来判断键的唯一性。

ConcurrentHashMap

JDK1.7时，使用的是segment锁分段机制，而到了JDK1.8使用了CAS算法。

HashTable和HashMap和ConcurrentHashMap的区别

HashTable

  • 底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化
  • 初始size为11，扩容：newsize = olesize*2+1
  • 计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

HashMap

  • 底层数组+链表实现，可以存储null键和null值，线程不安全
  • 初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
  • 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
  • 插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
  • 当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀
  • 计算index方法：index = hash & (tab.length – 1)

ConcurrentHashMap

  • 底层采用分段的数组+链表实现，线程安全
  • 通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
  • Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
  • 有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
  • 扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容

Map接口常用方法

- 增
  - put(K key,V value)添加元素到map集合，返回以前和key关联的值，如果没有针对key的映射关系，则返回null。
  - putAll(Map<? extends K, ? extends V> m)
- 删 
  - clear();
  - remove(Object key);
- 判断
  - containsKey(Object key)
  - containsValue(Object value)
  - isEmpty()
- 获取
  - get(Object key)
  - size()
- 迭代
  - keySet();
  - values();
  - entrySet();
    //常用的循环迭代方式
    Set<Map.Entry<String,String>> entrys = map.entrySet();
    Iterator<Map.Entry<String,String>> it = entrys.iterator();
    while(it.hasNext()){
        Map.Entry<String,String> entry = it.next();
        System.out.println("键" + entry.getKey() + "值" + entry.getValue());
    }

泛型

为什么使用泛型

  1. 可以把运行时出现的问题提前至编译时
  2. 避免了无谓的强制类型转换

泛型类要注意的事项

  1. 类上声明的自定义泛型的具体数据类型是在使用该类创建对象的时候定义的
  2. 如果一个类已经声明了自定义泛型，该类在创建对象的时候没有指定自定义泛型的具体数据类型，那么默认则为Object类型
  3. 静态的方法不能使用类上声明的自定义泛型，如果需要使用自定义泛型只能在自己方法上声明

泛型接口：

泛型接口的定义格式：

interface 接口名<声明自定义的泛型>{

}

泛型接口要注意的细节：

  1. 接口上自定义泛型的具体数据类型是在实现该接口的时候确定的
  2. 如果一个接口已经自定义了泛型，在实现该接口的时候没有指定自定义泛型的具体数据类型，那么默认为Object类型

泛型上下限：

泛型的通配符： ？

？ super Integer 泛型的下限 只能用于Integer或者是Integer的父类类型数据

？ extends Number 泛型的上限 只能用于Number或者是Number的子类类型数据

------------- 感谢阅读-------------