集合相关

Collection

集合概述

和数组一样,都是对多个数据进行储存操作的结构,简称Java容器

此时的存储 是指内存的储存 不涉及持久化储存(txt,jpg,avi,数据库中)

主要有两个接口 Collection 和 Map

Collection

是单列集合,主要方法 创建集合引用子类对象

添加的对象,对象要重写equals方法 因为判断是否包含要作比较

添加元素add(obj),/ addAll(Collection c)添加集合

删除元素remove(obj),删除所有void clear();判断是否为空isEmpty();

判断是否包含元素contains(obj);判断是否包含集合containsAll(Collection c);

获取hashcode值 判断元素是否与集合相等equals(obj)

转换为数组toArray() 获取迭代器Iterator iterator();

数组转为集合 Array.asList

Iterator

遍历集合使用iterator 是一种迭代模式

首先获得迭代器

1
 Iterator i = Collection.iterator();
2
for(i.hasNext){
3
​	System.out.println(i.next());
4
}

遍历时有指针默认在集合第一个元素前

其中主要方法 hasNext(),判断下一个是否有元素

next方法会移动指针 会返回下移到所在位置的元素

Set和List接口继承了Collection

常用的List的三个实现类 ArrayList,LinkedList,Voctor 都是存储有序可以重复的数据

List有索引 向List里添加对象 要重写该类的equals方法

有自己的方法

增add(obj) 删remove(可以元素 也可以集合) 改set 查get()

插入add(index,obj) 长度size(是添加元素的个数)

遍历1foreach 2 iterator 3 普通for循环

ArrayList

底层是Object[]实现 , 有索引,插入和删除慢,查找,更改快,线程不安全的效率高

1.7初始化就是长度为10

1.8初始化是{} 在add的时候才初始化长度

扩容是原数组的1.5倍

已知长度的时候建议用有参构造方法

ArrayList 的实现原理

  • 1.7中 当我们new ArrayList 的时候 底部会初始化一个长度为10的Object[] elementData
  • 我们调用add()就是给elementData[]赋值
  • 当添加的元素个数大于数组长度 会扩容数组到原来长度的1.5倍 并复制原来的数据到新的数组中
  • 1.8中 当我们new ArrayList()初始化的数组长度为0当我们首次调用add()是才会创建长度为10的Object[] elementData

LinkedList实现原理

  • 底层是双向链表的结构 维护了fist和last都得Node类型 Node里面包括item,prev和next
  • 我们添加元素默认是从最后
  • 增删快,查找修改慢, 是线程不安全的

Vector

早期的集合 比接口List还早 线程安全的 效率低 底层也是Object[]实现的

扩容是原数组的2倍

Set 主要实现类 HashSet LinkedHashSet TreeSet

特点 存储无序 不重复的 可以存储null值

无序体现不是随机性,而是指不是按照数组的索引排列,而是根据hash值

不重复是比较hash值还有比较equals

对于HashSet LinkedHashSet 添加的对象要重写hashcode和equals方法

TreeSet 比较方法是基于comperable 和 compartor 底层是红黑树实现

我们如何需要频繁使用遍历 建议使用LinkedHashSet 因为它底层是链表实现

维护了前一个和后一个

HashSet实现原理

我们在new HashSet 的时候 ,底层会创建一个长度为16的数组

我们在调用add()添加元素时 首先调用添加元素所在类的HashCode方法

然后通过计算算出所要放的位置,如果该位置上没有元素 直接添加

如果有元素或者多个元素 会先比较hashcode 如果有相同的 添加失败

如果没有相同的再比较equals 如果有相同的 添加失败

如果没有添加成功在同一位置

JDK7新添的元素会在数组中 原来的会在链表下

JDK8新添的元素会在链表下 原来的会在数组中

Map

  • Map 是双列集合 储存特点的key-value

  • key是唯一无序的 相当于set key所在类要重写equals()和hashcode()

  • value可重复无序 相当于collection

  • key-value构成一个entry[]

  • entry[]相当于set

  • 主要实现类

  • HashMap:线程不安全的效率高 可以存放null值

  • LinkedHashMap:继承了HashMap在原有的基础上维护了两个指针 从而遍历比HashMap效率高 也是线程不安全

  • TreeMap:添加的对象是同一类的 用compare和comperble做比较

  • Hashtable:早期的实现类 线程安全的 效率低 不能存放null值

  • properties:存储的类型都是String 常用于配置文件

  • HashMap实现原理

    HashMap在1.7中

  • 我们在new HashMap()时 会初始化初始容量为16和负载因子=0.75

  • 之后会去经过一系列判断列如初始容量位移为16 和得到Threshould临界值 生成长度为16的entry[] table

  • 在调用put()时 会判断是否为null 在hashtable中没有

  • 然后会先调用key所在类的hashcode()得到hash值 然后再计算得到再entry[]中的位置

  • 如果该位置上没有元素 则添加成功

  • 如果该位置上有元素或多个(多个是以链表存在的) 会比较hash值

  • 如果hash值没有一样的 则添加成功

  • 如果hash值一样 会调用key所在类的equals()

  • 如果返回结果为false 则添加成功

  • 如果返回结果为true 会用新的key所对应的value覆盖原有的value(可以看做的修改操作)

  • 对应在有元素的情况下添加成功 使用链表的形式存储 1.7中会将新的元素放在数组中 指向原来的元素

  • 1.8是用原来的元素指向新的元素

  • 在不断的添加过程中 涉及到扩容 扩容条件不是大于数组长度才扩容 因为在放元素的时候 很可能出现有的位置为空 其他的是链表 效率低

  • 当添加的元素>扩容临界值(就是数组容量*负载因子)是并且所要放的位置不为空是 会选择扩容

  • 扩容是扩容原来的2倍 会把原来的数据复制到新的数组 还会重写计算元素位置 有效的避免链表过长

  • 所以1.7底层结构是 数组+链表

    HashMap在1.8中

    我们new HashMap()是初始化了负载因子 我们在调用put()时才会创建长度为16的数组

  • 而且是Node[] table不是Entry[] table

  • 还有一个更改是 当某个索引上的元素以链表形式存在个数>8并且当前数组的长度>64 该位置的元素会以红黑树的形式存储

  • 1.8底层结构是 数组+链表+红黑树

关于HashMap容量是2的N次幂和扩容也是2的N次幂

因为初始容量initial capacity是2的N次幂(16) put()会调用putVal()

里面用的是(n-1) & hash(所在类hashcode方法算出的值)

扩容热size也有用到(n-1) & hash

避免hash碰撞 可以是元素均匀的分布到数组上 避免形成链表 是查询效率降低

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

一直不够努力<br><br>To be a better man<br>