创新平台网站建设方案,电商软件平台开发,网站开发综合实训总结,网站建设外包合同模板马上就要到金三银四佳季了#xff0c;是找工作的好时候#xff0c;小伙伴们一定要把握好时机#xff0c;找到心仪的高薪工作。找工作就少不了面试#xff0c;那我们从现在开始#xff0c;多刷刷面试题#xff0c;查缺补漏#xff01;#xff01;#xff01; 目录
⭐常… 马上就要到金三银四佳季了是找工作的好时候小伙伴们一定要把握好时机找到心仪的高薪工作。找工作就少不了面试那我们从现在开始多刷刷面试题查缺补漏 目录
⭐常见的数据结构⭐
⭐集合和数组的区别⭐
⭐List 和 Map、Set 的区别⭐
⭐List 和 Map、Set 的实现类⭐
⭐Hashmap的底层原理⭐
⭐Hashmap和hashtable ConcurrentHashMap区别⭐ ⭐常见的数据结构⭐ 常用的数据结构有数组栈队列链表树散列堆图 数组是最常用的数据结构数组的特点是长度固定数组的大小固定后就无法扩容了 数组只能存储一种类型的数据 添加删除的操作慢因为要移动其他的元素。
栈是一种基于先进后出FILO的数据结构是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据先进入的数据被压入栈底最后的数据在栈顶需要读数据的时候从栈顶开始弹出数据最后一个数据被第一个读出来。
队列是一种基于先进先出FIFO的数据结构是一种只能在一端进行插入在另一端进行删除操作的特殊线性表它按照先进先出的原则存储数据先进入的数据在读取数据时先被读取出来。
链表是一种物理存储单元上非连续、非顺序的存储结构其物理结构不能只表示数据元素的逻辑顺序数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结节链表中的每一个元素称为结点组成结点可以在运行时动态生成。根据指针的指向链表能形成不同的结构例如单链表双向链表循环链表等。
树是我们计算机中非常重要的一种数据结构同时使用树这种数据结构可以描述现实生活中的很多事物例如家谱、单位的组织架构等等。有二叉树、平衡树、红黑树、B树、B树。
散列表也叫哈希表是根据关键码和值 (key和value) 直接进行访问的数据结构通过key和value来映射到集合中的一个位置这样就可以很快找到集合中的对应元素。
堆是计算机学科中一类特殊的数据结构的统称堆通常可以被看作是一棵完全二叉树的数组对象。
图的定义图是由一组顶点和一组能够将两个顶点相连的边组成的 ⭐集合和数组的区别⭐ 区别数组长度固定 集合长度可变 数组中存储的是同一种数据类型的元素可以存储基本数据类型也可以存储引用数据类型集合存储的都是对象而且对象的数据类型可以不一致。在开发当中一般当对象较多的时候使用集合来存储对象。 ⭐List 和 Map、Set 的区别⭐ List和Set是存储单列数据的集合Map是存储键值对这样的双列数据的集合 List中存储的数据是有顺序的并且值允许重复 Map中存储的数据是无序的它的键是不允许重复的但是值是允许重复的 Set中存储的数据是无顺序的并且不允许重复但元素在集合中的位置是由元素的hashcode决定即位置是固定的Set集合是根据hashcode来进行数据存储的所以位置是固定的但是这个位置不是用户可以控制的所以对于用户来说set中的元素还是无序的。 ⭐List 和 Map、Set 的实现类⭐ (1)Connection接口:List 有序,可重复 ArrayList 优点: 底层数据结构是数组查询快增删慢。 缺点: 线程不安全效率高Vector 优点: 底层数据结构是数组查询快增删慢。 缺点: 线程安全效率低, 已给舍弃了LinkedList 优点: 底层数据结构是链表查询慢增删快。 缺点: 线程不安全效率高Set 无序,唯一 HashSet 底层数据结构是哈希表。(无序,唯一) 如何来保证元素唯一性? 依赖两个方法hashCode()和equals() LinkedHashSet 底层数据结构是链表和哈希表。(FIFO插入有序,唯一) 1.由链表保证元素有序 2.由哈希表保证元素唯一 TreeSet 底层数据结构是红黑树。(唯一有序) 1. 如何保证元素排序的呢? 自然排序 比较器排序 2.如何保证元素唯一性的呢? 根据比较的返回值是否是0来决定 (2)Map接口有四个实现类 HashMap 基于 hash 表的 Map 接口实现非线程安全高效支持 null 值和 null 键 线程不安全。HashTable 线程安全低效不支持 null 值和 null 键 LinkedHashMap 线程不安全是 HashMap 的一个子类保存了记录的插入顺序 TreeMap 能够把它保存的记录根据键排序默认是键值的升序排序线程不安全。 ⭐Hashmap的底层原理⭐ HashMap在JDK1.8之前的实现方式 数组链表, 但是在JDK1.8后对HashMap进行了底层优化,改为了由 数组链表或者数值红黑树实现,主要的目的是提高查找效率 Jdk8数组链表或者数组红黑树实现当链表中的元素超过了 8 个以后 会将链表转换为红黑树当红黑树节点 小于 等于6 时又会退化为链表。当new HashMap():底层没有创建数组首次调用put()方法示时底层创建长度为16的数组jdk8底层的数组是Node[],而非Entry[]用数组容量大小乘以加载因子得到一个值一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍专业术语叫做扩容在做扩容的时候会生成一个新的数组原来的所有数据需要重新计算哈希码值重新分配到新的数组所以扩容的操作非常消耗性能.默认的负载因子大小为0.75数组大小为16。也就是说默认情况下那么当HashMap中元素个数超过16*0.7512的时候就把数组的大小扩展为2*1632即扩大一倍。 在我们Java中任何对象都有hashcodehash算法就是通过hashcode与自己进行向右位移16的异或运算。这样做是为了计算出来的hash值足够随机足够分散还有产生的数组下标足够随机map.put(k,v)实现原理 1首先将k,v封装到Node对象当中节点。 2先调用k的hashCode()方法得出哈希值并通过哈希算法转换成数组的下标。 3下标位置上如果没有任何元素就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true那么这个节点的value将会被覆盖。 map.get(k)实现原理 (1)、先调用k的hashCode()方法得出哈希值并通过哈希算法转换成数组的下标。 (2)、在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有则返回null。如果这个位置上有单向链表那么它就会拿着参数K和单向链表上的每一个节点的K进行equals如果所有equals方法都返回false则get方法返回null。如果其中一个节点的K和参数K进行equals返回true那么此时该节点的value就是我们要找的value了get方法最终返回这个要找的value。 Hash冲突 不同的对象算出来的数组下标是相同的这样就会产生hash冲突当单线链表达到一定长度后效率会非常低。在链表长度大于8的时候将链表就会变成红黑树提高查询的效率。⭐Hashmap和hashtable ConcurrentHashMap区别⭐ 1、HashMap 是非线程安全的HashTable 是线程安全的。 2、HashMap 的键和值都允许有 null 值存在而 HashTable 则不行。 3、因为线程安全的问题HashMap 效率比 HashTable 的要高。 4、Hashtable 是同步的而 HashMap 不是。因此HashMap 更适合于单线 程环境而 Hashtable 适合于多线程环境。一般现在不建议用 HashTable, ① 是 HashTable 是遗留类内部实现很多没优化和冗余。②即使在多线程环境下 现在也有同步的 ConcurrentHashMap 替代没有必要因为是多线程而用 HashTable。 HashTable 使用的是 Synchronized 关键字修饰ConcurrentHashMap 是JDK1.7使用了锁分段技术来保证线程安全的。JDK1.8ConcurrentHashMap取消了Segment分段锁采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似数组链表/红黑二叉树。 synchronized只锁定当前链表或红黑二叉树的首节点这样只要hash不冲突就不会产生并发效率又提升N倍。
