JAVA-集合

2023-12-30 19:26:06

JAVA-集合

整体结构:
在这里插入图片描述
在这里插入图片描述

Collection

collection (以实现子类ArrayList为例:)

  • 存放类型为 Object,
  • 根据实现类的不同;其存放的元素可重复可 不重复; 有序或无序

在这里插入图片描述

迭代器

Iterator对象即为迭代器: 遍历Collection集合的元素

凡是实现 Iterator接口,都会有方法:iterator()

Iterator接口未实现Collection接口!!!

使用:

  • Collection arrayList = new ArrayList();
                arrayList.add("a");
                Iterator iterator = arrayList.iterator(); // 得到迭代器
                while (iterator.hasNext()) {             // 如果下一个有值
                    Object next = iterator.next();       // 获取下一个元素
                    System.out.println(next);
                }
    

增强for循环 : 简化版的迭代器

  • 底层仍是迭代器

List

  • List 子接口:该集合中元素有序,可重复
  • 支持根据索引(序号)查询 ,索引是从 0 开始的
ArrayList
  1. 本质上为一Object 类型的数组 elementData,来存储数据
  2. 可加入null元素
  3. add 时 没有synchronized线程不安全 效率较高; 多线程不推荐用
transient Object[] elementData; // 不会被序列化

transient:被修饰的属性不会被序列化

  1. ArrayList 有两个构造方法:

    • 无参: 初始容量=0, 第一次添加扩容到10,若满了则扩容至1.5倍。

      • 以无参创建的list 实际为空数组(设置容量为10),直到向数组add元素时,才 new Object[10]
    • 有参: 指定初始大小,之后扩容为 原来的1.5倍

      • new ArrayList( int num);
        
      • 该有参构造方法并不是将ArrayList()初始化为指定长度(容量),而是指定了其内部的Object数组的长度,指定了容量。当我们调用size()时,返回的是其实际长度,而非容量大小。

      • 对于ArrayList,想初始化设定长度,还是一个for循环插入吧。初始化不可靠。

Arrays.copyOf
Integer[] newArr = Arrays.copyOf(arr, x); 
  1. 从 arr 数组中,拷贝x个元素到 newArr 数组中

  2. 如果拷贝的长度 > arr.length 就在新数组的后面 增加 null

  3. 如果拷贝长度 < 0 就抛出异常 NegativeArraySizeException

Vector

Vector底层亦是一个对象数组:

protected Object[] elementData;
  1. 线程同步(线程安全) 该类的操作方法带有: synchronized\
  2. 适用于线程同步的场景;效率不高
    在这里插入图片描述
LinkedList
  • linkedList 底层:双向链表

  • first:首节点 ; last:尾结点

  • Node节点对象, prev属性指向前一节点、next属性指向后一节点

  • 删除、添加效率高; 链表嘛

(5条消息) LinkedList常用方法_一个浪子-CSDN博客_linkedlist方法

=

LinkedList 与ArrayList
  • LinkedList 善于增删
  • ArrayList 善于改查

Set

  • 无序,不可重复,可存一个null元素,无索引样,

就算插入多个重复元素,也只存一个

  • Set 接口也是 Collection 的子接口,因此,常用方法和 Collection 接口一样

没有 get(),不能取出元素

HashSet set = new HashSet();
set.add("lucy");//添加成功 
set.add("lucy");//加入不了 
set.add(new Dog("tom"));//OK 
set.add(new Dog("tom"));//Ok
set.add(new String("hsp"));//ok 
set.add(new String("hsp"));//加入不了

Dog不是同一对象

String重写了 equals方法,值一样;故加不了

HashSet

数组+链表是散列表

实现Set接口,其底层为 HashMap

public HashSet() { 
    map = new HashMap<>();
}

HashMap底层为 数组+链表+红黑树

  • 当数组存不下时,在每个数组后面拓展链表
  • 链表满了;将链表变成红黑树;便于查找
为什么HashSet 底层 HashMap 的 value为何是PRESENT而不写成null?

(12条消息) HashSet底层HashMap的value为何是PRESENT?_missbearC的博客-CSDN博客_hashset present

先看一下HashMap 的put方法: HashMap 的put()方法

