java 学习笔记-集合（五）

阅读量：6478 次

发布时间：2019-06-23

本文共 5511 字，大约阅读时间需要 18 分钟。

容器（Collection）

标签：javase 核心容器，面试必问。

List

ArrayList

底层实现是数组，查询快，增删慢，线程不安全。

我们知道，数组长度是有限的，而ArrayList是可以存放任意数量的对象，长度不受限制，那么它是怎么实现的呢?
1、本质上就是通过定义新的更大的数组，将旧数组中的内容拷贝到新数组，来实现扩容。
2、ArrayList的Object数组初始化长度为如果我们存储满了这个数组，需要存储第11个对象，就会定义新的长度更大的数组，并将原数组内容和新的元素一起加入到新数组中，源码如下：

LinkedList

底层采用双向链表实现，增删块，查询慢，线程不安全
双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。

注意事项：entry在英文中表示“进入、词条、条目”的意思。在计算机英语中一般表示“项、条目”的含义。

Map

HashTable和Hashmap区别

1、hashMap，线程不安全，效率高。允许k v为null

2、hashTable，线程安全，效率低，不允许k v为null

HashMap底层实现

底层实现是hash表

数据结构中以数组和链表实现存储
1、数组：占用空间连续。寻址容易，查询速度快。但是，增删速度慢。
2、链表：占用空间不连续。寻址困难，查询速度慢。但是，增删速度快。

结合数组和链表的优点（增删快，查询块）---答案就是哈希表（哈希表的本质就是"数组"+"链表"）

HashMap基本结构：

我们打开HashMap源码，发现有如下两个核心内容：

其中Entry[] table 就是hashmap核心的数组结构，也称之为"位桶数组",其源码如下：

一个Entry对象存储了：

1、hash：健对象的hash值

2、key：健对象；value：值对象

3、next：下一个节点的引用

显然每一个entry对象都是一个单向链表结构，如下

然后我们画出Entry[] 数组结构（也是HashMap结构）

HashMap存储数据过程put(key , value)：

核心是如何产生hash值，该值用来对应数组的存储位置。

我们的目地是将"key-value"两个对象成对存放到HashMap的Entry[]数组中
1、获得key对象的hashcode
调用key对象的hashcode(),生成hashcode
2、根据hashcode计算hash值（要求[0,数组长度-1)）
hashcode是一个整数，我们需要将他转化为[0,数组长度-1)，要求转化后hash值尽量均匀的分布在[0,数组长度-1)这个区间，避免hash冲突。

i. 一种极端简单和低下的算法是：
1、hash值 = hashcode/hashcode;
2、也就是说，hash值总是1。意味着，键值对对象都会存储到数组索引1位置，这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”，HashMap也退化成了一个“链表”。

ii. 一种简单和常用的算法是(相除取余算法)：
1、hash值 = hashcode%数组长度
2、这种算法可以让hash值均匀的分布在[0,数组长度-1]的区间。早期的HashTable就是采用这种算法。但是，这种算法由于使用了“除法”，效率低下。JDK后来改进了算法。首先约定数组长度必须为2的整数幂，这样采用位运算即可实现取余的效果：hash值 = hashcode&(数组长度-1)。

iii. 如下为我们自己测试简单的hash算法：

public class Test {    public static void main(String[] args) {        int h = 25860399;        int length = 16;//length为2的整数次幂,则h&(length-1)相当于对length取模        myHash(h, length);    }    /**     * @param h  任意整数     * @param length 长度必须为2的整数幂     * @return     */    public static  int myHash(int h,int length){        System.out.println(h&(length-1));        //length为2的整数幂情况下，和取余的值一样        System.out.println(h%length);//取余数        return h&(length-1);    }}

运行如上程序，我们就能发现直接取余(h%length)和位运算(h&(length-1))结果是一致的。事实上，为了获得更好的散列效果，JDK对hashcode进行了两次散列处理(核心目标就是为了分布更散更均匀)，源码如下：

3、生成Entry对象
如上所述，一个Entry对象包括4部分：hash值、key对象、value对象、next（指向下一个Entry对象的引用）

4、将Entry对象放到table数组中
如果本Entry对象对应的数组索引位置还没有放Entry对象，泽直接将Entry对象放入数组；如果对应索引位置已经有Entry对象，则将已有的Entry对象的next指向本Entry对象，形成链表。

总结如下过程：

当添加一个元素（key,value）时，首先计算key的hash值，依此确定插入数组中的位置，但是已经存在统一hash值的元素已经被放入数组同一位置了，这时就添加到同一hash值元素的后面，他们在数组的同一位置就形成了链表，同一个链表上的hash值是相同的，所以说数组存放的是链表。JDK8中，当链表长度大于8时，链表转化为红黑树，这样大大提高了查找效率。

HashMap取数据过程get(key)
1、我们需要通过key对象获取"健值对"对象，进而返回value对象。明白了存储数据过程，取数据比较简单了。
2、获得key的hashcode，通过hash散列算法得到hash值，进而定位到数组的位置。
3、在链表上挨个比较key对象。调用equals()方法，将key对象和链表上的所有节点的key对象进行比较，直到碰到返回true节点对象为止。
4、返回equals()为true的节点对象value对象
明白了存取cunqu数据的过程，我们再来看一下hashcode()和equals()的关系
Java中规定，两个内容相同(equals()为true)的对象必须具有相等的hashCode。因为如果equals()为true而两个对象的hashcode不同;那在整个存储过程中就发生了悖论。

扩容问题：

hashmap的位桶数组，初始大小为1<<4(16)。实际使用时，虽然大小可变。如果位桶数组中的元素达到（0.75* 数组length）就重新调整数组大小变为原来的两倍大小。

扩容很耗时。扩容的本质是定义新的更大数组，并将旧数组内容内容挨个拷贝到新数组中。

JDk8将链表在大于8的情况下变为红黑树（红黑二叉树）

JDK8中，HashMap在存储一个元素时，当对应链表长度大于8时，链表就转换为红黑树，这样又大大提高了查找的效率。

TreeMap的使用和底层实现

TreeMap是红黑二叉树的典型实现。我们打开TreeMap的源码，发现里面有一行核心代码：

private transient Entry
    
