526互联

集合+hashmap

发布时间 2023-08-15 22:29:14作者: 那一定是小锅巴

image-20230730195934181

数组

数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

image-20230814160053681

面试题：为什么数组索引从0开始？假如从1开始会怎么样？

image-20230814160538982

操作数组的时间复杂度

当未知数组查询时，时间复杂度为 O(n)

image-20230814161044731

总结

image-20230814162358182

——————————————————————————————————————————————

ArrayList

ArrayList底层的实现原理是什么

  • ArrayList底层是用动态的数组实现的
  • ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10
  • ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组
  • ArrayList在添加数组的时候
    • 确保数组已使用长度(size)加1之后足够存下下一个数据
    • 计算数组的容量，如果当前数据已使用长度+1后的大于当前的数组长度，则调用grow方法扩容(原来的1.5倍)
    • 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上
    • 返回添加成功布尔值

image-20230814164923204

如何实现数组和List之间的转换

image-20230814170103241

image-20230814170138948

——————————————————————————————————————————————————

链表

单向链表

  • 链表中的每一个元素称之为结点(Node)
  • 物理存储单元上，非连续、非顺序的存储结构
  • 单向链表：每个结点包括两部分：一个是存储数据元素的数据源，另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next

image-20230814172751018

image-20230814174156781

image-20230814174403567

双向链表

  • 每个结点不止有一个后继指针next指向后面的结点
  • 有一个前驱指针prew指向前面的结点

相比于单链表：

  • 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址
  • 支持双向遍历，增加操作的灵活性

image-20230814175327942

image-20230814180034201

总结

image-20230814180330269

——————————————————————————————————————————————————

ArrayList和LinkedList的区别是什么？

1.底层数据结构

  • ArrayList是动态数组的数据结构实现
  • LinkedList是双向链表的数据结构实现

2.操作数据效率

  • ArrayList按照下标查询的时间复杂度O(1) 【内存是连续的，根据寻址公式】，LinkedList不支持下标查询

  • 查询(未知索引)：ArrayList需要遍历，链表也需要遍历，时间复杂度都是O(n)

  • 新增和删除

    • ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)
    • LinkedList头尾节点增删时时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)

3.内存空间占用

  • ArrarList底层是数组，内存连续，节省内存
  • LinkedList是双向链表需要存储数据，和两个指针，更占用内存

4.线程安全

  • ArrayList和LinkedList都不是线程安全的

  • 如果需要保证线程安全，有两种方案：

    • 在方法内使用， 局部变量则是线程安全的

    • 使用线程安全的ArrayList和LinkedList

      List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>());
List<Object> syncLinkedList = Collections.synchronizedList(new LinkedList<>());

——————————————————————————————————————————————————

HashMap

二叉树

image-20230815102246681

image-20230815102413114

image-20230815102349515

红黑树

image-20230815102215278

image-20230815102815770

散列表（Hash Table）

散列表（Hash Table）又名哈希表/Hash表，是根据键(key)直接访问在内存存储位置值(Value)的数据结构，它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

1.什么是散列表？

  • 散列表（Hash Table）又名哈希表/Hash表
  • 根据键(key)直接访问在内存存储位置值(Value)的数据结构
  • 由数组演化而来的，利用了数组支持按照下标进行随机访问数据

2.散列冲突

  • 散列冲突又称哈希冲突，哈希碰撞
  • 指多个key映射到同一数组下标位置

3.散列冲突-链表法(拉链)

  • 数组的每个下标位置称之为桶(bucket)或槽（slot）
  • 每个桶（槽）对应一条链条
  • hash冲突后的元素都放到相同槽位对应的链表中或红黑树中

HashMap的实现原理

数据结构：底层使用hash表数据结构，即数组和链表或红黑树
  1. 往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
  2. 存储时，如果出现hash值相同的key，此时有两种情况。
    1. 如果key相同，则覆盖原始值
    2. 如果key不同（出现哈希冲突），则将当前的key-value放入链表或红黑树中
  3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值

HashMap的jdk1.7和jdk1.8有什么区别

  • JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合，数组中的每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可
  • JDK1.8在解决哈希冲突时有较大的变化，当链表长度大于阙值（默认为8）时并且数组长度达到64时，将链表转化成红黑树，以减少搜索时间。扩容resize（）时，红黑树拆分成树的结点数小于等于临界值6个，则退化成链表。

HashMap的put方法的具体流程

  • HashMap是懒惰加载，在创建对象时并没有初始化数组
  • 在无参的构造函数中，设置了默认的加载因子是0.75

image-20230815122654015

  1. 判断键值对数组table是否为空或为null，否则执行resize()进行扩容（初始化）
  2. 根据键值key计算hash值得到数组索引
  3. 判断table[i] == null,条件成立，直接新建节点添加
  4. 如果table[i] == null，不成立
    1. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value
    2. 判断table[i]是否为treeNode，即table[i]是否为红黑树，如果是红黑树，则直接在树中插入键值对
    3. 遍历table[i]，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现key已经存在直接覆盖value
  5. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold（数组长度*0.75），如果超过，进行扩容

HashMap的扩容机制

image-20230815161649082

  • 在添加元素或者初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次都是达到扩容阙值（数组长度*0.75）
  • 每次扩容的时候，都是扩容之前容量的2倍
  • 扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
    • 没有hash冲突的节点，则直接使用e.hash & (newCap - 1)计算新数组的索引位置
    • 如果是红黑树，走红黑树的添加
    • 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

image-20230815164937623