HashSet add() 底层

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
  • 如果 map.put(e, PRESENT)时,value 写的是null,则不论put成功或失败都会返回null,那么 add()方法每次返回都是true,也就不能够确认add成功还是失败了。

HashSet的remove方法

 public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

(12条消息) HashMap的remove()方法详解_瓦坎达forever的博客-CSDN博客_hashmap.remove

HashMap的remove方法: 会返回该key对应的value值

  • 如果HashMap底层的value保存的都是null的话,那么remove成功或者是失败都会返回null ,同样无法分辨。
HashSet添加元素

(29条消息) HashMap底层实现原理_fengxi_tan的博客-CSDN博客_hashmap底层实现原理

add()

HashSet中元素是否有序,取决于hash值得到的 索引

  1. 添加元素: 先得到hash值= key.hashCode()) ^ (h >>> 16) 不只是hashCode() 方法),

    • hash值的目的:table表的索引值
  2. 找到存储数据表(数组)table

    该所与位置是否已有元素

    • 没有:直接存入
    • 已有:判断条件: (判断是否为同一对象(hash值+对象地址)|| 该类的equals)
      • 调用equals方法(可自定义,注意不同类是否重写:没重写就是比较地址)比较
        • 相同:放弃添加 (HashMap为覆盖value)
        • 不同:一直for循环比较;直到都不同添加到末尾(链表)
          • 循环期间存在不同的也放弃添加
  3. 若一链表元素个数>= 8 且 table的长度>=64,将进行 树化(红黑树)

    • 若 某一链表长度>=8, 但 table表的长度<64,优先扩容表数组
扩容数组机制

第一次添加,table数组==初始化==扩容至16,临界值为12

临界值当前容量 * 0.75(加载因子);即 当数组已存个数size>此值后就开始扩容

扩容: 扩成原来的二倍 (<< 1

扩容有两种情况

  • 一种是链表到8、table表的长度<64
  • 另一种是数组存储到了临界值
扩容后新元素存放位置
  • java 在扩容的时候会新建一个新的 Node<K,V>[] 来存放扩容之后的值,并将旧有的Node数组置空;

至于旧有值移动到新的节点的时候存放于哪个节点,Java 是根据 (e.hash & oldCap) == 0 来判断的:

(e.hash & oldCap)就是:当前元素的hash 与 旧容器容量做 &(与)运算

hash():

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} 
  • ①若 e.hash & oldCap = 0的,在新表的位置=旧表中位置 ,记为低位区链表lo开头-low;

  • ② 若e.hash & oldCap != 0的,位置为旧表位置+旧表容量,记为高位区链表hi开头high.

    • 新的位置=老的位置+老的数组长度。

原文链接:https://blog.csdn.net/qq_37155154/article/details/115161022

(12条消息) jdk8之HashMap resize方法详解(深入讲解为什么1.8中扩容后的元素新位置为原位置+原数组长度)_诺浅的博客-CSDN博客_hashmap扩容后的位置

LinkedHashSet

底层: 数组+双向链表

有序!无重复元素

在Node的基础上 另加俩属性:next、prev

add过程:

  • 先求该元素的 hash值,求索引,定位到table表的位置

  • 将元素加入

    • 若此处无元素:加入
    • 与已有的元素比较(与hashSet一致):
      • 相同:不添加
      • 反之,加在其后面
        • 记录之前最新添加的元素(tail,双向链表末尾),使得:
        tail.next = newElement;
        newElement.pre = tail;
        tail = newElement; // 最新添加的元素为 双向链表的末尾
        

在这里插入图片描述

在这里插入图片描述

Map

整体结构:
在这里插入图片描述
常用API:
在这里插入图片描述

Map 结构:

  • key-value 键值对,两者一 一对应
  • key不可重复–Set;value可以重复–Collection
    • 当有相同的 k , 就替换原先的Value

      在这里插入图片描述

在这里插入图片描述

Node<k,v>即为HashMap的元素类型。

为了便于遍历map的key-value

  • 创建集合 EntrySet;每个元素的 定义类型是Entry使用类型是Node

    • (实质上就是 Node因为Node实现了 Entry接口):
    • static class Node<K,V> implements Map.Entry<K,V>
  • Map map = new HashMap();
    
    Set set = map.entrySet();
    for (Object o : set) {
        Map.Entry entry = (Map.Entry) o; 
        // set 中元素为Entry类型,Entry存放的就是<k,v>, 即: EntrySet< Entry<k,v> >
    	// 向下转型
        entry.getKey();
        entry.getValue();
    }
    
