My-Notes

014.数据结构与集合源码

8分钟阅读

企业真题

链表和数组有什么区别？

来源：腾?

略

栈是如何运行的？

来源：西?信息技术

先进后出。属于 ADT(abstract data type)，可以使用数组、链表实现栈结构

ArrayList 的默认大小是多少，以及扩容机制

来源：顺?、凡?科技、国?电网、?实在、?软国际

初始大小 10，JDK 8：一开始 0，第一次加元素初始大小 10

扩容机制：1.5 倍，1.5 都不够的话扩到需要的容量

ArrayList 的底层是怎么实现的？

来源：腾?、湖??利软件、汇?云通、猎?、苏州???动、上海?进天下、北京博?软件、?科软、大连?点科技、中?亿达、德?物流、天?伟业、猫?娱乐

Object[]，动态扩容

在 ArrayList 中 remove 后面几个元素该怎么做？

来源：惠?、中?亿达

前移。保证空间连续

ArrayList 1.7 和 1.8 的区别

来源：拓?思

类似于饿汉式、懒汉式

数组和 ArrayList 的区别

来源：阿??巴、?科软

ArrayList 看做是对数组的封装。

什么是线程安全的 List？

来源：平?金服

  • Vector：线程安全的。
  • ArrayList：线程不安全。→ 使用同步机制处理。
  • HashMap：线程不安全。→ 使用同步机制处理（JUC：ConcurrentHashMap）

说说 HahMap 底层实现

来源：新?股份、顺?、猫?娱乐、腾?、上海??网络、滴?、纬?软件、上海?想、?昂、?蝶??云、宇?科技、?东数科、猎?网、?度、北京中??译咨询、湖??利软件、爱?信、杭州?智、汇??通、猎?、苏州博?讯动、上海?进天下、北京博?软件、?科软、大连?点科技、中?亿达、德?物流、天?伟业、阿??巴、?米、?节跳动

Hash + 数组 + 链表 + 红黑树

HashMap 初始值 16，临界值 12 是怎么算的

来源：软??力

16：从底层源码的构造器中看到的。

12：threshold，使用数组的长度 x 加载因子（loadFactor）

HashMap 长度为什么是 2 的幂次方

来源：国?时代

为了方便计算要添加的元素的底层的索引 i。

为什么要保持 table 数组一直是 2 的 n 次幂？

HashMap 怎么计算哈希值和索引？扩容机制？怎么解决 hash 冲突？

来源：?软国际、中软?腾、新?股份、顺?、凡?科技、好实?

略

HashMap 底层是数组+链表，有数组很快了，为什么加链表？

来源：润?软件

因为产生了哈希冲突。解决方案，使用链表的方式。保证要添加的元素仍然在索引 i 的位置上。

哈希冲突有多种解决方式，如：Python 顺位添加

HashMap 为什么长度达到一定的长度要转化为红黑树

来源：?度、?软国际

红黑树的时间复杂度 ，比单向链表的 效率高。

HashMap 什么时候扩充为红黑树，什么时候又返回到链表？

来源：汉?、杭州?智公司、百?云创、?软国际

  • 索引 i 的位置的链表长度超过 8 且数组长度达到 64，需要索引 i 位置要变成红黑树。
  • 当索引 i 的位置元素的个数低于 6 时，要红黑树结构转为单向链表。为什么？节省空间。

在 JDK1.8 中，HashMap 的数据结构与 1.7 相比有什么变化，这些变化的好处在哪里？

来源：海?科

  1. 在 JDK8 中，当创建了 HashMap 实例以后，底层并没有初始化 table 数组。当首次添加 (key,value) 时，进行判断，如果发现 table 尚未初始化，则对数组进行初始化。
  2. 在 JDK8 中，HashMap 底层定义了 Node 内部类，替换 JDK7 中的 Entry 内部类。意味着，我们创建的数组是 Node[]
  3. 在 JDK8 中，如果当前的 (key,value) 经过一系列判断之后，可以添加到当前的数组角标 i 中。如果此时角标 i 位置上有元素。在 JDK7 中是将新的 (key,value) 指向已有的旧的元素（头插法），而在 JDK8 中是旧的元素指向新的 (key,value) 元素（尾插法）。
    • “七上八下”
    • 解决多线程可能出现循环链表问题
  4. JDK7：数组+单向链表；JDK8：数组+单向链表 + 红黑树
    • 什么时候会使用单向链表变为红黑树：如果数组索引 i 位置上的元素的个数达到 8，并且数组的长度达到 64 时，我们就将此索引 i 位置上的多个元素改为使用红黑树的结构进行存储。
    • 为什么修改呢？红黑树进行 put() / get() / remove() 操作的时间复杂度为 ，比单向链表的时间复杂度 的好。性能更高。
    • 什么时候会使用红黑树变为单向链表：当使用红黑树的索引 i 位置上的元素的个数低于 6 的时候，就会将红黑树结构退化为单向链表。
    • 为什么退化呢？节省空间。

hashCode 和 equals 区别？

来源：海?供应链管理

略

hashCode() 与 equals() 生成算法、方法怎么重写？

来源：阿?校招

  • 进行 equals() 判断使用的属性，通常也都会参与到 hashCode() 的计算中。
  • 保证一致性。
  • 使用 IDEA 自动生成

重写 hashCode() 和 equals()

说一下 equals 和 == 的区别，然后问 equals 相等 hash 值一定相等吗？hash 值相等 equals 一定相等吗？

来源：南?电网、上海?智网络

  • equals 相等 hash 值一定相等吗? 是
  • hash 值相等 equals 一定相等吗？不一定

HashSet 存放数据的方式？

来源：拓?软件

底层使用 HashMap。说一下 HashMap

Set 是如何实现元素的唯一性？

来源：湖??利软件

hashCode + equals

用哪两种方式来实现集合的排序

来源：凡?科技、北京中??信科技

自然排序、定制排序。（两个接口）

关系图谱