JAVA高级-集合

文章目录

集合

Collection接口

Collection常用方法Iterator迭代器foreach 循环遍历集合元素 List

List接口方法ArrayList源码分析linkedList源码分析Vector源码分析 Set 接口

HashSet源码分析linkedHashSet源码分析TreeSet源码分析 Map

HashMap源码分析（重点）

HashMap添加元素过程：hash函数（扰动函数）为什么采用hashcode的高16位和低16位异或能降低hash碰撞？hash函数能不能直接用key的hashcode？什么HashMap的数组长度要取2的整数幂JDK1.8相较于之前的优化：平常怎么解决HashMap线程不安全 linkedHashMap（了解）TreeMapHashtableProperties Collections工具类

排序操作查找、替换同步控制

---

集合

Map接口和Collection接口是所有集合框架的父接口：

1.Collection接口的子接口包括：Set接口和List接口2.Map接口的实现类主要有：HashMap、TreeMap、Hashtable、.ConcurrentHashMap以及Properties等3.Set接口的实现类主要有：HashSet、TreeSet、linkedHashSet等4.List接口的实现类主要有：ArrayList、linkedList、Stack以及Vector等

Java 集合可分为 Collection 和 Map 两种体系

Collection接口：单列数据，定义了存取一组对象的方法的集合

List：元素有序、可重复的集合

Set：元素无序、不可重复的集合 Map接口：双列数据，保存具有映射关系“key-value对”的集合 Collection接口 Collection常用方法

1、添加
add(Object obj)
addAll(Collection coll)
2、获取有效元素的个数
int size()
3、清空集合
void clear()
4、是否是空集合
boolean isEmpty()
5、是否包含某个元素
boolean contains(Object obj)：
是通过元素的equals方法来判断是否是同一个对象
boolean containsAll(Collection c)：也是调用元素的equals方法来比较的。拿两个集合的元素挨个比较。
6、删除
boolean remove(Object obj) ：通过元素的equals方法判断是否是
要删除的那个元素。只会删除找到的第一个元素
boolean removeAll(Collection coll)：取当前集合的差集
7、取两个集合的交集
boolean retainAll(Collection c)：把交集的结果存在当前集合中，不影响c
8、集合是否相等
boolean equals(Object obj)
9、转成对象数组
Object[] toArray()
10、获取集合对象的哈希值
hashCode()
11、遍历
iterator()：返回迭代器对象，用于集合遍历

Iterator迭代器

迭代器的执行原理

//hasNext():判断是否还有下一个元素
while(iterator.hasNext()){
//next():①指针下移 ②将下移以后集合位置上的元素返回
System.out.println(iterator.next());
}

Iterator接口remove()方法

Iterator iter = coll.iterator();//回到起点
while(iter.hasNext()){
Object obj = iter.next();
if(obj.equals("Tom")){
iter.remove();
	}
}

foreach 循环遍历集合元素

遍历集合的底层调用Iterator完成操作。

List

List集合类中元素有序、且可重复

List接口方法

void add(int index, Object ele):在index位置插入ele元素

boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来

Object get(int index):获取指定index位置的元素

int indexOf(Object obj):返回obj在集合中首次出现的位置

int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置

Object remove(int index):移除指定index位置的元素，并返回此元素

Object set(int index, Object ele):设置指定index位置的元素为ele

List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合

ArrayList源码分析

底层Object数组
JDK1.7：ArrayList像饿汉式，直接创建一个初始容量为10的数组
JDK1.8：ArrayList像懒汉式，一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组
扩容：
如果添加导致底层elementData数组容量不够，则扩容。 默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。
结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)

linkedList源码分析

linkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为linkedList中保存数据的基本结构。Node除了保存数据，还定义了两个变量：
prev变量记录前一个元素的位置
next变量记录下一个元素的位置

private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

新增方法：

void addFirst(Object obj)
 void addLast(Object obj)
 Object getFirst()
 Object getLast()
 Object removeFirst()
 Object removeLast()