Map遍历:

HashMap 的 7 种遍历方式与性能分析!「修正篇」 (qq.com)

由Key遍历
System.out.println("第一种《根据key集合》");

Set keySet = map.keySet(); // 获取到 key集合
for (Object o :keySet){
    Object o1 = map.get(o);
    System.out.println(o+"--"+o1);

}
System.out.println("第一种1迭代器《》");
Iterator iterator = keySet.iterator();
while (iterator.hasNext()) {
    Object next =  iterator.next();
    System.out.println(next+"---"+map.get(next));

}
获取value集合
Map map = new HashMap();
Collection values = map.values();
for (Object o : values){
    System.out.println(o);
}
EntrySet获取 k-v
Map map = new HashMap();
Set set = map.entrySet();
for (Object o : set) {
    Map.Entry entry = (Map.Entry) o;
    System.out.println( entry.getKey()+"--"+ entry.getValue());
}
HashMap

与HashSet源码一样,无序(因为是Hash表存储)

HashMap:线程不安全:因为方法没有 synchronized关键字

put()方法

(29条消息) HashMap底层实现原理_fengxi_tan的博客-CSDN博客_hashmap底层实现原理

  • 如果不存在则执行插入,返回 null 。

    • (第一次插入该元素,则返回null(表示之前没加入过。))

  • 如果插入的 key 对应的 value 已经存在,则执行 value 替换操作,返回旧的 value 值,

  • 但如果put失败也是返回 null
    在这里插入图片描述

为什么HashMap的长度一定是2的次幂?

(8条消息) HashMap初始容量为什么是2的n次幂及扩容为什么是2倍的形式_猿人小郑的博客-CSDN博客_hashmap扩容为什么是2倍

集合中添加元素时,会使用(n - 1) & hash计算方法来得出该元素在集合中的位置

  • 当HashMap的容量是2的n次幂时,(n-1)的2进制也就是1111111***111这样形式的,这样与添加元素的hash值进行位运算时,能够充分的散列,使得添加的元素均匀分布在HashMap的每个位置上,以减少hash值碰撞,避免形成链表的结构,使得查询效率降低!

不能让参与&运算的二进制数有0的存在 ,不然0对应的那一位参与&运算永远是0,也就意味着数组的某一个位置会&不出来,hash值不能被充分散列。如果长度是2的幂,参与&运算的二进制数的每一位都会是1,就会避免这种情况。

Java集合常见面试题总结(下)–hashmap-的长度为什么是-2-的幂次方 | JavaGuide

  • 因为 hash值的取值范围是:-2147483648 到 2147483647 大概40亿的映射空间,(目的是这样的hash比较均匀,不易出现碰撞),而数组放不下这么大的下标,需要对其取余。
  • 而 取余操作 hash%length 若除数为2的幂次的话,等价于 length-1 & hash;大大提高了运算效率。

另一种解释:

这是因为当table.length为2的幂次时,(table.length-1) 的二进制形式的特点是除最高位外全部是1,配合这种索引计算方式可以实现key在table中的均匀分布 ,减少hash冲突——出现hash冲突时,结点就需要以链表或红黑树的形式链接到table[i],这样无论是插入还是查找都需要额外的时间。
原文链接:(31条消息) 大厂之路一由浅入深、并行基础、源码分析一 “J.U.C”之collections框架:ConcurrentHashMap扩容迁移等方法的源码分析_slow is fast.的博客-CSDN博客

rehash:

背景-- 当前hash表容量装不下了,需要新建更大的hash表,将数据从老的hash表 迁移到 新的hash表

疫苗:Java HashMap的死循环 | 酷 壳 - CoolShell

HashMap的ReHash图解 - 简书 (jianshu.com)

Transfer():
void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //下面这段代码的意思是:
    //  从OldTable里摘一个元素出来,然后放到NewTable中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);// 求出放到新表的位置
                e.next = newTable[i];
                // newTable[i];一开始是null
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
} 

在这里插入图片描述