      root = null;

root用来存储整个树的根节点。我们继续跟踪Entry(是TreeMap的内部类)的代码：

可以看到里面存储了本身数据、左节点、右节点、父节点、以及节点颜色。 TreeMap的put()/remove()方法大量使用了红黑树的理论。本书限于篇幅，不再展开。需要了解更深入的，可以参考专门的数据结构书籍。
1、TreeMap和HashMap实现了同样的接口Map，因此，用法对于调用者来说没有区别。
2、HashMap效率高于TreeMap;
3、在需要排序的Map时才选用TreeMap。

Set接口

Set接口继承自Collection，Set接口中没有新增方法，方法和Collection保持完全一致。我们在前面通过List学习的方法，在Set中仍然适用。因此，学习Set的使用将没有任何难度。

Set容器特点：无序、不可重复。无序指Set中的元素没有索引，我们只能遍历查找;不可重复指不允许加入重复的元素。更确切地讲，新元素如果和Set中某个元素通过equals()方法对比为true，则不能加入;甚至，Set中也只能放入一个null元素，不能多个。

Set常用的实现类有：HashSet、TreeSet等，我们一般使用HashSet。

HashSet基本使用

重点体会“设置是无序，不可重复”的核心要点。

HashSet底层实现

HashSet是采用哈希算法实现，底层实际是用HashMap实现的(HashSet本质就是一个简化版的HashMap)，因此，查询效率和增删效率都比较高。我们来看一下HashSet的源码：

我们发现里面有个map属性，这就是HashSet的核心秘密。我们再看add()方法，发现增加一个元素说白了就是在map中增加一个键值对，键对象就是这个元素，值对象是名为PRESENT的Object对象。说白了，就是“往set中加入元素，本质就是把这个元素作为key加入到了内部的map中”。

由于map中key都是不可重复的，因此，Set天然具有“不可重复”的特性。

TreeSet使用和底层实现

TreeSet底层实际是TreeMap实现的，内部维持了一个简化版的Treemap,通过key来存储Set元素。TreeSet内部实现元素排序，需要实现Comparable接口。这样，才能根据compareTo()方法比较对象之间的大小，才能进行内部类排序。

使用TreeSet要点：

(1) 由于是二叉树，需要对元素做内部排序。如果要放入TreeSet中的类没有实现Comparable接口，则会抛出异常：java.lang.ClassCastException。

(2) TreeSet中不能放入null元素。

使用Iterator迭代器遍历容器元素(List/Set/Map)--如果遇到遍历容器时，判断删除元素的情况，使用迭代器遍历!

迭代器遍历List

public class TestIterator{    public static void main(String[] args){        List
    
      list = new ArrayList<>();        for(int i = 0; i<5;i++){            list.add("ad"+i);        }        System.out.println(list);        //使用迭代器进行遍历        Iterator
     
       it = list.iterator();        while(it.hahNext()){            String next = it.next();            if(next.endWith("3")){                list.remove()            }        }        System.out.println(list);    }}

Map
    
      maps = new HashMap
     
      ();Set
      
         keySet =  maps.keySet();for(Integer id : keySet){System.out.println(maps.get(id).name);}

Set
    
     
      >  ss = maps.entrySet();for (Iterator iterator = ss.iterator(); iterator.hasNext();) {    Entry e = (Entry) iterator.next();     System.out.println(e.getKey()+"--"+e.getValue());