Vector源码分析

作为List接口的古老实现类；线程安全的，效率低；底层使用Object[ ] elementData存储

Set 接口

存储无序的、不可重复的数据
Set 判断两个对象是否相同不是使用 == 运算符，而是根据 equals() 方法

HashSet源码分析

底层是HashMap

linkedHashSet源码分析

linkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。
优点：对于频繁的遍历操作，linkedHashSet效率高于HashSet

TreeSet源码分析

TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。
TreeSet底层使用红黑树结构存储数据
TreeSet 两种排序方法：自然排序和定制排序。TreeSet 默认采用自然排序.（升序）

    //按照姓名从大到小排列,年龄从小到大排列
    @Override
    public int compareTo(Object o) {
        if(o instanceof User){
            User user = (User)o;
//            return -this.name.compareTo(user.name);
            int compare = -this.name.compareTo(user.name);
            if(compare != 0){
                return compare;
            }else{
                return Integer.compare(this.age,user.age);
            }
        }else{
            throw new RuntimeException("输入的类型不匹配");
        }

    }

Map

用于保存具有映射关系的数据:key-value

HashMap源码分析（重点）

JDK 7及以前版本：HashMap是数组+链表结构(即为链地址法)
JDK 8版本发布以后：HashMap是数组+链表+红黑树实现。

JDK1.7

JDK1.8

HashMap添加元素过程：

1判断数组是否为空，为空进行初始化;2不为空，计算 k 的 hash 值，通过 (n - 1) & hash计算应当存放在数组中的下标 index ;3查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；4存在数据，说明发生了hash冲突, 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；5如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创建树型节点插入红黑树中；6如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8， 大于的话链表转换为红黑树；7插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。 hash函数（扰动函数）

hash函数是先拿到通过key 的hashcode，是32位的int值，然后让hashcode的高16位和低16位进行异或操作。

设计有二点原因：
1.一定要尽可能降低hash碰撞，越分散越好；
2.算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

为什么采用hashcode的高16位和低16位异或能降低hash碰撞？hash函数能不能直接用key的hashcode？

因为 key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。int值范围为**-2147483648~2147483647**，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。你想，如果HashMap数组的初始大小才16，用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。

2.源码中模运算就是把散列值和数组长度-1做一个"与"操作，位运算比%运算要快。 什么HashMap的数组长度要取2的整数幂

因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

JDK1.8相较于之前的优化：

1.HashMap map = new HashMap();//默认情况下，先不创建长度为16的数组，当首次调用map.put()时，再创建长度为16的数组2.数组为Node类型，在jdk7中称为Entry类型3.形成链表结构时，新添加的key-value对在链表的尾部（七上八下）.链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；4.扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；5.在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容； 平常怎么解决HashMap线程不安全

Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。

1.HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大；2.Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；3.ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。 linkedHashMap（了解）

在HashMap存储结构的基础上，使用了一对双向链表来记录添加
元素的顺序。

static class Entry extends HashMap.Node {
             Entry before, after;//能够记录添加的元素的先后顺序
             Entry(int hash, K key, V value, Node next) {
                super(hash, key, value, next);
             }
         }

TreeMap

TreeSet底层使用红黑树结构存储数据。
TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。

Hashtable

Hashtable是个古老的 Map 实现类，JDK1.0就提供了。不同于HashMap，Hashtable是线程安全的。

Properties

Properties 类是 Hashtable 的子类，该对象用于处理属性文件。

Collections工具类

Collections 是一个操作 Set、List 和 Map 等集合的工具类

排序操作

reverse(List)：反转 List 中元素的顺序

shuffle(List)：对 List 集合元素进行随机排序

sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序

sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序

swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

查找、替换

Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素

Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素

Object min(Collection)
Object min(Collection，Comparator)
int frequency(Collection，Object)：返回指定集合中指定元素的出现次数

void copy(List dest,List src)：将src中的内容复制到dest中

boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换List 对象的所有旧值

同步控制

Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题