困惑的点:

  1. 先是for循环遍历旧表的数组,之后开始do-while遍历每个数组元素后面的链表。
    1. e这个链表节点一直是在旧表中。
  2. newTable[i] 是 要放到新表的数组元素(从这里开始放链表节点)
  3. 旧数据放到新的hash表的位置:key % 新表大小
  4. 链表插入的方式是头插法
  5. newTable[]是在每个线程里new出来的,属于线程私有的;所以,第一次,里面并没有值(或者是随机的值);

(29条消息) 记java7 HashMap的transfer()方法中的疑惑_山鬼谣me的博客-CSDN博客_hashmap transfer

在这里插入图片描述

HashTable

HashTable和HashMap的区别详解 - 割肉机 - 博客园 (cnblogs.com)

(41条消息) HashMap和Hashtable的区别

Hashtable继承Dictionary类,

  • 存放的元素是键值对,存入对象 Entry

  • 键和值 都不能为空;否则抛 空指针异常

  • 线程安全的(synchronized)而HashMap线程不安全

  • 初始化:数组大小:11;

    • 加载因子:0.75
    • 临界值:11 * 0.75 = 8(8.25)
  • 扩容机制

    • 当前个数 >= 数组长度时扩容;
    • 按照;2X+1扩容
int newCapacity = (oldCapacity << 1) + 1;

Hashtable采用取模的方式来计算数组下标,同时数组的长度尽量为素数或者奇数,这样的目的是为了减少Hash碰撞,计算出来的数组下标更加分散,让元素均匀的分布在数组各个位置。

  • Hashtable计算hash值,直接用key的hashCode(),
  • Hashtable在求hash值对应的位置索引时,用取模运算
  • 而HashMap重新计算了key的hash值,而HashMap在求位置索引时,则用与运算

在这里插入图片描述

Properties

Map接口的实现类。

继承HashTable,所以 key&value 都不能为空

在这里插入图片描述

TreeSet

底层:TreeMap;二叉树

本质上靠的是二叉树的中序遍历。(左中右)

public TreeSet() {
    this(new TreeMap<>());
}
  • 无参构造:调用集合元素的compareTo(Object obj),排序按照添加元素类所实现的方法比较

    • Integer和String对象都可以进行默认的TreeSet排序
      • 默认以ASCll码排序元素,升序【按照key的字典顺序来排序(升序) 】
    • 如果对应的类没有实现Comparable接口,则会引发ClassCastException异常
      • 自己定义的类必须实现Comparable接口,并且覆写相应的compareTo()函数,才可以正常使用。
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    
  • 重写匿名内部类new Comparator<Object>() compare()方法

    • 则比较时,按照重写的方法进行比较排序

    • if (cmp < 0)
          t = t.left;
      else if (cmp > 0)
          t = t.right;
      else
          return t.setValue(value);
      
      • 结果<0;将新元素放其左边
      • 结果>0;将新元素放其右边
      • 结果=0;则重新设置其 value值,key值不变,认为元素相同
        • key不变 value会重新set ,因为是treeset单列的 所以value值都一样替换啥啊 值一直都是PRESENT 这是键
comparable 和 Comparator 的区别

面试官:元素排序Comparable和Comparator有什么区别? - 腾讯云开发者社区-腾讯云 (tencent.com)

  1. 字面含义不同

    • Comparable 翻译为中文是“比较”的意思,而 Comparator 是“比较器”的意思。Comparable 是以 -able 结尾的,表示它自身具备着某种能力,
    • 而 Comparator 是以 -or 结尾,表示自身是比较的参与者,这是从字面含义先来理解二者的不同。
  2. 应用场景:

    1. comparable 需要 原有的类实现 ComparablecompareTo 方法,否则无法使用 Collection.sort()排序
      1. Comparator 不需更改原有的类,需创建个比较器或匿名构造器使用 Collections.sort() 排序; Collection可以用各自的sort方法排序 (list.sort)
TreeMap

又称有序表,把key按照顺序排序,

线程不安全

重写匿名内部类new Comparator<Object>() compare()方法“

  • 结果=0;则重新设置其 value值,key值不变
    • key不变 value会重新set ,TreeMap
    • TreeMap通过红黑树实现Map接口的类,key不可以为null,会报NullPointerException异常,value可以为null。
TreeMap常用方法:

