java 学习笔记-集合(五)

容器(Collection)

标签:javase 核心容器,面试必问。


List

ArrayList

  • 底层实现是数组,查询快,增删慢,线程不安全。
  • 我们知道,数组长度是有限的,而ArrayList是可以存放任意数量的对象,长度不受限制,那么它是怎么实现的呢?
    1、本质上就是通过定义新的更大的数组,将旧数组中的内容拷贝到新数组,来实现扩容。
    2、ArrayList的Object数组初始化长度为如果我们存储满了这个数组,需要存储第11个对象,就会定义新的长度更大的数组,并将原数组内容和新的元素一起加入到新数组中,源码如下:
    1523295-20190529084937791-1524561751.png

LinkedList

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

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

Map

HashTable和Hashmap区别

  • 1、hashMap,线程不安全,效率高。允许k v为null
  • 2、hashTable,线程安全,效率低,不允许k v为null

HashMap底层实现

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

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

HashMap基本结构:

  • 我们打开HashMap源码,发现有如下两个核心内容:
    1523295-20190529084954966-1282165616.png

  • 其中Entry[] table 就是hashmap核心的数组结构,也称之为"位桶数组",其源码如下:
    1523295-20190529085002635-157379649.png

一个Entry对象存储了:
1、hash:健对象的hash值
2、key:健对象;value:值对象
3、next:下一个节点的引用

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

1523295-20190529085019260-1910779627.png

  • 然后我们画出Entry[] 数组结构(也是HashMap结构)

1523295-20190529085026607-1228029118.png

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

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

1523295-20190529085039642-54086665.png

  • 我们的目地是将"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进行了两次散列处理(核心目标就是为了分布更散更均匀),源码如下:

1523295-20190529085133798-295612258.png

  • 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的内部类)的代码:
    1523295-20190529085151027-836219544.png

  • 可以看到里面存储了本身数据、左节点、右节点、父节点、以及节点颜色。 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的源码:
    1523295-20190529085203723-1576112162.png

  • 我们发现里面有个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());

如下情况,可能需要我们重写equals/hashCode方法:

1) 要将我们自定义的对象放入HashSet中处理。

2) 要将我们自定义的对象作为HashMap的key处理。

3) 放入Collection容器中的自定义对象后,可能会调用remove、contains等方法时。

JDK1.5以后增加了泛型。泛型的好处:

1) 向集合添加数据时保证数据安全。

2) 遍历集合元素时不需要强制转换。

转载于:https://www.cnblogs.com/willem-xin/articles/10941676.html

原文链接:加载失败,请重新获取