网站流量查询网站统计查询,wordpress上传目录,两个公司的网站建设,可以看男男做的视频网站目录 1、请简单介绍下 Java 的集合类吧。
Collection
Set
TreeSet和HashSet
List
ArrayList 和 LinkedList
数组和链表的区别
Java 的列表有哪些实现类#xff1f;
Vector
Queue
Map
能说下 HashMap 的实现原理吗#xff1f;
能说下 HashMap 的扩容机制吗#x…目录 1、请简单介绍下 Java 的集合类吧。
Collection
Set
TreeSet和HashSet
List
ArrayList 和 LinkedList
数组和链表的区别
Java 的列表有哪些实现类
Vector
Queue
Map
能说下 HashMap 的实现原理吗
能说下 HashMap 的扩容机制吗
HashMap与HashTable
HashSet 和 HashMap
LinkedHashMap 有了解过吗
TreeMap 有了解过吗
IdentityHashMap 有了解过吗
WeakHashMap 有了解过吗
ConcurrentHashMap 1.7和1.8有什么区别
ConcurrentHashMap#get 需要加锁吗
为什么 ConcunentHashMap 不支持 key 或者 value 为 null
2、你有听过 Copy-0n-Write 吗
3、ConcurentModificationException 这种错误有遇到过吗为什么会出现这个错误
扩展单线程情况下修改集合 1、请简单介绍下 Java 的集合类吧。
Java 集合从分类上看有 collection 和 map 两种。前者是存储对象的集合类,后者存储的是键值对 key-value)
Collection
Set
TreeSet和HashSet
主要功能是保证存储的集合不会重复至于集合是有序还是无序的需要看具体的实现类比如 TreeSet 就是有序的 HashSet 是无序的 List
ArrayList 和 LinkedList
列表具体的实现类有 ArrayList 和 LinkedList。 两者的区别在于底层实现不同前者是数组后者是双向链表。
数组和链表的区别
数组的内存是连续的且存储的元素大小是固定的实现上是基于一个内存地址然后由于元素固定大小支持利用下标的直接访问。
而由于要保持内存连续这个持性不能在内存中间空一块所以删除中间元素时就需要搬迁元素需进行内存拷贝所以说删除的效率不高。
链表的内存不需要连续它们是通过指针相连这样对内存的要求没那么高数组的申请需要一块连续的内存链表就可以散装内存不过链表需要额外存储指针所以总体来说链表的占用内存会大一些。
且由于是指针相连所以直接无法随机访问一个元素必须从头开始遍历。 空间局部性 (spatial locality) 如果一个存储器的位置被引用那么将来它附近的位置也会被引用。
根据这个原理就会有预读功能像 CPU 缓存就会读连续的内存这样一来如果你本就要遍历数组的那么你后面的数据就已经被上一次读取前面数据的时候一块被加载了这样就是 CPU 亲和性。
反观链表由于内存不连续所以预读不到所以CPU 亲和性低。
链表数组加了点约束的话还可以用作栈、队列和双向队列。 Java 的列表有哪些实现类
最常见的就是 ArrayList 和 LinkedList, 汪意这两者都不是并发容器所以线程不安全。
ArrayList 是基于动态数组实现的因此它的特性与数组一致随机访问很快删除和插入相对比较慢。
LinkedList 是基于双向链表实现的因此两端都能操作特性就是正常的链表特性两端插入删除很快但是随机访问需要遍历链表所以比较慢。 Vector
它也是基于动态数组实现与 ArrayList 类似但它是线程安全所有方法都是同步的都加了 synchronize 锁也因为同步开销较大所以它性能相对较低。 Queue
队列有序严格遵守先进先出常用的实现类就是 LinkedList。
优先队列即PriorityQueue, 内部是基于数组构建的用法就是你定义一个 comparator 自己定义对比规则这个队列就是按这个规则来排列出队的优先级。 Map
实现类 HashMap 无序。
还有两个实现类 LinkedHashMap 和 TreeMap, 前者里面搞了个链表这样塞入顺序就被保存下来了后者是红黑树实现了所以有序。 能说下 HashMap 的实现原理吗
HashMap 基于哈希表的数据结构实现允许存储键值对并且通过键快速访问对应的值。
它内部使用数组和链表在 Java 8 及以后还可以使用红黑树来存储元素每个数组槽位 (bucket)对应一个链表或红黑树。
数组内的元素保存了 key 和 value。 当要塞入一个键值对的时候会根据一个 hash 算法计算 key 的hash 值然后通过数组大小 n-1 hash 值之后得到一个数组的下标然后往那个位置塞入这键值对。
我们知道 hash 算法是可能产生冲突的且数组的大小是有限的所以很可能通过不同的 key 计算得到一样的下标因此为了解决键值对冲突的问题采了链表法如下图所示 当链表的长度大于 8 且数组大小大于等于 64 的时候就把链表转化成红黑树当红黑树节点小于6的时候又会退化成链表。 能说下 HashMap 的扩容机制吗
我们都知道 HashMap 是基于数组和链表红黑树来实现的。
在 HashMap 中有阈值的概念比如我们设置一个16 大小的 map, 那么默认的阈值等于 16 * 0.7512也就是说如果 map 中元素的数量超过 12 那么就会触发扩容。
扩容的时候默认会新建一个数组新数组的大小是老数组的两倍。然后将 map 内的元素重新 hash 映射搬运到新的数组中。
因为数组的长度是 2 的 n 次方所以设以前的数组长度 16 二进制表示是 010000 那么新数组的长度 32 二进制表示是 100000, 它们之间的差别就在于高位多了一个 1 而我们通过key 的 hash 值定位其在数组位置所采用的方法是数组长度-1 hash 。 HashMap与HashTable
线程安全性
HashMap: 不是线程安全的。如果多个线程同时访问一个 HashMap, 并且至少有一个线程在结构上修改了它比如添加或删除键值对可以通过以下代码封装进行同步
MapString,String map Collections.synchronizedMap(new HashMap());
Hashtable: 是线程安全的。所有的方法都加了锁可以在多线程环境中使用。
性能
HashMap: 由于没有同步开销所以它的性能一般比 Hashtable 更好尤其是在单线程环境中。
Hashtable: 由于每个方法都进行同步因此性能比HashMap 差。
null 值的处理
HashMap: 允许一个 null 键和多个 null 值。
HashtabIe 不允许 null 键和 null 值。如果将 null 键或值放入 Hashtable会抛出 NullPointerException. HashSet 和 HashMap
HashSet 其实内部的实现还是 HashMap!并且 HashSet 的add方法实际上调用的就是 HashMap 的put方法。
因此 HashSet 就是封装了一下 HashMap! 内部的实现逻辑其实都由 HashMap 来代劳。 LinkedHashMap 有了解过吗
LinkedHashMap 的父类是 HashMap 所以HashMap 有的它都有然后基于 HashMap 做了一些扩展。
首先它把 HashMap 的 Entry 加了两个指针before 和 after。 这目的已经很明显了就是要把塞入的 Entry 之间进行关联串成双向链表如下图红色的就是新增的两个指针 并且内部还有个 accessOrder 成员默认是false, 代表链表是顺序是按插入顺序来排的如果是 true 则会根据访问顺序来进行调整就是咱们熟知的 LRU 那种如果哪个节点访问了就把它移到最后代表最近访问的节点。
具体实现其实就是 HashMap 埋了几个方法然后 LinkedHashMap 实现了这几个方法做了操作比如以下这三个从方法名就能看出了访问节点之后干啥插入节点之后干啥删除节点之后干啥。 举个 afterNodelnsertion 的例子它埋在HashMap 的put里在塞入新节点之后会调用这个方法 然后 LinkedHashMap 实现了这个方法可以看到这个方法主要用来移除最老的节点。 看到这你能想到啥假如你想用 map 做个本地缓存由于缓存的数量不可能无限大所以你就能继承 LinkedHashMap 来实现当节点超过一定数量的时候在插入新节点的同时移除最老最久没有被访问的节点这样就实现了一个 LRU。 TreeMap 有了解过吗
TreeMap 内部是通过红黑树实现的可以让 key实现 Comparable 接囗或者自定义实现一个comparator 传入构造函数这样塞入的节点就会根据你定义的规则进行排序。
基本特性
• 数据结构 TreeMap 基于红黑树实现红黑树是一种自平衡的二叉查找树能够保证基本操作插入、删除、查找的时间复杂度为O(log n)。
• 键的有序性TreeMap 中的键是有序的默认按自然顺序键的 ComparabIe 实现排序也可以通过构造时提供的 Comparator 进行自定义排序。
• 不允许 null 键 TreeMap 不允许键为 null, 但允许值为 null。 IdentityHashMap 有了解过吗
它判断是否相等的依据不是靠 equals,而是对象本身是否是它自己。
什么意思呢首先看它覆盖的 hash 方法 可以看到它用了个 System.identityHashCode(x) ,而不是 x.hashCode() 。
而这个方法会返回原来默认的 hashCode 实现不管对象是否重写了 hashCode 方法默认的实现返回的值是对象的内存地址转化成整数。
它判断 key 是否相等并不靠 hash 值和 equals, 而是直接用了而其实就是地址判断只有相同的对象进行才会返回 true。 ldentityHashMap 的存储方式有点不一样它是将 value 存在 key 的后面。 WeakHashMap 有了解过吗
WeakHashMap 是 Java 中的一种特殊的 Map 实现它使用弱引用 WeakReference) 来存储键。
WeakHashMap 里对 key 的引用就是弱引用所以当一个键不再有任何强引用时即使它被WeakHashMap 引用着垃圾回收器也可以回收该键和它对应的值。
它被使用在临时需要大量数据但这些数据又可以因为内存吃紧随时被回收的场景。
比如一些缓存场景例如缓存一些图片当图片不再被其他部分引用时它们可以被垃圾回收从而避免内存泄漏。
在一些框架中需要为对象存储额外的元数据但不希望这些元数据影响对象的生命周期。可以用 WeakHashMap 来存储这些元数据。 ConcurrentHashMap 1.7和1.8有什么区别
ConcurrentHashMap 1.7
其实大体的哈希表实现跟 HashMap 没有本质的区别都是经过 key 的 hash 定位到一个下标然后获取元素如果冲突了就用链表相连。
差别就在于引入了一个 Segments 数组我们来看下大致的结构。 原理就是先通过 key 的 hash 判断得到 Segment数组的下标将这个 Segment 上锁然后再次通过 key 的 hash 得到 Segment 里 HashEntry数组的下标下面这步其实就是 HashMap 一致了所以我说差别就是引入了一个 Segments 数组。
因此可以简化的这样理解每个 Segment 数组存放的就是一个单独的 HashMap。 可以看到图上我们有 6 个 Segment, 那么等于有六把锁因此共可以有六个线程同时操作这个ConcurrentHashMap, 并发度就是 6 相比于直接将 put 方法上锁并发度就提高了这就是分段锁。
具体上锁的万式来源于 Segment, 这个类实际继承了 ReentrantLock 因此它自身具备加锁的功能。 ConcurrentHashMap 1.8
1.8 ConcurrentHashMap 做了更细粒度的锁控制可以理解为 1.8 HashMap 的数组的每个位置都是一把锁这样扩容了锁也会变多并发度也会增加。 思想的转变就是把粒度更加细化。不分段了我直接把 Node 数组的每个节点分别上一把锁这样并发度不就更高了吗
并且 1.8 也不借助于 ReentrantLock 了直接用synchronized 这也侧面证明都 1.8 了synchronized 优化后的速度已经不下于ReentrantLock 了。 1.8 的扩容它允许协助扩容也就是多线程扩容。 ConcurrentHashMap#get 需要加锁吗
不需要加锁。保证 Put 的时候线程安全之后 get 的时候只需要保证可见性即可而可见性不需要加锁。具体是通过 Unsafe#getXXXVolatile 和用 volatile 来修饰节点的 val 和 next 指针来实现的。 为什么 ConcunentHashMap 不支持 key 或者 value 为 null
1 避免二义性
因为在多线程情况下 get 方法返回 null 时无法区分 map 里到底是不存在在这个 key 还是说被 put(key, null) 了。
这里可能有人会说那 HashMap 不一样有这个问题 HashMap 可以通过 containsKey 来判断是否存在这个 key 而多线程使用的ConcurrentHashMap 就不能够。
比如你 get (key) 得到了 null, 此时 map 里面没有这个 key 的但是你不知道所以你想调用 containsKey 看看而恰巧在你调用之前别的线程 Put 了这个 key 这样你 containsKey 就发现有这个 key, 这是不是就发生误会了
2 简化实现
不支持 null, 这样在并发环境下可以避免对 null 的特殊处理可以减少代码中的条件分支提高性能和可维护性。 2、你有听过 Copy-0n-Write 吗
顾名思义当需要 write 的时候 copy 。
我们都知道操作系统有父子进程的概念当父进程创建子进程之后父子进程的内存空间是共享的只有当子进程或父进程尝试写入或修改数据的时候才需要复制一个内存新页面写入。
这样有什么好处
因为一开始共享内存所以在没有发生写入的时候内存其实压根不需要新复制一份当写入的时候才发生复制这就不仅节省内存也避免了内存频繁复制的开销。
copy-on-write 对读比较友好多个并发读可以共享互相不会阻塞且当有个写在修改数据的时候也不会阻塞读因为可以读老的数据。但是写是独占的。读写分离
不过 Copy-On-Write 也有缺点写操作会延迟因为写的时候需要拷贝数据这并不快。
如果写操作非常频繁就会一直拷贝数据开销比较大所以它适合读多写少的场景。
在 Java 中主要有 CopyOnWriteArrayList 这个实现类底层基于数组存储写的时候会烤贝一个新数组。它是线程安全的读不会被写阻塞。 3、ConcurentModificationException 这种错误有遇到过吗为什么会出现这个错误
这个错误发生在迭代集合对象时候修改集合本身内容包括新增、修改和删除。
其实这个错误是为了检测并发修改的行为在非线程安全的集合中并发修改集合数据可能会发生数据丢失等一些奇怪的问题。
因此 Java 引入了这个错误是为了保证集合迭代时语义的一致性。简单来说就是规矩就这样定了这个集合非并发安全的不让你改改了就报错。
它的原理是在集合内部维护了一个修改次数的记录如果发生了修改那么这个次数会增加。在每次迭代的时候会检查这个次数发现增加了就立马报错。
如果非要修改那么可以使用线程安全的集合例如可以使用 collections.synchronizedList 将List包装为线程安全的集合或者直接使用CopyOnWriteArrayListConcurrentHashMap 。 扩展单线程情况下修改集合
如果单线程在一个循环中遍历集合的同时直接修改集合也会报这个错可以通过 lterator 进行遍历并使用 lterator 提供的 remove 方法来删除元素可以避免 ConcurentModificationException。