get(Object key)            //put(K key, V value)      // 增
remove(Object key)     // 删
firstKey()                       // 返回map中最小的key
lastKey()                       // 返回map中最大的key
ceilingKey(K key)         // 返回大于等于key的最小key
floorKey(K key)            // 返回小于等于key的最大key
higherKey()                   // 返回严格大于key的最小key
lowerKey()                     // 返回严格小于key的最大key
containsKey(Object Key)
containsValue(Object Value)
clear()
clone()
entrySet()
firstEntry()
lastEntry()
floorEntry(K key)
ceilingEntry(K key)
higherEntry()
lowerEntry()
size()

总结

单列:(Collection)

  • 允许重复

    • List
      • 增删多: LinkedList (底层:双向链表)
      • 查改多:ArrayList (底层:动态数组Object类型)
  • 不允许重复:

    • Set

      • 无序:HashSet 【底层:HashMap,即:数组+链表+红黑树】

      • 有序:TreeSet 【底层:TreeMap】

      • 有序: LinkedHashSet【底层:LinkedHashMap】

双列:键值对 Map

  • HashMap 【底层:数组+链表+红黑树】线程不安全
  • HashTable 【底层与HashMap一致】,线程安全,继承自Dictionary类
  • LinkedHashMap 键值对插入、输出顺序一致
  • 读取文件:properties
  • TreeMap

Collection工具类

操作Set、List、Map等的集合的工具类,包含对集合元素进行排序,查询,修改等操作

  1. 排序(都是静态方法)
    • reverse(List) 翻转List中的顺序
    • shuffle(List) 对List中的元素进行随机排序
理解Comparator接口中的返回值 1,-1,0
  • sort(List,comparator) 对List中的元素进行自然排序(升序)

    • 按照comparator重写的规则进行排序

    • 保持这个顺序就返回-1,表示不想调整顺序

    • 交换顺序就返回1,表示我想调整顺序

    • 什么都不做就返回0;所以 升序的话 如果1<2,返回-1,保持顺序[1,2],如果3>2,返回-1,交换顺序[2,3]

  • swap(List,int,int) 将List的i处元素与j处进行交换

在这里插入图片描述

测试题

在这里插入图片描述

  1. 试分析输出结果:

该 Cat类已重写了 HashCode和equals方法

HashSet set1 = new HashSet();//ok
Cat p1 = new Cat(1001,"AA");
Cat p2 = new Cat(1002,"BB");
set1.add(p1); set1.add(p2);
p1.Cname="CC";
set1.remove(p1);
System.out.println(set1);

set1.add(new Cat(1001,"CC"));
System.out.println(set1);

set1.add(new Cat(1001,"AA"));
System.out.println(set1);

当类重写了HashCode方法和equals方法,可知:

  • 该类的hash值 由属性决定。当属性改变,其hash值也会改变
@Override
public int hashCode() {
    return Objects.hash(Cname, id);
}
  1. remove()方法 根据hash删除。此时 p1对象hash是由 1001,“AA” 计算,而Cname变成“CC”,p1的hash值不变。此时remove根据 1001,"CC" 找 p1 ,肯定找不到,故没有删除p1.
  2. remove底层是按照修改name之后的对象获取hash进行搜索删除的,然而得到的索引和实际存放的索引不一样了
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

? 此时的元素:

[Cat{id=1002, Cname='BB'}, Cat{id=1001, Cname='CC'}]

  1. set1.add(new Cat(1001,"CC"));

    • 新对象p3 hash = 1001,“CC”. 另开辟了表空间
    • 绕不出去的问题在于p1.name=CC之后其实此时占用的还是AA的哈希位置,所以添加进去的CC经过哈希之后不可能在原来AA的位置

    [Cat{id=1002, Cname='BB'}, Cat{id=1001, Cname='CC'}, Cat{id=1001, Cname='CC'}]

  2. set1.add(new Cat(1001,"AA"));

    • ? 新对象p4 hash = 1001,“AA”. 与 p1 的hash一致。 但equals 两者不同,故在p1 后另加链表 p4

[Cat{id=1002, Cname='BB'}, Cat{id=1001, Cname='CC'}, Cat{id=1001, Cname='CC'}, Cat{id=1001, Cname='AA'}]

文章来源:https://blog.csdn.net/qq_45888242/article/details/135307869
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。